Prim算法
(1)将G剪切成两个集合A、B，A中只有一个点r
(2)取最小权的交叉边(x,y)，x∈A, y∈B
(3)将y加入A
(4)如果已经加了n-1条边，结束。否则，转 (3)
Kruskal算法
(1)将G所有条边按权从小到大排序；图mst开始为空
(2)从小到大次序取边(x,y)
(3)若加入边(x,y)，mst就有环，则放弃此边，转(2)
(4)将边(x,y)加入mst，如果已经加了n-1条边，结束。否则，转 (2)
本算法的要点在如何判断加入边（x,y）构成了环。可以化为判断xy是否相连，可用并查集进行查找。
对稀疏图一般用Kruskal算法。
平面上有K个水源（井），N个居民供水点，怎样用最少的管道使这N个居民点都能用连接到水源。注：边只能水源、居民点之间直接相连。
这个道题可以加一个虚节点，到各个水源的距离都为0，没有到其它点距离的，则使得个点之间连通。从而MST。