---

一、最小生成树的概念

一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。

对于一个带权连通无向图 G ，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。权值之和最小的那颗生成树称为 G 的最小生成树（Minimum-Spanning-Tree, MST）。

1. 最小生成树的几条性质

• 若图 G 中存在权值相同的边，则 G 的最小生成树可能不唯一，即最小生成树的树形不唯一；当图 G 中的各边权值互不相等时，G 的最小生成树是唯一的。

• 若无向连通图 G 的边数比顶点数少 1 ，即 G 本身是一棵树时，则 G 的最小生成树就是它本身。

• 虽然最小生成树不唯一，但其对应的边的权值之和总是唯一的，而且是最小的。

• 最小生成树的边数为顶点数减 1 。

• 虽然最小生成树中所有边的权值之和最小，但不能保证任意两个顶点之间的路径是最短路径。

最小生成树算法主要有 Prim 算法和 Kruskal 算法，它们都基于贪心算法的策略，其中 Prim 最小生成树算法应用了类似广度优先搜索（Breadth-First-Search, BFS）的思想。采用不同存储结构时 Prim 算法和 Kruskal 算法的时间复杂度如下图所示：（其中 n 为顶点数，e 为边数）

	Prim 算法	Kruskal 算法
邻接矩阵	O(n2)	/
邻接表	/	O(e·loge)

2. 例题

① 任何一个无向连通图的最小生成树（ A ）。
A. 有一棵或多棵
B. 只有一棵
C. 一定有多棵
D. 可能不存在

② 以下叙述中，正确的是（ A ）。
A. 只要无向连通图中没有权值相同的边，则其最小生成树唯一
B. 只要无向图中有权值相同的边，则其最小生成树一定不唯一
C. 从 n 个顶点的连通图中选取 n-1 条权值最小的边，即可构成最小生成树
D. 设连通图 G 含有 n 个顶点，则含有 n 个顶点、n-1 条边的子图一定是 G 的生成树

③ 设有 n 个顶点的无向连通图的最小生成树不唯一，则下列说法中正确的是（ A ）。
A. 图的边数一定大于 n-1
B. 图的权值最小的边一定多余
C. 图的最小生成树的代价不一定相等
D. 图的各条边的权值不相等

④ 【2023 统考真题】已知无向连通图 G 中各边的权值均为 1 。在下列算法中，一定能够求出图 G 中从某顶点到其余各顶点最短路径的是（ B ）。
I. Prim 算法 II. Kruskal 算法 III. 图的广度优先搜索算法
A. 仅 I
B. 仅 III
C. 仅 I、II
D. I、II、III

二、Prim 算法

1. 步骤

• 初始时从图中任取一顶点加入树 T ，此时树中只含有一个顶点；
• 之后选择一个与当前 T 中顶点集合距离最近的顶点，并将该顶点和相应的边加入 T ，每次操作后T中的顶点数和边数都增 1 ；
• 重复第二步，直至图中所有的顶点（n 个）都并入 T ，得到的 T 就是最小生成树，此时 T 中必然有 n-1 条边。

2. 示例

（b）图中权值最小的边为 V₁V₃（权值为 1），因此将顶点 V₁、V₃ 以及连接这两个顶点的边加入树 T 中；

（c）将顶点 V₁、V₃ 看成一个集合，找出一个与当前 T 中顶点集合距离最近的顶点，即权值最小的顶点，并将该顶点和相应的边加入 T ，因此将顶点 V₆ 以及连接 V₃、V₆ 的边加入树 T 中；
（顶点集合为 {V₁, V₃} ，其中 V₁V₂ 的权值为 6 、V₁V₄ 的权值为 5 、V₃V₂ 的权值为 5 、V₃V₄ 的权值为 5 、V₃V₅ 的权值为 6 、V₃V₆ 的权值为 4）

（d）将顶点 V₄ 以及连接 V₆、V₄ 的边加入树 T 中；
（顶点集合为 {V₁, V₃, V₆} ，其中 V₁V₂ 的权值为 6 、V₁V₄ 的权值为 5 、V₃V₂ 的权值为 5 、V₃V₄ 的权值为 5 、V₃V₅ 的权值为 6 、V₆V₄ 的权值为 2、V₆V₅ 的权值为 6）

（e）将顶点 V₂ 以及连接 V₃、V₂ 的边加入树T中，虽然 V₁V₄、V₃V₄ 的权值与 V₃V₂ 一样，都是最小权值，但是由于顶点 V₁、V₃、V₄ 都在树 T 中，因此不予考虑；
（顶点集合为 {V₁, V₃, V₆, V₄} ，其中 V₁V₂ 的权值为 6 、V₁V₄ 的权值为 5 、V₃V₂ 的权值为 5、V₃V₄ 的权值为 5 、V₃V₅ 的权值为 6 、V₆V₅ 的权值为 6）

（f）将顶点 V₅ 以及连接 V₅、V₂ 的边加入树 T 中；
（顶点集合为 {V₁, V₃, V₆, V₄, V₂} ，其中 V₁V₂ 的权值为 6 、V₁V₄ 的权值为 5 、V₃V₄ 的权值为 5 、V₃V₅ 的权值为 6 、V₆V₅ 的权值为 6 、V₂V₅ 的权值为 3）

