最小生成树算法详解（Kruskal & Prim）
最小生成树（Minimum Spanning Tree, MST）是图论中的一个经典问题，其目标是在一个加权连通无向图中找到一个子图，该子图是一棵树，且包含图中的所有顶点，同时使得树上所有边的权值之和最小。以下是两种常用的最小生成树算法：Kruskal算法和Prim算法。
一、Kruskal算法
1. 算法思想
Kruskal算法是一种基于贪心策略的算法，其核心思想是从小到大选择边，每次选择一条权值最小的边，确保加入该边后不会形成环，直到生成树包含所有顶点。
2. 算法步骤
1. 初始化：将所有边按权值从小到大排序。
2. 构建生成树：
- 初始化一个空的边集合T（用于存储生成树的边）。
- 遍历排序后的边集合，对于每条边(u, v)：
- 如果u和v不在同一个连通分量中，则将边(u, v)加入T，并合并u和v所在的连通分量。
- 如果u和v已经在同一个连通分量中，则跳过该边（避免形成环）。
3. 终止条件：当T中的边数等于顶点数减一时，算法结束。
3. 关键点
- 连通分量的维护：通常使用并查集（Union-Find）来高效判断两个顶点是否属于同一个连通分量。
- 时间复杂度：排序的时间复杂度为O(E log E)（E为边数），并查集操作的时间复杂度接近O(1)，总复杂度为O(E log E)。
4. 示例
假设有以下图：
顶点：A, B, C, D, E
边及权值：(A, B, 1), (A, C, 3), (B, C, 2), (B, D, 4), (C, D, 5), (D, E, 6)
步骤：
1. 按权值排序边：(A, B, 1), (B, C, 2), (A, C, 3), (B, D, 4), (C, D, 5), (D, E, 6)。
2. 依次选择边，确保不形成环：
- 选择(A, B, 1)，加入生成树。
- 选择(B, C, 2)，加入生成树。
- 跳过(A, C, 3)（A和C已连通）。
- 选择(B, D, 4)，加入生成树。
- 跳过(C, D, 5)（C和D已连通）。
- 选择(D, E, 6)，加入生成树。
结果：生成树包含边(A, B, 1), (B, C, 2), (B, D, 4), (D, E, 6)，总权值为13。
二、Prim算法
1. 算法思想
Prim算法也是一种贪心算法，其核心思想是从一个初始顶点开始，逐步扩展生成树，每次选择一条权值最小的边，将新的顶点加入生成树，直到包含所有顶点。
2. 算法步骤
1. 初始化：
- 选择任意一个顶点作为起始点，加入生成树集合T。
- 初始化一个数组key[]，记录每个顶点到生成树的最小边权值（初始为无穷大，起始点除外）。
- 初始化一个数组mstSet[]，标记顶点是否已加入生成树。
2. 构建生成树：
- 重复以下步骤，直到所有顶点都加入生成树：
1. 从mstSet[]为false的顶点中，选择key[]值最小的顶点u。
2. 将u加入生成树集合T，并标记mstSet[u]为true。
3. 更新u的邻接顶点的key[]值：如果u到邻接顶点v的边权值小于key[v]，则更新key[v]为该边权值。
3. 关键点
- 优先队列优化：使用最小堆或优先队列来高效选择key[]值最小的顶点，时间复杂度可降低至O(E log V)（V为顶点数）。
- 时间复杂度：邻接矩阵实现为O(V^2)，邻接表+优先队列实现为O(E log V)。
4. 示例
假设有以下图（与Kruskal示例相同）：
顶点：A, B, C, D, E
边及权值：(A, B, 1), (A, C, 3), (B, C, 2), (B, D, 4), (C, D, 5), (D, E, 6)
步骤（以A为起始点）：
1. 初始化：key[] = [0, ∞, ∞, ∞, ∞]，mstSet[] = [false, false, false, false, false]。
2. 选择A，加入生成树，更新邻接顶点：
- key[B] = 1，key[C] = 3。
3. 选择B（key[]最小），加入生成树，更新邻接顶点：
- key[C] = 2（更新），key[D] = 4。
4. 选择C（key[]最小），加入生成树，更新邻接顶点：
- key[D]保持4（不更新）。
5. 选择D（key[]最小），加入生成树，更新邻接顶点：
- key[E] = 6。
6. 选择E（key[]最小），加入生成树。
结果：生成树包含边(A, B, 1), (B, C, 2), (B, D, 4), (D, E, 6)，总权值为13。
三、Kruskal与Prim算法的比较
| 特性 | Kruskal算法 | Prim算法 |
|------------------|----------------------------------|----------------------------------|
| 核心思想 | 从小到大选择边，避免形成环 | 从一个顶点开始，逐步扩展生成树 |
| 适用场景 | 边稀疏的图（E << V^2） | 边密集的图（E ≈ V^2） |
| 时间复杂度 | O(E log E)（排序+并查集） | O(V^2)（邻接矩阵）或O(E log V)（邻接表+优先队列） |
| 空间复杂度 | 较低（仅需存储边和并查集） | 较高（需存储key[]和mstSet[]）|
| 实现难度 | 较低（排序+并查集） | 较高（需维护优先队列） |
四、
- Kruskal算法更适合边稀疏的图，其实现简单，依赖并查集高效判断连通性。
- Prim算法更适合边密集的图，尤其是当图以邻接矩阵表示时，可直接通过索引访问邻接顶点。
- 选择建议：
- 若图的边数远小于顶点数的平方（
E << V^2），优先选择Kruskal算法。 - 若图的边数接近顶点数的平方（
E ≈ V^2），优先选择Prim算法（邻接矩阵实现）。
- 若图的边数远小于顶点数的平方（
通过理解两种算法的核心思想和实现细节，可以根据具体问题灵活选择合适的算法。
（本文地址：https://www.nzw6.com/6296.html）
