1.最小生成树的定义

图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树 (Minimum Spanning Tree，MST) ；

一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的 n − 1 n-1n−1 条边；

对于一个带权 (假定每条边上的权均为大于零的数) 连通无向图 G GG 中的不同生成树，其每棵树的所有边上的权值之和也可能不同；

简单来说，对于一个有 $n$ 个点的图，边一定是大于等于 $n−1$ 条的，最小生成树就是在这些边中选择 $n−1$ 条出来连接所有的 n 个点，且这 $n−1$ 条边的边权之和是所有方案中最小的；

2. Prim 算法

2.1. 思路

Prim 算法是一种构造性算法；

假设 G = ( V , E ) 是一个具有 $n$ 个顶点的带权连通无向图， T = ( U , TE ) 是 G 的最小生成树，其中 U 是 T 的顶点集， TE 是 T 的边集，则由 G 构造从起始顶点 v 出发的最小生成树 T 的步骤如下：

初始化 U = { v } ；以 v 到其他顶点的所有边为候选边；

重复以下步骤 $n−1$ 次，使得其他 $n−1$ 个顶点被加入到 U 中：

以顶点集 U 和顶点集 V − U 之间的所有边(称为割集 ( U , V−U ) 作为候选边，从中挑选权值最小的边(称为轻边)加入 TE ，设该边在 V−U 中的顶点是 k ，将 k 加入 U 中；

考察当前 V−U 中的所有顶点 j ，修改候选边，若 (k,j) 的权值小于原来和顶点 j 关联的候选边，则用 (k,j) 取代后者作为候选边；

2.2. 例子

使用 Prim 算法生成图的最小生成树，以结点 6 作为起点；

将结点划分成两个集合 U 和 V−U ；

1. U = { 6 } , V−U = { 1 , 2 , 3 , 4 , 5 , 7 } ；

候选边有 (6, 1, 1) 和 (6, 5, 8) ；

选择 (6, 1, 1) 为最小生成树的一条边，并且将结点1加入到 U 集合中；

此时最小生成树为，

2. U = { 6 , 1 } , V − U = { 2 , 3 , 4 , 5 , 7 } ；

侯选边有 (1, 2, 6) 和 (6, 5 ,8) ;

选择 (1, 2, 6) 为最小生成树的一条边，并且将结点 2 加入 U 集合中；

此时最小生成树为，

3. U = { 6 , 1 , 2 , 7 } , V − U = { 3 , 4 , 5 } ； 侯选边有 (6, 5, 8), (7, 5, 7), (7, 4, 5), (2, 3, 4)；

选择 (2, 3, 4) 为最小生成树的一条边，并且将结点3加入 U 集合中；

此时最小生成树为，

4. U = { 6 , 1 , 2 , 7 , 3 } , V − U = { 4 , 5 } ； 侯选边有 (6, 5, 8), (7, 5, 7), (4, 5, 6) ；

选择 (4, 5, 6) 为最小生成树的一条边，并且将结点5加入 U 集合中；

$n−1$ 轮执行完毕，得到最小生成树；