3. 时间复杂度

Prim 算法采用邻接矩阵存储结构时的时间复杂度为 O(|V|²) ，不依赖于 |E| ，因此它适用于求解边稠密的图的最小生成树。

4. 例题

用 Prim 算法求一个带权连通图的最小生成树，在算法执行的某个时刻，已选取的顶点集合 U = {1, 2, 3} ，已选取的边集合 TE = {(1, 2), (2, 3)} ，要选取下一条权值最小的边，应当从（ A ）组中选取。
A. {(1, 4), (3, 4), (3, 5), (2, 5)}
B. {(3, 4), (3, 5), (4, 5), (1, 4)}
C. {(1, 2), (2, 3), (3, 5)}
D. {(4, 5), (1, 3), (3, 5)}

二、Kruskal 算法

与 Prim 算法从顶点开始扩展最小生成树不同，Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

1. 步骤

• 初始时为只有 n 个顶点而无边的非连通图 T ，每个顶点自成一个连通分量；
• 按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在 T 中不同的连通分量上（使用并查集判断这两个顶点是否属于同一颗集合树），则将此边加入 T ，否则舍弃此边而选择下一条权值最小的边；
  【树与二叉树的应用——并查集】
• 重复第二步，直至T中所有顶点都在一个连通分量上。

2. 示例

V₁V₃（权值为 1）< V₄V₆（权值为 2）< V₂V₅（权值为 3）< V₃V₆（权值为 4）< V₁V₄、V₂V₃、V₃V₄（权值为 5）< V₁V₂、V₃V₅、V₅V₆（权值为 6）

（b）图中权值最小的边为 V₁V₃（权值为 1），因此将顶点 V₁、V₃ 以及连接这两个顶点的边加入树 T 中，此时树的顶点集合为 {V₁, V₃} ；

（c）图中权值第二小的边为 V₄V₆（权值为 2），因此将顶点 V₄、V₆ 以及连接这两个顶点的边加入树 T 中，此时树的顶点集合为 {{V₁,V₃}, {V₄,V₆}} ；

（d）图中权值第三小的边为 V₂V₅（权值为 3），因此将顶点 V₂、V₅ 以及连接这两个顶点的边加入树 T 中，此时树的顶点集合为 {{V₁,V₃}, {V₄,V₆}, {V₂,V₅}} ；

（e）图中权值第四小的边为 V₃V₆（权值为 4），因此将连接这两个顶点的边加入树 T 中，此时树的顶点集合为 {{V₁,V₃,V₄,V₆}, {V₂,V₅}}；

（f）图中权值第五小的边为 V₁V₄、V₂V₃、V₃V₄（权值为 5），由于顶点 V₁、V₃、V₄ 在同一个连通分量上，所以舍弃边 V₁V₄ 和 V₃V₄ ，因此将连接顶点 V₂、V₃ 的边加入树 T 中，此时树的顶点集合为 {V₁, V₃, V₄, V₆, V₂, V₅} ；

3. 时间复杂度

在 Kruskal 算法中。最坏情况需要对 |E| 条边各扫描一次，通常采用堆来存放边的集合，每次选择最小权值的边需要 O(log₂|E|) 的时间；每次使用并查集来快速判断两个顶点是否属于一个集合所需的时间为 O(α(|V|)) ，α(|V|) 的增长极其缓慢，可视作常数。算法的总时间复杂度为 O(|E|log₂|E|) ，不依赖于 |V| ，因此 Kruskal 算法适合于边稀疏而顶点较多的图。

4. 例题

① 用 Prim 算法和 Kruskal 算法构造图的最小生成树，所得到的最小生成树（ C ）
A. 相同
B. 不相同
C. 可能相同，可能不同
D. 无法比较

② 用 Kruskal 算法求一个带权连通图的最小生成树，在算法执行的某个时刻，已选取的边集合 TE = {(1, 2), (2, 3), (3, 5)} ，要选取下一条权值最小的边，不可能选取的边是（ C ）。
A. (3, 6)
B. (2, 4)
C. (1, 3)
D. (1, 4)

③ 【2012 统考真题】下列关于最小生成树的叙述中，正确的是（ A ）。
I. 最小生成树的代价唯一
II. 所有权值最小的边一定会出现在所有的最小生成树中
III. 使用 Prim 算法从不同顶点开始得到的最小生成树一定相同
IV. 使用 Prim 算法和 Kruskal 算法得到的最小生成树总不相同
A. 仅 I
B. 仅 II
C. 仅 I 、III
D. 仅 II 、IV

④ 【2015 统考真题】求下面的带权图的最小（代价）生成树时，可能是 Kruskal 算法第 2 次选中但不是 Prim 算法（从 V₄ 开始）第 2 次选中的边是（ C ）。

A. (V₁, V₃）
B. (V₁, V₄）
C. (V₂, V₃）
D. (V₃, V₄）

⑤ 【2020 统考真题】已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加到最小生成树中的边依次是（ A ）。

A. (b, f), (b, d), (a, e), (c, e), (b, e)
B. (b, f), (b, d), (b, e), (a, e), (c, e)
C. (a, e), (b, e), (c, e), (b, d), (b, f)
D. (a, e), (c, e), (b, e), (b, f), (b, d)