Kruskal 算法

2026 大纲 五（四）图的基本应用 1. 最小（代价）生成树 · 加边法（加点法、以及 MST 的定义与割性质见《Prim》）。

换个贪法：不盯顶点，盯边

Prim 的贪心对象是顶点——每轮把离树最近的那个顶点拉进来。Kruskal 换了个角度：直接盯边。

做法一句话：把所有边按权值升序排队，依次考察，不成环就收下，收够 $n-1$ 条结束。

这一换带来一个重要的结构差别：

🔴 Kruskal 的中间状态是森林——已选的边可能分散在好几个互不相连的连通块里，直到最后一条边才并成一整棵树。而 Prim 的中间状态始终是一棵连通的树。

这个差别不只是观感问题：正因为中间是若干互不相连的块，才需要一个数据结构来回答"这两个顶点现在连通了吗"——这就是并查集在这里出现的理由。

先动手看一眼

加载可视化中...

盯"当前连通块"那一栏：它一开始是 $n$ 个孤立的块，每收下一条边就少一块，收够 $n-1$ 条时恰好剩一块。这个计数关系就是算法的终止条件。

判环 = 判连通，所以用并查集

为什么"不成环"可以换成"两端不连通"？因为树上任意两点之间的路径唯一：

加入边 $(u,v)$ 会成环 $⟺$ $u$ 与 $v$ 在已选边构成的森林中已经连通。

于是判环变成了三个并查集操作：parent[i]=i 初始化、Find(u)==Find(v) 判、Union(u,v) 合并。

typedef struct { int u, v, w; } Edge;   // 边的两个端点与权值

Edge edges[MAXE];
int parent[MAXV], rank_[MAXV];

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]++; }   // 只有两棵等高树合并，树高才 +1
}

// n 个顶点、m 条边，返回 MST 总权值；图不连通返回 -1
int Kruskal(int n, int m) {
    int i, cnt = 0, totalW = 0;
    qsort(edges, m, sizeof(Edge), cmp);              // ① 排序——整个算法的瓶颈
    for (i = 0; i < n; i++) { parent[i] = i; rank_[i] = 0; }   // ② 初始化并查集

    // ③ 贪心选边。两个终止条件缺一不可：
    //    cnt < n-1 让选够就提前停；i < m 保证边用完也能退出
    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++;
        }
        // else：丢弃。由环性质，它是所构成回路上权值最大的边，弃之无害
    }
    if (cnt < n - 1) return -1;          // 凑不够 n-1 条 → 图不连通
    return totalW;
}

并查集加了路径压缩和按秩合并后，单次操作均摊近似 $O(\alpha (n))$（$\alpha$ 是反阿克曼函数，现实规模下不超过 4，可视为常数）。详见并查集。

教材里还有一种更朴素的判环写法：用 Vexset[] 直接给每个顶点标"所属连通分量编号"，合并时把编号为 vs2 的全部改成 vs1。概念上更直白，但每次合并要扫一遍 $n$ 个顶点，合并总代价升到 $O(ne)$。用并查集把它降到近似常数，才使得排序成为唯一的瓶颈。

顺带白拿一个功能：边考察完了仍有 cnt < n-1，就说明图不连通，不必额外跑连通性检查（Prim 那边要靠显式判 k == -1）。

为什么丢弃是安全的：环性质

收边一侧的正确性由割性质保证（在《Prim》那篇证过）。丢边一侧靠的是另一条：

🔴 环性质：设 $C$ 是图中任一回路，$f$ 是 $C$ 上权值最大且严格大于其他边的那条，则任何 MST 都不含 $f$。

证明（反证）。设某棵 MST $T$ 含 $f$。从 $T$ 中删去 $f$，$T$ 被分成两个连通块，顶点集分成 $U$ 与 $V-U$，且 $f$ 跨越这个划分。回路 $C$ 上除 $f$ 之外必然还有另一条跨越边 $g$（回路要从 $U$ 出去再回来，至少跨两次）。把 $g$ 加回来即得另一棵生成树 $T^{\prime }$，且

$$w(T^{\prime })=w(T)-w(f)+w(g)<w(T)$$

与 $T$ 是最小生成树矛盾。∎

Kruskal 正是环性质的直接执行：遇到一条两端已连通的边时，它与已选路径恰好构成一个回路；而边是按权值升序考察的，所以这条边一定是该回路上权值最大（或并列最大）的那条，丢弃安全。

顺便回答一个常见的疑虑——"先选了小边，会不会把后路堵死？" 不会。被丢弃的边一定是某个回路上的最大边，而回路上的最大边必不属于任何 MST，丢了不损失最优解。

手算这道题的唯一诀窍：严格按升序

真题里出现过的问法是"加入到最小生成树中的边依次是"，四个选项给的是四种不同的加边次序。这类题答错基本只有一个原因：没有严格按权值升序排队。

正确的手算流程只有三步，别跳：

1. 把所有边按权值从小到大列成一行（相同权值的先后无所谓）。
2. 从头逐条考察，只做一个判断：这条边的两端现在连通吗——连通就划掉，不连通就收下并把两块并起来。
3. 收够 $n-1$ 条立刻停，后面的边不必再看。

