最小成本： n 个顶点，用 n−1 条边把一个连通图连接起来，并且使得权值的和最小。 最小生成树：构造连通网的最小代价生成树。

根据原来写的博客：【图】图的定义，里面提到一个连通图的生成树是一个极小连通子图，它含有图中全部的顶点，但只有足以构成一棵树的 n−1 条边。

找连通网的最小生成树，经典的有两种算法：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。

先给出一个连通网：

普里姆（Prim）算法

基本思想

假设 N=(V,{E}) 是连通网， TE 是 N 上最小生成树中边的集合。 算法从 U=u0(u0ϵV),TE={} 开始，重复执行下述操作：

在所有 uϵV,vϵV−U 的边 (u,v)ϵE 中找一条代价最小的边 (u0,v0) 并入集合 TE ，同时 v0 并入 U ，直至 U=V 为止。

此时 TE 中必有 n−1 条边，则 T=(V,{TE}) 为 N 的最小生成树。

普里姆（Prim）算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树。

图解

下图给出权值矩阵。

从第一个顶点 A 开始通过普里姆算法生成最小生成树。 1、初始状态： V 是所有顶点的集合，即V={A,B,C,D,E,F,G,H,I}， U 和 TE 都为空。 初始化一个数组 lowcost={∞,∞,∞,∞,∞,∞,∞,∞} ，用来更新当前最小权值。 2、将顶点 A 加入到 U 中。 此时， U={A},V−U={B,C,D,E,F,G,H,I} 。如图2。 将顶点 A 的更小的权值更新进lowcost={0,10,∞,∞,∞,11,∞,∞,∞} 此时代价最小边为 10。 3、选取顶点 B ，将顶点 B 加入到 U 中。 此时，U={A,B},V−U={C,D,E,F,G,H,I}。如图3。 将顶点 B 的更小的权值更新进lowcost={0,0,18,∞,∞,11,16,∞,12} 此时代价最小边为 11。

4、选取顶点 F ，将顶点 F 加入到 U 中。 此时，U={A,B,F},V−U={C,D,E,G,H,I}。如图4。 将顶点 F 的更小的权值更新进lowcost={0,0,18,∞,26,0,16,∞,12} 此时代价最小边为 12。 5、选取顶点 I ，将顶点 I 加入到 U 中。 此时，U={A,B,F,I},V−U={C,D,E,G,H}。如图5。 将顶点 I 的更小的权值更新进lowcost={0,0,8,21,26,0,16,∞,0} 此时代价最小边为 8。 6、选取顶点 C ，将顶点 C 加入到 U 中。 此时，U={A,B,F,I,C},V−U={D,E,G,H}。如图6。 将顶点 C 的更小的权值更新进lowcost={0,0,0,21,26,0,16,∞,0} 此时代价最小边为 16。 7、选取顶点 G ，将顶点 G 加入到 U 中。 此时，U={A,B,F,I,C,G},V−U={D,E,H}。如图7。 将顶点 G 的更小的权值更新进lowcost={0,0,0,21,26,0,0,19,0} 此时代价最小边为 19。 8、选取顶点 H ，将顶点 H 加入到 U 中。 此时，U={A,B,F,I,C,G,H},V−U={D,E}。如图8。 将顶点 H 的更小的权值更新进lowcost={0,0,0,16,7,0,0,0,0} 此时代价最小边为 7。 9、选取顶点 E ，将顶点 E 加入到 U 中。 此时，U={A,B,F,I,C,G,H,E},V−U={D}。如图9。 将顶点 E 的更小的权值更新进lowcost={0,0,0,16,0,0,0,0,0} 此时代价最小边为 16。 10、选取顶点 D ，将顶点 D 加入到 U 中。 此时，U={A,B,F,I,C,G,H,E,D},V−U={}。如图10。 将顶点 H 的更小的权值更新进lowcost={0,0,0,0,0,0,0,0,0} 此时，最小生成树构造完成。包括的顶点依次是： A,B,F,I,C,G,H,E,D 。

时间复杂度

有两个嵌套循环，所以时间复杂度为 O(n2) 。