本文共 857 字，大约阅读时间需要 2 分钟。
最小生成树，解决网络联通问题，最小联通权，唯一性判定。
克鲁斯卡尔：
贪心思想，适合稀疏图，O(ElogE)
用堆维护边，最小权边优先考虑。 并查集加速联通分量的判断。模版题：ZOJ1203，POJ1861，POJ1251，POJ2031，POJ2421
普里姆：
贪心思想，适合稠密图，O(N*N)
维护一个长度为N的数组，保存当前可到达点的最短距离，若目前无法到达则INT_MAX，若已经计算过，则-1。模版题：ZOJ1586，POJ1789，POJ2349，POJ1751，POJ1258
较难问题A：
POJ3026 Borg迷宫，题意比较难读，50*50迷宫中有墙，有数个A需要感染，有1个初始位置S，保证所有S和A是可达的。 感染规则为，从S出发，可以是多个感染源同时出发，感染源意识是相同的，只要有一个感染源感染了新A，则其他感染源不会在考虑这个A，感染源感染了新A后可以再分裂成多个感染源。 则所有感染源走过的路径和是？读懂题后发现是最小生成树，哈希+BFS+prim。
A和S可以统一考虑，从不从S出发无所谓。
对每个A使用BFS找到它和其他A的最短距离，构造A全连接图。 具体做法为，把每个A坐标对应上一个唯一id，用哈希实现(x,y)->id 构造邻接矩阵，初始INT_MAX，在BFS时不断更新最小值即可。 BFS搜索时，vis矩阵表示节点是否访问过，避免BFS重复访问。 最后，对A全连接图使用prim找到最小生成树即可。MST唯一性：
对所有相同权值边做标记，
先用克鲁斯卡尔或普里姆生成一遍MST，若没有包含标记边，则MST唯一。 否则，去掉标记边，重新MST，若MST权值相同，则不唯一，否则唯一。模版题，POJ1679
实现上，
利用克鲁斯卡尔比较简单， 对边排序后，每个边维护一个flag值，表示是否有与之相同的边。 再维护一个used值，初始为0，第一次MST时置为1，第二次时若为1且flag为真，则跳过。转载地址：http://fdwji.baihongyu.com/