最小成本：
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)
。
