最小生成树——Kruskal与Prim
较难4语言版本：C++
概述：最小生成树就像是给所有城市装水管，用最少的管道把所有路口都连接起来，Kruskal和Prim是两位不同的“管道工”。
最小生成树算法详解：Kruskal与Prim
想象你要为学校里的5个科学实验室搭建一个局域网，让每间实验室都能互相通信。你手头有若干根网线（每根连接两个实验室），但每根网线长度不同，价格也不同（长度越长越贵）。你希望用最少的网线总长度把所有实验室连起来（不一定要每对直接相连，只要通过其他实验室中转就行）。这个问题就是典型的 最小生成树（Minimum Spanning Tree, MST）问题：在一个连通无向图中，找出一棵包含所有顶点、且所有边权之和最小的树（边数为顶点数-1）。
最小生成树有很多实际应用：城市铺天然气管道、电路布线、网络组播树等等。下面我们介绍两种最经典的算法——Kruskal和Prim，它们就像是两位不同风格的“管道工”，都能又快又好地完成任务。
什么是生成树和最小生成树？
- 生成树：一个图如果含有全部 n 个顶点，并且恰好有 n-1 条边，而且这些边不形成环（即是一棵树），那么它就是原图的一棵生成树。
- 最小生成树：在所有可能的生成树中，边权总和最小的那棵（注意：可能不止一棵）。
生活例子：假设有5个小区（顶点），它们之间修路的价格（边权）如下：
- 0-1: 2万元
- 0-3: 6万元
- 1-2: 3万元
- 1-3: 8万元
- 1-4: 5万元
- 2-4: 7万元
- 3-4: 9万元
我们要选5-1=4条路，使得所有小区连通且总价最低。这就是接下来的算法要解决的问题。
Kruskal算法：贪心选边，并查集防环
核心思想
Kruskal管道工的做法是：先把所有边按长度从小到大排序，然后从最短的边开始，只要这条边不会形成环，就把它加入管道网络。怎么判断会不会形成环？用“并查集”工具！只要边连接的两个顶点还没连通（即不在同一个集合里），就可以加入。一直选到 n-1 条边为止。
并查集快速入门
并查集是一种高效判断两个元素是否属于同一集合的数据结构，支持两个操作：
find(x)：找到 x 所在集合的代表元素（根），同时进行路径压缩，让后续查找更快。unite(x, y)：合并 x 和 y 所在的两个集合。
路径压缩的递归写法：
int find(int x) {
if (parent[x] == x) return x; // 自己是根
return parent[x] = find(parent[x]); // 路径压缩：直接挂到根
}
Kruskal算法步骤（拿上面5个小区的例子）
- 将所有边按价格排序（价格已经从小到大）：
- (0,1,2), (1,2,3), (0,3,6), (1,4,5), (2,4,7), (1,3,8), (3,4,9)
- 初始化并查集，每个小区各自成一个集合。
- 从小到大依次考虑每条边：
- 边(0,1,2)：0和1在不同集合→加入，合并{0,1}，总价=2。
- 边(1,2,3)：1和2在不同集合→加入，合并{0,1,2}，总价=5。
- 边(0,3,6)：0和3在不同集合→加入，合并{0,1,2,3}，总价=11。
- 边(1,4,5)：1和4在不同集合→加入，合并所有，总价=16。此时已选4条边，停止。 最终得到最小生成树总价16，选择的边是：(0,1,2)、(1,2,3)、(0,3,6)、(1,4,5)。
Kruskal完整C++代码（带详细注释）
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, w; // u:起点, v:终点, w:权值
};
// ---------- 并查集 ----------
int parent[100]; // 存储每个顶点的父节点
int find(int x) {
if (parent[x] == x) return x; // 自己是根，返回
return parent[x] = find(parent[x]); // 路径压缩，直接挂到根
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x != y) parent[x] = y; // 将x的根挂到y的根下
}
int main() {
int n = 5; // 房子数量（顶点数）
// 所有可能的管道及其长度
vector<Edge> edges = {
{0,1,2}, {0,3,6}, {1,2,3}, {1,3,8}, {1,4,5}, {2,4,7}, {3,4,9}
};
// 1. 按边长从小到大排序（重载比较函数）
sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
return a.w < b.w;
});
// 2. 初始化并查集：每个顶点自己单独一个集合
for (int i = 0; i < n; ++i) parent[i] = i;
int total = 0; // 最小生成树总权值
vector<Edge> mst; // 存放选中的边
// 3. 遍历所有边，贪心选择
for (const Edge& e : edges) {
if (find(e.u) != find(e.v)) { // 如果u和v尚未连通
unite(e.u, e.v); // 合并两个集合
total += e.w; // 累加权值
mst.push_back(e); // 记录这条边
}
}
// 输出结果
cout << "最小生成树的总长度: " << total << "\n所用道路:\n";
for (const Edge& e : mst) {
cout << e.u << " - " << e.v << " 长度: " << e.w << "\n";
}
return 0;
}
常见错误与注意事项（Kruskal）
- 并查集忘记初始化：使用前一定要让每个元素的父节点指向自己。
- 路径压缩写错：
parent[x] = find(parent[x])而不是直接find(parent[x])，否则每次查找都会退化成单链。 - 排序后边数不足 n-1：如果图本身不连通，选不到 n-1 条边，说明图没有最小生成树（此时需要额外判断）。
- 权值相同时的处理：Kruskal 可以任意选择，不影响总权值，但要注意不能形成环。
Prim算法：从起点生长，每次加最近点
核心思想
Prim管道工的做法则不同：随手选一个房子作为起点，然后看看从当前已连通的房子出发，哪条待选的边最短，就把那个新房子和那条边加上，直到所有房子都连上。就像往锅里下饺子，从第一个开始，每次加一个距离最近的。
算法步骤（同样用上面例子）
- 起点任选，比如顶点0。初始化一个集合S={0}，一个数组dist记录每个顶点到S的最短距离（初始时dist[0]=0，其他设为无穷大）。
- 循环 n-1 次：
- 在S外找一个离S最近的顶点v（即dist[v]最小）。
- 把v加入S，并将连接v的那条边加入生成树。
- 用v更新其他不在S中的顶点的dist值（如果边(v, x)的权值小于当前的dist[x]）。
- 最终得到生成树。
用优先队列（堆）优化Prim
朴素Prim每次扫描所有顶点找最小dist，复杂度O(n²)。用优先队列可以将复杂度降到O(m log n)，适合稀疏图。
优先队列版本Prim代码（带详细注释）：
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int MAXN = 100; // 最大顶点数
vector<pair<int,int>> graph[MAXN]; // 邻接表: graph[u] = {(v, w), ...}
bool visited[MAXN]; // 标记顶点是否已在树中
int dist[MAXN]; // 顶点到当前树的最短距离
int prim(int start, int n) {
// 初始化
fill(visited, visited + n, false);
fill(dist, dist + n, INT_MAX);
dist[start] = 0;
// 优先队列：存储 (距离, 顶点)，小顶堆
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, start});
int total = 0;
int edges_used = 0; // 已经选中的边数
while (!pq.empty() && edges_used < n) {
auto [d, u] = pq.top(); pq.pop();
if (visited[u]) continue; // 这个顶点已经处理过了
visited[u] = true;
total += d; // 累加边权
edges_used++; // 选中一个顶点（不是边，但顶点数-1后就是边数）
// 遍历u的所有邻居
for (auto [v, w] : graph[u]) {
if (!visited[v] && w < dist[v]) {
dist[v] = w; // 更新最短距离
pq.push({w, v}); // 入队
}
}
}
// 如果最后选中的顶点数不等于n，说明图不连通，不存在最小生成树
if (edges_used < n) return -1; // 返回-1表示失败
return total;
}
int main() {
int n = 5; // 顶点数
// 构建邻接表（与上文相同的图）
vector<Edge> edges = {
{0,1,2}, {0,3,6}, {1,2,3}, {1,3,8}, {1,4,5}, {2,4,7}, {3,4,9}
};
for (auto e : edges) {
graph[e.u].push_back({e.v, e.w});
graph[e.v].push_back({e.u, e.w}); // 无向图
}
int result = prim(0, n);
if (result == -1) {
cout << "图不连通，无法形成最小生成树" << endl;
} else {
cout << "Prim算法得到的最小生成树总长度: " << result << endl;
}
return 0;
}
常见错误与注意事项（Prim）
- 优先队列中可能包含过时的距离：因为更新dist后，旧的(dist, v)对还留在队列里。所以弹出时要检查
visited[u]，忽略已处理的顶点。 - 忘记处理不连通情况：如果图不连通，最后
edges_used会小于n，要返回错误标识。 - 邻接表要建无向图：必须把边双向加入，否则无法搜索到所有邻居。
- dist数组初始化为INF：要包含头文件
<climits>并使用INT_MAX。
Kruskal与Prim对比
| 算法 | 思想 | 数据结构 | 时间复杂度 | 适用场景 |
|---|---|---|---|---|
| Kruskal | 按边选，避环 | 边集 + 并查集 | O(m log m) | 稀疏图（边数少） |
| Prim（堆优化） | 按点扩，贪心 | 邻接表 + 优先队列 | O((n+m)log n) | 稠密图（边数多） |
选择建议：如果图较稀疏（边数≈顶点数），Kruskal更容易实现；如果图稠密（边数接近n²），Prim更高效（用邻接矩阵的朴素Prim是O(n²)）。
完整可运行代码（两种算法合二为一）
下面的程序读入顶点数和边数，然后测试同一个图，分别输出Kruskal和Prim的结果。代码已包含完善注释和错误处理。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 边结构体
struct Edge {
int u, v, w;
};
// ---------- 并查集（用于Kruskal） ----------
int parent[100];
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x != y) parent[x] = y;
}
// Kruskal算法
int kruskal(int n, vector<Edge>& edges) {
// 按权排序
sort(edges.begin(), edges.end(), [](Edge a, Edge b){ return a.w < b.w; });
// 初始化并查集
for (int i = 0; i < n; ++i) parent[i] = i;
int total = 0, cnt = 0; // cnt记录已选边数
for (const Edge& e : edges) {
if (find(e.u) != find(e.v)) {
unite(e.u, e.v);
total += e.w;
cnt++;
if (cnt == n-1) break; // 已选够n-1条边
}
}
return (cnt == n-1) ? total : -1;
}
// ---------- Prim算法（堆优化） ----------
vector<pair<int,int>> graph[100];
bool visited[100];
int dist[100];
int prim(int start, int n) {
fill(visited, visited + n, false);
fill(dist, dist + n, INT_MAX);
dist[start] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, start});
int total = 0, cnt = 0;
while (!pq.empty() && cnt < n) {
auto [d, u] = pq.top(); pq.pop();
if (visited[u]) continue;
visited[u] = true;
total += d;
cnt++;
for (auto [v, w] : graph[u]) {
if (!visited[v] && w < dist[v]) {
dist[v] = w;
pq.push({w, v});
}
}
}
return (cnt == n) ? total : -1;
}
int main() {
// 示例：5个顶点，7条边
int n = 5;
vector<Edge> edges = {
{0,1,2}, {0,3,6}, {1,2,3}, {1,3,8}, {1,4,5}, {2,4,7}, {3,4,9}
};
// 为Prim构建邻接表
for (int i = 0; i < n; ++i) graph[i].clear();
for (const Edge& e : edges) {
graph[e.u].push_back({e.v, e.w});
graph[e.v].push_back({e.u, e.w});
}
// 分别运行
int result1 = kruskal(n, edges);
int result2 = prim(0, n);
cout << "Kruskal最小生成树总长: " << (result1 == -1 ? "无法生成" : to_string(result1)) << endl;
cout << "Prim最小生成树总长: " << (result2 == -1 ? "无法生成" : to_string(result2)) << endl;
return 0;
}
输出：
Kruskal最小生成树总长: 16
Prim最小生成树总长: 16
常见错误综合提醒
- 图不连通：两种算法都会失败，一定要在代码中判断并处理。
- 边权可能为负数：最小生成树可以在负权边存在时正常工作（但Prim算法的堆优化版本依然正确），不过注意负权边可能导致总权更小，算法同样适用。
- 顶点编号从0还是1开始：代码中统一从0开始，如果题目从1编号，需要适当调整数组大小或减1处理。
- 使用优先级队列的“过时”元素：Prim中如果不加
visited判断，可能把一个顶点多次更新加入，导致逻辑错误或超时（但通常无害，只是多了一些无效弹出）。 - 并查集路径压缩写成了
find(parent[x])而不是赋值：会导致每次查找都递归，效率低且可能栈溢出。
相关知识点指引
- 次小生成树：在最小生成树基础上，求权值第二小的生成树，通常用 Kruskal 结合 LCA 或替换法。
- 瓶颈生成树：最小化生成树中最大边的权值，与最小生成树的关系密切（最小生成树一定是瓶颈生成树）。
- 最短路径 vs 最小生成树：最短路径解决“从一个点到另一个点的最短路径”，而最小生成树解决“连接所有点总长度最小”，两个问题不同，算法也不同（Dijkstra vs Prim/Kruskal）。
- 图的存储方式：邻接矩阵适合稠密图，邻接表适合稀疏图；边集数组适合Kruskal。
掌握了 Kruskal 和 Prim，你就拥有了解决“连接一切”问题的两把利器。快去试试用它们来解决你自己生活中的“铺管道”问题吧！
例题精讲
1单选题
在Kruskal算法中，若使用并查集（带路径压缩和按秩合并），则find操作的均摊时间复杂度接近（ ）。
AO(1)
BO(log n)
CO(n)
DO(α(n))
2单选题
对于一个边数远大于顶点数（例如E≈V²）的稠密图，使用哪种算法求最小生成树通常更高效？
AKruskal算法
BPrim算法（使用二叉堆）
C两者效率一样
D无法确定
3判断题
在Kruskal算法中，使用并查集检查边的两个端点是否属于同一集合，若属于同一集合则跳过，否则加入该边并合并集合。这一过程能够确保不会形成环。
4判断题
使用二叉堆优化的Prim算法，初始化时将起点距离设为0，其余顶点距离设为无穷大，并将所有顶点插入堆中。之后每次取出堆顶，更新邻接点的距离，若新距离更小则调整堆。该算法的时间复杂度为O(V log V + E log V)。
5填空题
下面是Kruskal算法求最小生成树的核心代码片段，请填写if语句中的条件，使得算法正确判断是否应加入当前边。
int kruskal() {
sort(edges, edges+m, cmp);
int sum=0, cnt=0;
for(int i=0;i<m;i++) {
int u=edges[i].u, v=edges[i].v, w=edges[i].w;
if( ___ ) {
unionSet(u,v);
sum += w;
if(++cnt == n-1) break;
}
}
return sum;
}