⚠️ 干扰选项通常是按 Prim 的次序排的——同样的边集、同样的总权值，但顺序不同。所以看清题目问的是哪个算法，Prim 的答案里边是"一条接一条长出去"的，Kruskal 的答案里前几条边往往彼此不相邻。

六顶点无向网的逐条选边推演，以及并查集内部的变化（想手动模拟一遍就展开）

先看一个 4 顶点的最小例子。边集排序后为 $(A,B,1)\to (C,D,2)\to (A,C,3)\to (B,D,4)\to (B,C,5)$：第 1 步选 $(A,B,1)$（$A$、$B$ 原本不连通）；第 2 步选 $(C,D,2)$；第 3 步选 $(A,C,3)$，把 $\{A,B\}$ 与 $\{C,D\}$ 两块合并，已选 $n-1=3$ 条，结束。

下面换成与 Prim 完全相同的那张 6 顶点、10 条边的无向网，以便直接对比两种算法的选边次序：

排序后依次考察（权值相同的边按字典序排，实际实现中任选次序都可以）：

序	边	权	Find(u) 与 Find(v)	决策	考察后的连通块	已选
1	$A-C$	1	不同	选中	{A,C} {B} {D} {E}	1
2	$D-F$	2	不同	选中	{A,C} {B} {E}	2
3	$B-E$	3	不同	选中	{A,C} {B,E}	3
4	$C-F$	4	不同	选中	{A,C,D,F}	4
5	$A-D$	5	相同	丢弃（成环 $A-C-F-D-A$）	不变	4
6	$B-C$	5	不同	选中 → 已选够 5 条，结束		5

结果：5 条边 $(A,C),(D,F),(B,E),(C,F),(B,C)$，总权值 $1+2+3+4+5=\mathbf{15}$。

与 Prim 的对照：Prim 在同一张图上选出的是 $(A,C),(C,F),(F,D),(C,B),(B,E)$——边集完全相同，只是次序不同，总权值也同为 15。这不是巧合，因为这张图的 MST 恰好唯一。另外，Kruskal 在第 3 步时手上有 {A,C}、{B,E}、{D,F} 三棵互不相连的小树，Prim 在任何时刻都只有一棵——这就是"加边法"与"加点法"的实质区别。

并查集内部 parent[] 的逐步变化（把 $A\sim F$ 编号为 $0\sim 5$，初始 parent[i]=i、rank_[i]=0）：

处理的边	Find 结果	Union 动作	parent[]（下标 $ABCDEF$）	rank_ 变化
初始	—	—	$ABCDEF$	全 0
$A-C$	$A\ne C$	秩相等 → $C$ 挂到 $A$，rank_[A]=1	$AB\mathbf{A}DEF$	$A:1$
$D-F$	$D\ne F$	秩相等 → $F$ 挂到 $D$，rank_[D]=1	$ABADE\mathbf{D}$	$D:1$
$B-E$	$B\ne E$	秩相等 → $E$ 挂到 $B$，rank_[B]=1	$ABAD\mathbf{B}D$	$B:1$
$C-F$	$\text{Find}(C)=A$，$\text{Find}(F)=D$，不同	秩相等（都是 1）→ $D$ 挂到 $A$，rank_[A]=2	$ABA\mathbf{A}BD$	$A:2$
$A-D$	$\text{Find}(A)=A$，$\text{Find}(D)=A$，相同	丢弃，parent 不变	$ABAABD$	—
$B-C$	$\text{Find}(B)=B$，$\text{Find}(C)=A$，不同	$\text{rank}[B]=1<\text{rank}[A]=2$ → $B$ 挂到 $A$	$A\mathbf{A}AABD$	不变

两点值得注意：

• 第 4 行的 Find(F)：$F$ 的 parent 是 $D$、$D$ 的 parent 是自己，根是 $D$，这一步走了两级；若树再深一点，路径压缩会把 $F$ 直接改挂到根上，下次查只要一步。
• 第 5 行的丢弃是"免费"的：只做了两次 Find，没有任何写操作。这正是并查集比"每次做一趟 DFS 判连通"高效得多的地方。

最终 parent[] = [A, A, A, A, B, D]，从任何顶点向上追都能到 $A$，说明 6 个顶点已并成一块。

自检：边数 $=5=n-1$ ✓；覆盖全部 6 个顶点 ✓；无回路 ✓；被丢弃的 $A-D$ 确实在已选边构成的回路上 ✓。

复杂度的三段分解与 Prim 的定量比较（要在两者间选型时展开）

步骤	时间复杂度	说明
① 边排序	$O(e\log e)$	用快排 / 归并 / 堆排序，见排序算法比较
② 初始化并查集	$O(n)$	每个顶点各成一块
③ 遍历边 + 并查集操作	$O(e\cdot \alpha (n))\approx O(e)$	每条边最多一次 Find 对 + 一次 Union
总计	$\mathbf{O}\mathbf{(}\mathbf{e}\log \mathbf{e}\mathbf{)}$	瓶颈在排序

