最小生成树之 Prim算法 & Kruskal算法
1 描述
问题：修建一个连接各个小区与煤气供应站点之间的管道，使得造价成本最低，即构造一颗最小生成树。但是如何求解？
对应模型：树结构，生成树，最小生成树
2 prim算法实例
基本思想：在满足如下条件的边中选出一条最小的边：
一端已选，另一端未选。
因此，该算法需要给出起点，以作为已选顶点。
对下图所示图，用Prim算法求最小生成树。
3 Kruskal算法实例
反复在满足如下条件的边中选出一条最小的边——和已选边不构成回路。
判断构成回路的经典方法：电位法：
初始状态：各顶点的电位=顶点号
每当选择一条边时，相连通的顶点的电位全都按照其中最小的值设置。
由此可知新的候选边是否和已选边构成回路
Kruskal算法的时空复杂度为Ｏ(eloge)、Ｏ() 。其时间性能和空间性能都不是很如意。