Appearance
Kruskal 算法
为什么需要Kruskal 算法
最小生成树（MST）是图论中的经典问题：给定一个带权无向连通图，找到一棵包含所有顶点的树，使得边权之和最小。
Kruskal 算法是求解最小生成树的两大经典算法之一。它从边的角度出发，按权值从小到大贪心选边，特别适合处理边稀疏的图。408 考研中，Kruskal 与 Prim 算法常以对比形式出题，是图论章节的核心考点。
核心思想
Kruskal 算法的核心策略是按边贪心：
- 对所有边按权值升序排序
- 依次选择权值最小的边，若该边加入后不会形成回路，则将其纳入生成树
- 利用并查集判断回路：若一条边的两个端点已属于同一连通分量，则加入该边会形成回路，应跳过
- 重复上述过程，直到选够 n-1 条边（n 为顶点数），算法结束
算法过程示意：
原始边集（按权值排序）:
(A,B,1) → (C,D,2) → (A,C,3) → (B,D,4) → (B,C,5)
逐步选边：
第1步: 选 (A,B,1) ✓ 不构成回路
第2步: 选 (C,D,2) ✓ 不构成回路
第3步: 选 (A,C,3) ✓ 不构成回路 → 已选 n-1=3 条边，算法结束交互可视化
通过下方的交互动画，你可以逐步观察Kruskal 算法的执行过程：
操作详解
算法思路
- 将图中所有边按权值升序排序
- 初始化并查集，每个顶点各自为一个独立集合
- 依次遍历排序后的边 (u, v, w)：
- 若 u 和 v 不在同一集合（即加入不会成环），则选中该边，合并两个集合
- 若 u 和 v 在同一集合，跳过该边
- 当选中的边数达到 n-1 时，最小生成树构建完成
执行过程详解
以下为 Kruskal 算法的 C 语言实现：
c
#include <stdio.h>
#include <stdlib.h>
#define MAXE 1000 // 最大边数
#define MAXV 100 // 最大顶点数
typedef struct {
int u, v; // 边的两个端点
int w; // 边的权值
} Edge;
Edge edges[MAXE]; // 边集数组
int parent[MAXV]; // 并查集父节点数组
int rank_[MAXV]; // 并查集秩（用于按秩合并）
// 比较函数，用于 qsort 按权值升序排序
int cmp(const void *a, const void *b) {
return ((Edge *)a)->w - ((Edge *)b)->w;
}
// 并查集：查找根节点（带路径压缩）
int Find(int x) {
if (parent[x] != x)
parent[x] = Find(parent[x]);
return parent[x];
}
// 并查集：合并两个集合（按秩合并）
void Union(int x, int y) {
int rx = Find(x), ry = Find(y);
if (rx == ry) return;
if (rank_[rx] < rank_[ry])
parent[rx] = ry;
else if (rank_[rx] > rank_[ry])
parent[ry] = rx;
else {
parent[ry] = rx;
rank_[rx]++;
}
}
// Kruskal 算法
int Kruskal(int n, int m) { // n: 顶点数, m: 边数
int i, cnt = 0, totalW = 0;
// 1. 按权值排序所有边
qsort(edges, m, sizeof(Edge), cmp);
// 2. 初始化并查集
for (i = 0; i < n; i++) {
parent[i] = i;
rank_[i] = 0;
}
// 3. 贪心选边
for (i = 0; i < m && cnt < n - 1; i++) {
int u = edges[i].u, v = edges[i].v;
if (Find(u) != Find(v)) { // 不在同一集合，不会成环
Union(u, v); // 合并
totalW += edges[i].w; // 累加权值
cnt++; // 已选边数 +1
}
}
if (cnt < n - 1) return -1; // 图不连通，无法生成 MST
return totalW;
}并查集辅助
并查集（Union-Find）是 Kruskal 算法高效判环的关键数据结构。
核心操作：
| 操作 | 功能 | 优化策略 |
|---|---|---|
| Find(x) | 查找 x 所在集合的根 | 路径压缩：查找时将沿途节点直接挂到根上 |
| Union(x, y) | 合并 x 和 y 所在的集合 | 按秩合并：将矮树挂到高树上，控制树高 |
为什么用并查集判环？ 若边 (u, v) 的两个端点已在同一集合中，说明 u 到 v 之间已存在路径，再加入该边必然形成回路。
经过路径压缩和按秩合并优化后，单次 Find/Union 操作的均摊时间复杂度接近 O(α(n))，其中 α 为反阿克曼函数，实际可视为常数。
复杂度分析
算法各步骤的时间消耗：
| 步骤 | 时间复杂度 | 说明 |
|---|---|---|
| 边排序 | O(ElogE) | 快排 / 归并排序 |
| 初始化并查集 | O(V) | 每个顶点初始化为独立集合 |
| 遍历边 + 并查集操作 | O(E·α(V)) | α(V) 近似为常数 |
| 总计 | O(ElogE) | 瓶颈在排序步骤 |
注：由于 E ≤ V(V-1)/2，所以 O(ElogE) = O(ElogV)，两种写法等价。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(ElogE) | 排序为主要开销 |
| 空间复杂度 | O(V+E) | 边集数组 O(E) + 并查集 O(V) |
适用场景：Kruskal 算法的时间复杂度只与边数 E 相关，因此特别适合边稀疏图（E 远小于 V²）。
Kruskal vs Prim 对比：
| 对比项 | Kruskal | Prim |
|---|---|---|
| 策略 | 按边贪心 | 按顶点扩展 |
| 数据结构 | 并查集 | 优先队列 / 邻接矩阵 |
| 时间复杂度 | O(ElogE) | O(V²) 或 O(ElogV) |
| 适用图 | 边稀疏图 | 边稠密图 |
| 边的存储 | 边集数组 | 邻接矩阵 / 邻接表 |
考研高频考点
- ⭐ Kruskal 算法的执行过程手动模拟（选择题/应用题高频）
- ⭐ Kruskal vs Prim 的适用场景对比（简答题必考）
- ⭐ 并查集的 Find 和 Union 操作原理（常结合 Kruskal 考察）
- ⭐ 时间复杂度 O(ElogE) 的推导及瓶颈分析
- 最小生成树的性质：n 个顶点恰好 n-1 条边、权值之和最小、不唯一（当存在等权边时）
- 判断给定图是否存在最小生成树（图必须连通）