写成 $O(e\log n)$ 也对：简单图中 $e\le n(n-1)/2<n^2$，故 $\log e<2\log n$，常数被 $O$ 吸收。

空间 $O(n+e)$：边集数组 $O(e)$ + 并查集 $O(n)$。⚠️ 它需要"边集数组"这种存储形式；题目若给的是邻接矩阵，要先花 $O(n^2)$ 把边抽出来。

图的形态	$e$ 的量级	Prim $O(n^2)$	Kruskal $O(e\log e)$	谁更快
稀疏（如 $e\approx n$）	$n$	$n^2$	$n\log n$	Kruskal
中等（如 $e\approx n\log n$）	$n\log n$	$n^2$	$n{\log }^{2}n$	Kruskal（$n$ 较大时）
稠密（$e\approx n^2/2$）	$n^2$	$n^2$	$n^2\log n$	Prim

既然瓶颈是排序，优化 Kruskal 就要从排序下手——例如边权取值范围很小时改用基数排序。

考点速记

三条结论：

1. 按边贪心 + 并查集判环；收边由割性质保证，丢边由环性质（回路上的最大边必不在 MST 中）保证。
2. $O(e\log e)$，瓶颈是排序，只与边数有关，所以适合稀疏图；稠密图上退化到 $O(n^2\log n)$，不如 Prim。
3. 中间状态是森林（Prim 是一棵树），凑不够 $n-1$ 条边就说明图不连通。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 依次加入 MST 的边：给一张 6 顶点的无向网，问加入的边依次是哪几条。严格按权值升序逐条考察，两端已连通就跳过；干扰选项往往是同一批边按 Prim 的次序排列的。
• Prim 与 Kruskal 第 $k$ 次选边的对比：问"可能是 Kruskal 第 2 次选中、但不是 Prim（从某顶点开始）第 2 次选中的边"。两个算法各跑两步列出候选，再取差集；Prim 的起点由题目指定，换个起点答案就变。
• 枚举全部最经济方案（跨科目大题）：给一张城市光缆费用图，要求给出所有可能的最经济方案并算总费用。同题还会问"该图可采用哪种存储结构"和"求解用什么算法"——存储答邻接矩阵或邻接表（这类题两者都可），算法答 Kruskal 或 Prim。等权边处并列时会产生多个方案，要逐个列全，别只写一个。
• 四个 MST 命题的真伪判断：代价唯一（对）、所有最小权边都在所有 MST 中（错）、Prim 从不同起点结果一定相同（错）、Prim 与 Kruskal 结果总不相同（错）。
• 能不能用来求最短路：作为错误选项出现——即使各边权都为 1，MST 也不是最短路径树。

易错：MST 不唯一，但总权值唯一。 等权边先考察哪一条会影响选出哪一棵 MST，却不影响总权值。所以问"总费用"不必纠结排序次序，问"写出方案"就要把并列造成的多个方案都列出来。

易错：手算时必须严格按权值升序，不能顺着图的画法走。 这是这类题唯一的失分点。

易错：丢弃的边是"两端已连通"的边，不是"看起来会绕圈"的边。 判据是并查集里两个根相不相同，画图时在旁边维护一份连通块清单最稳。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p169，算法 6.9： "可以看出，克鲁斯卡尔算法逐步增加生成树的边，与普里姆算法相比，可称为加边法。 与普里姆算法一样，每次选择最小边时，可能有多条同样权值的边可选，可以任选其一。" 同页给出算法步骤：将边按权值从小到大排序；依次取边 $(v_1,v_2)$， 查 Vexset 中两端所在的连通分量 vs1、vs2， 不等则输出此边并合并两个连通分量，相等则舍去。
• 同书印刷 p170（算法分析）： "对于包含 $e$ 条边的网，上述算法排序时间是 $O(e{\log }_{2}e)$……整个 for 循环的执行时间是 $O(e{\log }_{2}e)$，由此，克鲁斯卡尔算法的时间复杂度为 $O(e{\log }_{2}e)$，与网中的边数有关， 与普里姆算法相比，克鲁斯卡尔算法更适合于求稀疏网的最小生成树。"
• MST 性质（割性质）及其反证法证明见同书印刷 p165–p166，本篇引用自 Prim。

相关知识

Prim 算法（加点法，适合稠密图；MST 定义、割性质、唯一性判据都在那一篇）｜ 并查集（判环的数据结构，路径压缩与按秩合并）｜ 排序算法比较（瓶颈是排序，排序方法直接决定常数）｜ 邻接表（稀疏图的高效存储）｜ 图的基本概念（生成树、连通分量、"$n-1$ 条边"的来历）

相关文章

• 图的基本概念
• 邻接矩阵
• 邻接表
• 十字链表与邻接多重表
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 最小生成树：Prim
• BFS 求无权图最短路径
• Dijkstra 算法
• Floyd 算法
• DAG 描述表达式
• 拓扑排序
• 关键路径

交互体验

前往完整可视化页面 →

真题练习

相关真题（5题）

2023Q62分2020Q72分2018Q4212分2015Q62分2012Q82分