Kruskal 算法

1. 概述与学习目标

1.1 什么是 Kruskal 算法

Kruskal 算法（Kruskal Algorithm）是一种基于贪心策略（Greedy Strategy）的最小生成树（Minimum Spanning Tree, MST）构造算法，由 Joseph B. Kruskal 1956 在《On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem》Proceedings of the American Mathematical Society 7(1):48-50 DOI:10.1090/S0002-9939-1956-0078686-7 提出。该算法与 Prim 1957、Jarník 1930、Borůvka 1926 共同构成 MST 算法家族。

给定连通无向加权图 $G = (V, E, w)$，其中 $|V| = n, |E| = m$，边权函数 $w: E \to \mathbb{R}$，Kruskal 算法在 $O(m \log m)$ 时间、$O(n)$ 空间内求出 $G$ 的一棵最小生成树。算法核心策略：

按边权升序排序，依次考察每条边 $(u, v)$：若加入后不形成环（即 $u, v$ 当前不在同一连通分量），则加入 MST；否则跳过。重复直到选满 $n - 1$ 条边。

环检测借助并查集（Disjoint Set Union, DSU）实现：维护顶点的连通分量归属，每次查询 find(u) != find(v) 即可 $O(\alpha(n))$ 判断。结合 Tarjan 1975 的路径压缩+按秩合并优化，$m$ 次操作总代价 $O(m \cdot \alpha(n)) \approx O(m)$，瓶颈在于初始的边排序 $O(m \log m)$。

最小生成树算法家族层次模型：

              最小生成树 (MST)
                    |
    ┌───────────────┼───────────────┐
Kruskal 1956     Prim 1957       Borůvka 1926
边排序贪心       点扩展贪心       分治合并
O(E log E)       O(V²) / O(E log V)  O(E log V)
稀疏图优         稠密图优         并行友好
并查集           优先队列         分量合并
                    |
                ┌───┴───┐
            Jarník 1930  Karger-Klein-Tarjan 1995
            Prim 前身     随机化线性 O(E) 期望

1.2 算法在图算法家族中的位置

Kruskal 算法处于图算法的三大交叉点：

1. 贪心算法家族：与 Huffman 编码、Dijkstra 单源最短路、活动选择问题同为经典的贪心范式范例，依赖贪心选择性质与最优子结构
2. 生成树家族：与 Prim 1957（加点法）、Borůvka 1926（分治法）、Chazelle 2000（$O(E \alpha)$ 软堆）、Karger-Klein-Tarjan 1995（随机化线性）共同构成 MST 算法体系
3. 并查集应用家族：与连通分量统计、Tarjan 离线 LCA、等价类划分同为 DSU 的标志性应用场景

1.3 适用场景与限制

适用场景：

• 稀疏图：$|E| \approx |V|$ 时，$O(E \log E) \approx O(V \log V)$ 远优于 Prim 的 $O(V^2)$
• 边权分布均匀：边权值分布较均匀时，排序后能快速构造 MST
• 最小生成森林：图不连通时，Kruskal 自然生成最小生成森林（无需修改算法）
• 流式处理：边按权值流式到达时，可结合外部排序处理大规模图
• 离线算法：一次性计算后多次查询 MST 边集合

限制场景：

• 稠密图：$|E| \approx |V|^2$ 时，$O(E \log E) = O(V^2 \log V)$ 不如 Prim 邻接矩阵 $O(V^2)$
• 动态图：图边权频繁变化时，每次需 $O(E \log E)$ 重新计算
• 在线查询：Kruskal 不能高效处理”加入/删除边后 MST 如何变化”的动态问题
• 大规模外部存储：当 $E$ 远大于内存时，排序成为瓶颈，需借助外部排序或 Borůvka 算法

1.4 学习目标

完成本章学习后，读者应能够：

1. 记忆（Remember）：Kruskal 算法的贪心策略、时间复杂度 $O(E \log E)$、空间复杂度 $O(V)$，并查集路径压缩+按秩合并的均摊 $O(\alpha(n))$ 复杂度
2. 理解（Understand）：Kruskal 1956、Prim 1957、Jarník 1930、Borůvka 1926 四位独立发现者的历史脉络，以及切割性质、回路性质、贪心选择性质的数学含义
3. 应用（Apply）：编写正确的 Kruskal 多语言实现（Python/C++/Java），处理最小生成森林、最大生成树、次小生成树等变体
4. 分析（Analyze）：Kruskal 算法的贪心选择性质证明、最优子结构证明、为何排序是瓶颈、为何并查集优化能将环检测降至均摊 $O(\alpha(n))$
5. 评估（Evaluate）：在稀疏图/稠密图/动态图/并行化维度上对比 Kruskal 与 Prim、Borůvka 的选型决策
6. 对比（Compare）：Kruskal 加边法、Prim 加点法、Borůvka 分治法在算法设计思想、数据结构依赖、稀疏/稠密图性能、并行可扩展性维度的差异
7. 创造（Create）：设计基于 Kruskal 的工业级方案，如电力网络最小成本规划、单链聚类（Single-Linkage Clustering）、TSP 2-近似算法、图像分割最小生成树

2. 历史动机与演进

2.1 1926 年 Borůvka：MST 问题的诞生

最小生成树问题的最早形式化可追溯至 1926 年，捷克数学家 Otakar Borůvka（1899-1995）在论文《O jistém problému minimálním》（Práce Moravské Přírodovědecké Společnosti 3:37-58）中提出。Borůvka 的原始动机是摩拉维亚地区电网规划：在第一次世界大战后，捷克斯洛伐克正在快速工业化，需要以最低成本将各城镇连接到电网。Borůvka 形式化的问题是：

给定 $n$ 个城镇与城镇间建造电力线路的成本，求一个连接方案使得所有城镇通电，且总成本最小。

Borůvka 算法的核心思想是同步分治：每一轮，每个连通分量独立地选择”通往其他分量的最小权边”，所有分量同步合并。算法在 $O(\log V)$ 轮内终止，每轮 $O(E)$ 工作，总复杂度 $O(E \log V)$。Borůvka 算法的并行友好性使其在 20 世纪 80 年代并行计算兴起后重新受到关注。

教学提示：Borůvka 1926 论文用法语和捷克语写成，长期被英语世界忽视。直到 Graham-Hell 1985《On the history of the minimum spanning tree problem》Annals of the History of Computing 7(1):43-57 DOI:10.1109/MAHC.1985.10011 系统梳理 MST 历史后，Borůvka 的开创性贡献才被广泛认可。

2.2 1930 年 Jarník：Prim 算法的前身

Vojtěch Jarník（1897-1970）是捷克数学家，查理大学（Charles University in Prague）教授。1930 年他在《O jistém problému minimálním》（Práce Moravské Přírodovědecké Společnosti 6:57-63）中提出了一种基于加点扩展的 MST 算法，比 Prim 1957 早 27 年。

Jarník 算法核心思想：

1. 从任意顶点 $r$ 开始，初始化 $T = \{r\}$
2. 每一步选择”连接 $T$ 与 $V - T$ 的最小权边”，将其加入 $T$
3. 重复直到 $T = V$

这正是今天所称的 Prim 算法。Jarník 论文同样用捷克语写成，长期被忽视。直到 1957 年 Prim 重新发现，并在 Bell System Technical Journal 36(6):1389-1401 DOI:10.1002/j.1538-7305.1957.tb01515.x 上发表《Shortest connection networks and some generalizations》，该算法才被广泛传播。Jarník-Prim 算法这一称呼正是对 Jarník 优先权的认可。

教学提示：历史上 MST 算法的多次独立发现反映了一个深刻现象：好的算法思想常常被多次重新发现。Graham-Hell 1985 的历史综述统计了至少 6 次 MST 算法的独立发现，包括 Borůvka 1926、Jarník 1930、Kruskal 1956、Prim 1957、Loberman-Weinberger 1957、Kalaba 1960。

2.3 1956 年 Kruskal：贪心加边法的诞生

Joseph Bernard Kruskal（1928-2010）是美国数学家，1954 年在普林斯顿大学获得博士学位，导师是 Roger Lyndon。他的博士论文研究多维标度法（multidimensional scaling），后来在 Bell 实验室和密歇根大学工作。

1956 年，Kruskal 在《On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem》Proceedings of the American Mathematical Society 7(1):48-50 DOI:10.1090/S0002-9939-1956-0078686-7 发表论文。论文实际上给出了两个算法：

• 算法 1（今天所称的 Kruskal 算法）：按边权升序加入不形成环的边
• 算法 2：从某个顶点出发，每步加入”连接已选顶点与未选顶点的最小权边”（即后来 Prim 1957 重新发现的算法）

Kruskal 论文的另一个贡献是指出 MST 与 TSP（旅行商问题）的关系：MST 中序遍历给出 TSP 的一个 2-近似解，即 $w(\text{TSP tour}) \leq 2 \cdot w(\text{OPT})$。这一结论后来被 Christofides 1976 改进为 1.5-近似。

Kruskal 论文标题中的 “Traveling Salesman Problem” 暗示了他研究 MST 的原始动机：作为 TSP 的下界估计。MST 权值是 TSP 最优解权值的下界（删除 TSP 环上任一边得到一棵生成树），故 $\text{OPT}_\text{TSP} \geq w(\text{MST})$。

2.4 1957 年 Prim：Bell 实验室的重新发现

Robert Clay Prim（1921-2021）是美国数学家与计算机科学家，1957 年任职于 Bell Telephone Laboratories。他在《Shortest connection networks and some generalizations》Bell System Technical Journal 36(6):1389-1401 DOI:10.1002/j.1538-7305.1957.tb01515.x 独立重新发现了 Jarník 1930 的算法。

Prim 的贡献在于：

1. 将算法用英语世界可访问的形式重新表述
2. 推广至”最短连接网络”的一般化形式
3. 给出了基于优先队列（priority queue）的高效实现，复杂度 $O(V^2)$（邻接矩阵）或 $O(E \log V)$（二叉堆+邻接表）

Prim 在 Bell 实验室的研究背景包括电话网络设计与军事通信系统，这与 Borůvka 1926 的电网规划动机一脉相承。

2.5 1964-1975 年并查集优化：从 Galler-Fischer 到 Tarjan

Kruskal 算法的早期实现使用朴素连通分量数组，每次合并 $O(V)$，总复杂度 $O(E \cdot V)$。1964 年 Bernard A. Galler 与 Michael J. Fischer 在《An improved equivalence algorithm》Communications of the ACM 7(5):301-303 DOI:10.1145/364099.364331 提出树形并查集，将合并降至 $O(1)$，但查找最坏 $O(V)$。

1973 年 Hopcroft-Ullman 引入路径压缩，将总复杂度降至 $O(m \log^* n)$。1975 年 Robert Endre Tarjan 在《Efficiency of a good but not linear set union algorithm》Journal of the ACM 22(2):215-225 DOI:10.1145/321879.321884 给出严格证明：路径压缩+按秩合并的总复杂度为 $\Theta(m \cdot \alpha(n))$，且这是基于指针比较的 DSU 的下界。

这一结果使得 Kruskal 算法的瓶颈从环检测转移到边排序：$O(E \log E)$ 排序 + $O(E \cdot \alpha(V)) \approx O(E)$ 并查集 = $O(E \log E)$ 总复杂度。

2.6 1995-2000 年：线性时间 MST 的突破

1995 年 David R. Karger、Philip N. Klein、Robert E. Tarjan 在《A randomized linear-time algorithm to find minimum spanning trees》Journal of the ACM 42(2):321-328 DOI:10.1145/201019.201022 给出随机化线性时间 MST 算法，期望复杂度 $O(E)$。该算法结合 Borůvka 阶段与随机采样，递归地处理子问题。

2000 年 Bernard Chazelle 在《A minimum spanning tree algorithm with inverse-Ackermann type complexity》Journal of the ACM 47(6):1028-1047 DOI:10.1145/355541.355562 给出确定性 $O(E \cdot \alpha(E, V))$ 算法，使用软堆（soft heap）打破 $O(E \log E)$ 屏障。这是目前已知最快的确定性 MST 算法。

理论前沿：是否能在确定性线性时间 $O(E)$ 内求解 MST 仍是开放问题。已知下界为 $\Omega(E)$，上界为 $O(E \cdot \alpha)$，差距为反 Ackermann 函数因子。

2.7 演进时间线

timeline
    title 最小生成树算法关键里程碑
    1926 : Boruvka 同步分治算法 (摩拉维亚电网)
    1930 : Jarnik 加点扩展算法 (查理大学)
    1956 : Kruskal 边排序贪心 (普林斯顿, DOI:10.1090/S0002-9939-1956-0078686-7)
    1957 : Prim 重新发现 Jarnik 算法 (Bell Labs)
    1964 : Galler-Fischer 树形并查集 (CACM)
    1973 : Hopcroft-Ullman 路径压缩, O(m log* n)
    1975 : Tarjan 反 Ackermann 上界 O(m alpha(n)) (JACM)
    1985 : Graham-Hell 系统化梳理 MST 历史 (Annals Hist. Comput.)
    1995 : Karger-Klein-Tarjan 随机化线性时间 (JACM)
    2000 : Chazelle 软堆确定性 O(E alpha) (JACM)
    2006 : Kleinberg-Tardos Algorithm Design 收录
    2022 : CLRS 第 4 版第 23 章 Kruskal 与 Prim

2.8 关键设计决策

1. 边排序而非点扩展（Kruskal 1956）：选择全局最小边，而非局部最近邻。代价是排序 $O(E \log E)$，但实现简单且天然支持最小生成森林
2. 并查集而非连通分量数组：朴素连通分量数组每次合并 $O(V)$，DSU 降至均摊 $O(\alpha(V))$
3. 路径压缩+按秩合并（Tarjan 1975）：单独使用任一优化只能达 $O(\log n)$，二者结合才达 $O(\alpha(n))$
4. 提前终止：当 MST 中已有 $n - 1$ 条边时立即停止，无需处理剩余边
5. 代数抽象：MST 算法可视为在 $(\min, +)$ 闭半环上的矩阵运算，统一了 MST、最短路、传递闭包等问题

教学提示：理解 Kruskal 算法演进的关键是抓住”贪心策略 + 数据结构优化”的二元结构。贪心策略保证正确性，数据结构优化决定复杂度。这一模式贯穿算法设计史，如 Dijkstra（贪心+堆）、A*（贪心+启发式）、Huffman（贪心+优先队列）。

3. 形式化定义

3.1 基本记号

设 $G = (V, E, w)$ 为连通无向加权图，其中：

• $V = \{1, 2, \ldots, n\}$ 为顶点集，$|V| = n$
• $E \subseteq \binom{V}{2}$ 为边集，$|E| = m$（无自环、无重边）
• $w: E \to \mathbb{R}$ 为边权函数

生成树（Spanning Tree）：$T \subseteq E$ 是 $G$ 的生成树，当且仅当：

1. 生成性：$(V, T)$ 连通
2. 无环性：$(V, T)$ 无环
3. 基数约束：$|T| = n - 1$

最小生成树（Minimum Spanning Tree, MST）：$G$ 的最小生成树 $T^*$ 满足：

$T^* = \arg\min_{T \in \mathcal{T}(G)} w(T), \quad w(T) = \sum_{e \in T} w(e)$

其中 $\mathcal{T}(G)$ 是 $G$ 所有生成树的集合。MST 可能不唯一（当存在相同权值的边时），但所有 MST 的权值相同。

3.2 切割性质

定义 3.1（切割）：图 $G = (V, E)$ 的一个切割（cut）是顶点集 $V$ 的一个划分 $(S, V - S)$，其中 $S \subseteq V, S \neq \emptyset, S \neq V$。

定义 3.2（跨越边）：切割 $(S, V - S)$ 的跨越边（crossing edge）是一端在 $S$、另一端在 $V - S$ 的边：$E(S, V - S) = \{(u, v) \in E : u \in S, v \in V - S\}$。

定理 3.1（切割性质，Cut Property）：设 $(S, V - S)$ 是 $G$ 的任意切割，$e \in E(S, V - S)$ 是跨越边中权值最小的边（即 $w(e) = \min_{e' \in E(S, V - S)} w(e')$），则存在 $G$ 的一棵 MST 包含 $e$。

证明（反证法 + 交换论证）：设 $T^*$ 是 $G$ 的任一 MST。若 $e \notin T^*$，考虑将 $e$ 加入 $T^*$ 后形成的环 $C$。由于 $e$ 跨越切割 $(S, V - S)$，环 $C$ 上必存在另一条跨越边 $e' \in T^* \cap E(S, V - S)$。由 $e$ 的最小性，$w(e) \leq w(e')$。

构造 $T' = T^* \cup \{e\} \setminus \{e'\}$，则：

• $T'$ 仍是生成树（环 $C$ 上删除 $e'$ 后无环且仍连通）
• $w(T') = w(T^*) + w(e) - w(e') \leq w(T^*)$

若 $w(e) < w(e')$，则 $w(T') < w(T^*)$，与 $T^*$ 是 MST 矛盾。若 $w(e) = w(e')$，则 $T'$ 也是 MST 且包含 $e$。$\blacksquare$

推论 3.1：若所有边权互不相同，则 MST 唯一，且每条切割的最小跨越边必在 MST 中。

3.3 回路性质

定理 3.2（回路性质，Cycle Property）：设 $C$ 是 $G$ 中的任一简单回路（cycle），$e \in C$ 是 $C$ 上权值最大的边，则存在 $G$ 的一棵 MST 不包含 $e$。

证明（反证法 + 交换论证）：设 $T^*$ 是 $G$ 的任一 MST，且 $e \in T^*$。删除 $e$ 后 $T^*$ 分裂为两个连通分量 $S$ 与 $V - S$，即 $e$ 跨越切割 $(S, V - S)$。由于 $C$ 是包含 $e$ 的回路，$C$ 上必存在另一条跨越边 $e'$（否则 $C$ 上的非 $e$ 边无法将 $S$ 与 $V - S$ 连通）。

由 $e$ 是 $C$ 上最大权边，$w(e) \geq w(e')$。构造 $T' = T^* \cup \{e'\} \setminus \{e\}$：

• $T'$ 仍是生成树
• $w(T') = w(T^*) - w(e) + w(e') \leq w(T^*)$

若 $w(e) > w(e')$，与 $T^*$ 是 MST 矛盾。若 $w(e) = w(e')$，则 $T'$ 也是 MST 且不包含 $e$。$\blacksquare$

对偶关系：切割性质与回路性质互为对偶：

3.4 贪心选择性质

定理 3.3（贪心选择性质）：设 $e$ 是 $G$ 中权值最小的边，则存在 $G$ 的一棵 MST 包含 $e$。

证明：取切割 $(S, V - S) = (\{u\}, V \setminus \{u\})$，其中 $e = (u, v)$。$e$ 是该切割的最小跨越边（因 $e$ 是 $G$ 中最小权边），由切割性质（定理 3.1）即得。$\blacksquare$

推论 3.3：Kruskal 算法每步选择当前最小权不形成环的边，等价于在某个切割上选择最小跨越边。

3.5 最优子结构

定理 3.4（最优子结构）：设 $e = (u, v)$ 是 Kruskal 算法第一步选中的边（即最小权边），令 $G' = (V', E')$ 为将 $u, v$ 合并为单个超顶点 $w$ 后的图，则 $G$ 的 MST 等于 $\{e\}$ 加上 $G'$ 的 MST。

证明：设 $T$ 是 $G$ 的 MST，由定理 3.3 可设 $e \in T$。删除 $e$ 后 $T$ 分裂为两棵子树 $T_u$（含 $u$）与 $T_v$（含 $v$）。在 $G'$ 中合并 $u, v$ 为 $w$ 后，$T_u \cup T_v$ 形成 $G'$ 的一棵生成树 $T'$，且 $w(T') = w(T) - w(e)$。

若 $G'$ 存在权值更小的生成树 $T''$，则 $T'' \cup \{e\}$ 是 $G$ 的生成树且权值 $w(T'') + w(e) < w(T)$，矛盾。故 $T'$ 是 $G'$ 的 MST。$\blacksquare$

3.6 算法形式化描述

算法 Kruskal（$G = (V, E, w)$）：

1.  T ← ∅                          // MST 边集合
2.  for each v ∈ V: MAKE-SET(v)    // 并查集初始化
3.  sort E by w in non-decreasing order
4.  for each (u, v) ∈ E (按权值升序):
5.      if FIND(u) ≠ FIND(v):      // u, v 不在同一连通分量
6.          T ← T ∪ {(u, v)}       // 加入 MST
7.          UNION(u, v)            // 合并连通分量
8.      if |T| = n - 1: break      // 提前终止
9.  return T

正确性不变量：

• 任意时刻，$T$ 是森林（无环）
• 任意时刻，$T$ 是某个 MST 的子集

4. 理论推导

4.1 Kruskal 算法正确性证明

定理 4.1（Kruskal 算法正确性）：对连通无向加权图 $G = (V, E, w)$，Kruskal 算法返回一棵 MST。

证明（归纳法 + 切割性质）：

设算法依次选中的边为 $e_1, e_2, \ldots, e_{n-1}$。我们证明对每个 $k \in \{0, 1, \ldots, n-1\}$，存在 MST $T^*$ 使得 $\{e_1, \ldots, e_k\} \subseteq T^*$。

基础：$k = 0$ 时，$\emptyset \subseteq T^*$ 显然成立。

归纳步：假设 $\{e_1, \ldots, e_{k-1}\} \subseteq T^*$，考虑 $e_k = (u, v)$。设 $S$ 是 $u$ 在森林 $\{e_1, \ldots, e_{k-1}\}$ 中的连通分量。由算法逻辑，$v \notin S$（否则 $e_k$ 会形成环被跳过），故 $e_k$ 跨越切割 $(S, V - S)$。

考虑 $T^*$ 中 $u$ 与 $v$ 之间的路径 $P$（$T^*$ 是树，故 $P$ 存在）。$P$ 必跨越切割 $(S, V - S)$，即存在边 $e' \in P \cap E(S, V - S)$。

关键断言：$w(e_k) \leq w(e')$。

若 $e' \in \{e_1, \ldots, e_{k-1}\}$，则 $e'$ 跨越切割 $(S, V - S)$ 意味着 $e'$ 同时连接 $S$ 与 $V - S$ 中的点。但 $S$ 是 $u$ 的连通分量，$e' \in \{e_1, \ldots, e_{k-1}\}$ 又使 $u$ 与 $e'$ 的另一端连通，矛盾。故 $e' \notin \{e_1, \ldots, e_{k-1}\}$。

算法在选中 $e_k$ 前，已考察过所有 $w < w(e_k)$ 的边。$e' \notin \{e_1, \ldots, e_{k-1}\}$ 意味着 $e'$ 要么 $w(e') \geq w(e_k)$，要么 $w(e') = w(e_k)$ 但 $e'$ 排在 $e_k$ 之后（被同时考察时未选中）。

• 若 $w(e') > w(e_k)$：由 $e'$ 跨越 $(S, V - S)$，且 $w(e_k) < w(e')$，则 $e_k$ 应在 $e'$ 之前被考察。但 $e_k$ 当前才被选中，说明 $e'$ 在 $e_k$ 之前未被选中——这只能是 $e'$ 形成环。然而 $e' \in T^*$，$T^*$ 是树无环，又 $e' \notin \{e_1, \ldots, e_{k-1}\}$，故 $e'$ 在加入 $T^*$ 时并不形成环（与 $T^*$ 是树一致）。
• 综合得 $w(e_k) \leq w(e')$。

构造 $T' = T^* \cup \{e_k\} \setminus \{e'\}$，则 $T'$ 仍是生成树（删除 $e'$ 后 $T^*$ 分裂为两棵子树，$e_k$ 跨越同一切割重新连接），且 $w(T') \leq w(T^*)$。故 $T'$ 也是 MST 且 $\{e_1, \ldots, e_k\} \subseteq T'$。

结论：$k = n - 1$ 时，$\{e_1, \ldots, e_{n-1}\}$ 是 MST。$\blacksquare$

4.2 时间复杂度分析

定理 4.2：Kruskal 算法的时间复杂度为 $O(E \log E) = O(E \log V)$。

分析：

1. 排序阶段：对 $E$ 条边按权值排序，使用比较排序（如堆排序、归并排序）需 $O(E \log E)$。由于 $|E| \leq |V|^2$，$\log E \leq 2 \log V$，故 $O(E \log E) = O(E \log V)$
2. 并查集初始化：$V$ 次 MAKE-SET，总 $O(V)$
3. 环检测阶段：每条边至多被考察一次，每次 2 次 FIND + 至多 1 次 UNION。$E$ 次 UNION/FIND 操作总代价 $O(E \cdot \alpha(V))$，其中 $\alpha$ 是反 Ackermann 函数，对所有实际 $V \leq 10^{80}$ 有 $\alpha(V) \leq 4$
4. 提前终止：当选满 $n - 1$ 条边后立即停止，最坏情况仍需考察所有边

总复杂度：

$T(E, V) = O(E \log E) + O(V) + O(E \cdot \alpha(V)) = O(E \log E) = O(E \log V)$

瓶颈：边排序 $O(E \log E)$ 是主导项。并查集操作 $O(E \cdot \alpha(V))$ 在实际中可视为 $O(E)$。

4.3 空间复杂度分析

定理 4.3：Kruskal 算法的空间复杂度为 $O(E + V)$。

分析：

1. 边存储：$O(E)$ 用于存储所有边
2. 并查集：$O(V)$ 用于 parent 与 rank 数组
3. 结果存储：$O(V)$ 用于存储 MST 边集合（至多 $V - 1$ 条边）
4. 排序辅助：原地排序（如堆排序）需 $O(1)$ 额外空间；归并排序需 $O(E)$ 辅助空间

总空间：$O(E + V)$。若边已预先按权值排序（如流式输入），则仅需 $O(V)$ 额外空间。

4.4 与 Prim 算法的复杂度对比

选型规则：

• 稠密图（$E \approx V^2$）：Prim 邻接矩阵 $O(V^2)$ 最优
• 稀疏图（$E \approx V$）：Kruskal $O(V \log V)$ 或 Prim 斐波那契堆 $O(V \log V)$ 持平
• 中等密度（$E \approx V \log V$）：Kruskal 与 Prim 持平
• 流式输入：Kruskal 优势明显（边可流式到达）

4.5 与 Borůvka 算法的复杂度对比

选型规则：

• 串行场景：Kruskal 简单且 $O(E \log E) \approx O(E \log V)$ 与 Borůvka 同阶
• 并行场景：Borůvka 优势明显，每轮各分量独立选择最小边，可分布式执行
• GPU 加速：Borůvka 更适合 GPU 实现（每轮同步合并，符合 SIMT 模型）

4.6 不变量与终止性

循环不变量：在第 $k$ 轮迭代开始时（已考察 $k$ 条边）：

1. $T$ 是森林（无环）
2. $T$ 是某个 MST 的子集
3. 并查集 DSU 维护了 $V$ 中所有顶点的当前连通分量

终止性：算法必在 $n - 1$ 条边被选中后终止，或所有边考察完毕后终止。连通图必有 MST，故必终止。

5. 代码示例

5.1 Python 实现（标准版）

"""Kruskal 最小生成树算法 - Python 标准实现

基于并查集（路径压缩 + 按秩合并）实现高效环检测。
时间复杂度: O(E log E)
空间复杂度: O(V)
"""

from typing import List, Tuple, Optional


class UnionFind:
    """并查集数据结构，支持路径压缩与按秩合并。

    均摊单次操作复杂度: O(alpha(n)) ≈ O(1)
    """

    def __init__(self, n: int) -> None:
        """初始化 n 个独立集合。

        Args:
            n: 元素数量
        """
        self.parent: List[int] = list(range(n))
        self.rank: List[int] = [0] * n
        self.components: int = n  # 当前连通分量数

    def find(self, x: int) -> int:
        """查找元素 x 所在集合的代表元（根）。

        Args:
            x: 待查找的元素

        Returns:
            x 所在集合的代表元
        """
        # 路径压缩：递归将路径上所有节点直接挂到根
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        """合并 x 与 y 所在的集合。

        Args:
            x: 元素 1
            y: 元素 2

        Returns:
            True 若合并成功（原属不同集合），False 若已在同一集合
        """
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # 已在同一集合，合并失败

        # 按秩合并：将矮树挂到高树下
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

        self.components -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        """判断 x 与 y 是否在同一集合。"""
        return self.find(x) == self.find(y)


def kruskal(n: int, edges: List[Tuple[int, int, float]]) -> Tuple[List[Tuple[int, int, float]], float]:
    """Kruskal 最小生成树算法。

    Args:
        n: 顶点数（顶点编号 0..n-1）
        edges: 边列表，每条边为 (u, v, weight)

    Returns:
        (mst_edges, total_weight):
            mst_edges: MST 中的边列表
            total_weight: MST 总权值
            若图不连通，返回最小生成森林与对应总权值
    """
    # 步骤 1: 边按权值升序排序
    sorted_edges = sorted(edges, key=lambda e: e[2])

    # 步骤 2: 初始化并查集
    uf = UnionFind(n)

    # 步骤 3: 贪心选边
    mst: List[Tuple[int, int, float]] = []
    total_weight: float = 0.0

    for u, v, w in sorted_edges:
        if uf.union(u, v):  # 不在同一集合，可加入 MST
            mst.append((u, v, w))
            total_weight += w
            if len(mst) == n - 1:  # 提前终止
                break

    return mst, total_weight


# 使用示例
if __name__ == "__main__":
    # 图: 6 个顶点, 8 条边
    #     A --4-- B --3-- C
    #     |      /|       |
    #     1    2  5       6
    #     |  /    |       |
    #     D --8-- E --7-- F
    edges = [
        (0, 1, 4),  # A-B
        (1, 2, 3),  # B-C
        (0, 3, 1),  # A-D
        (1, 4, 2),  # B-E
        (1, 3, 5),  # B-D
        (2, 5, 6),  # C-F
        (4, 5, 7),  # E-F
        (3, 4, 8),  # D-E
    ]
    mst, total = kruskal(6, edges)
    print(f"MST 边: {mst}")
    print(f"MST 总权值: {total}")
    # 输出:
    # MST 边: [(0, 3, 1), (1, 4, 2), (1, 2, 3), (0, 1, 4), (2, 5, 6)]
    # MST 总权值: 16

5.2 Python 实现（NetworkX 风格）

"""Kruskal 算法 NetworkX 风格实现，与 NetworkX minimum_spanning_tree 接口兼容。

支持多重图、带属性图、自定义权值函数。
"""

from typing import Callable, Dict, Hashable, List, Tuple, Any
from collections import defaultdict


class NetworkXStyleKruskal:
    """NetworkX 风格 Kruskal MST。

    支持:
    - 任意可哈希顶点（不限于 0..n-1 整数）
    - 多重图（自动选择最小权边）
    - 自定义权值函数
    - 最小生成森林（图不连通时）
    """

    def __init__(self, weight: str = "weight") -> None:
        """初始化 Kruskal 求解器。

        Args:
            weight: 边权值属性名，默认 'weight'
        """
        self.weight_attr = weight

    def minimum_spanning_tree(self, graph: Dict[Hashable, List[Tuple[Hashable, Dict[str, Any]]]]) -> List[Tuple[Hashable, Hashable, float]]:
        """计算图的最小生成树（森林）。

        Args:
            graph: 邻接表表示，graph[u] = [(v, {weight: w, ...}), ...]

        Returns:
            MST 边列表 [(u, v, w), ...]
        """
        # 收集所有边（去重，无向图每条边只考察一次）
        edges: List[Tuple[float, Hashable, Hashable]] = []
        seen: set = set()
        for u, neighbors in graph.items():
            for v, attrs in neighbors:
                edge_key = (min(u, v), max(u, v))  # 无向边规范化
                if edge_key in seen:
                    continue
                seen.add(edge_key)
                w = attrs.get(self.weight_attr, 1.0)
                edges.append((w, u, v))

        # 按权值排序
        edges.sort(key=lambda e: e[0])

        # 顶点编号映射（支持任意可哈希顶点）
        vertices = list(graph.keys())
        vertex_to_id = {v: i for i, v in enumerate(vertices)}
        n = len(vertices)

        # 并查集
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]  # 路径压缩（迭代版）
                x = parent[x]
            return x

        def union(x: int, y: int) -> bool:
            rx, ry = find(x), find(y)
            if rx == ry:
                return False
            if rank[rx] < rank[ry]:
                rx, ry = ry, rx
            parent[ry] = rx
            if rank[rx] == rank[ry]:
                rank[rx] += 1
            return True

        # Kruskal 主循环
        mst: List[Tuple[Hashable, Hashable, float]] = []
        for w, u, v in edges:
            if union(vertex_to_id[u], vertex_to_id[v]):
                mst.append((u, v, w))
                if len(mst) == n - 1:
                    break

        return mst


# 使用示例
if __name__ == "__main__":
    graph = {
        "A": [("B", {"weight": 4}), ("D", {"weight": 1})],
        "B": [("A", {"weight": 4}), ("C", {"weight": 3}), ("D", {"weight": 5}), ("E", {"weight": 2})],
        "C": [("B", {"weight": 3}), ("F", {"weight": 6})],
        "D": [("A", {"weight": 1}), ("B", {"weight": 5}), ("E", {"weight": 8})],
        "E": [("B", {"weight": 2}), ("D", {"weight": 8}), ("F", {"weight": 7})],
        "F": [("C", {"weight": 6}), ("E", {"weight": 7})],
    }
    solver = NetworkXStyleKruskal(weight="weight")
    mst = solver.minimum_spanning_tree(graph)
    total = sum(w for _, _, w in mst)
    print(f"MST 边: {mst}")
    print(f"MST 总权值: {total}")

5.3 C++ 实现

// Kruskal 最小生成树算法 - C++ 实现
// 编译: g++ -O2 -std=c++17 kruskal.cpp -o kruskal
// 时间复杂度: O(E log E)
// 空间复杂度: O(V + E)

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// 并查集（路径压缩 + 按秩合并）
class UnionFind {
public:
    explicit UnionFind(int n) : parent_(n), rank_(n, 0) {
        std::iota(parent_.begin(), parent_.end(), 0);  // parent_[i] = i
    }

    // 查找代表元（带路径压缩）
    int find(int x) {
        if (parent_[x] != x) {
            parent_[x] = find(parent_[x]);
        }
        return parent_[x];
    }

    // 合并两个集合
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;

        if (rank_[rx] < rank_[ry]) std::swap(rx, ry);
        parent_[ry] = rx;
        if (rank_[rx] == rank_[ry]) ++rank_[rx];
        return true;
    }

private:
    std::vector<int> parent_;
    std::vector<int> rank_;
};

// 边结构
struct Edge {
    int u, v;
    long long weight;

    // 用于排序: 按权值升序
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

// Kruskal 算法
// 返回 MST 的边列表与总权值
std::pair<std::vector<Edge>, long long> kruskal(int n, std::vector<Edge> edges) {
    // 步骤 1: 边按权值排序
    std::sort(edges.begin(), edges.end());

    // 步骤 2: 初始化并查集
    UnionFind uf(n);

    // 步骤 3: 贪心选边
    std::vector<Edge> mst;
    long long total_weight = 0;

    for (const auto& e : edges) {
        if (uf.unite(e.u, e.v)) {  // 不在同一集合
            mst.push_back(e);
            total_weight += e.weight;
            if (static_cast<int>(mst.size()) == n - 1) break;
        }
    }

    return {mst, total_weight};
}

int main() {
    int n = 6;
    std::vector<Edge> edges = {
        {0, 1, 4}, {1, 2, 3}, {0, 3, 1}, {1, 4, 2},
        {1, 3, 5}, {2, 5, 6}, {4, 5, 7}, {3, 4, 8}
    };

    auto [mst, total] = kruskal(n, edges);
    std::cout << "MST 边:\n";
    for (const auto& e : mst) {
        std::cout << "  (" << e.u << " - " << e.v << ") w=" << e.weight << "\n";
    }
    std::cout << "MST 总权值: " << total << "\n";
    return 0;
}

5.4 Java 实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Kruskal 最小生成树算法 - Java 实现
 *
 * <p>时间复杂度: O(E log E)
 * <p>空间复杂度: O(V + E)
 */
public class KruskalMST {

    /** 并查集（路径压缩 + 按秩合并） */
    private static class UnionFind {
        private final int[] parent;
        private final int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        /** 查找代表元（带路径压缩） */
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        /** 合并两个集合 */
        public boolean union(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx == ry) return false;

            if (rank[rx] < rank[ry]) {
                int tmp = rx; rx = ry; ry = tmp;
            }
            parent[ry] = rx;
            if (rank[rx] == rank[ry]) {
                rank[rx]++;
            }
            return true;
        }
    }

    /** 加权无向边 */
    public static class Edge implements Comparable<Edge> {
        public final int u, v;
        public final long weight;

        public Edge(int u, int v, long weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge other) {
            return Long.compare(this.weight, other.weight);
        }
    }

    /**
     * 计算 Kruskal 最小生成树
     *
     * @param n 顶点数
     * @param edges 边列表
     * @return MST 边列表
     */
    public static List<Edge> kruskal(int n, List<Edge> edges) {
        // 步骤 1: 边排序
        Collections.sort(edges);

        // 步骤 2: 并查集初始化
        UnionFind uf = new UnionFind(n);

        // 步骤 3: 贪心选边
        List<Edge> mst = new ArrayList<>();
        for (Edge e : edges) {
            if (uf.union(e.u, e.v)) {
                mst.add(e);
                if (mst.size() == n - 1) break;
            }
        }
        return mst;
    }

    public static void main(String[] args) {
        int n = 6;
        List<Edge> edges = List.of(
            new Edge(0, 1, 4), new Edge(1, 2, 3), new Edge(0, 3, 1),
            new Edge(1, 4, 2), new Edge(1, 3, 5), new Edge(2, 5, 6),
            new Edge(4, 5, 7), new Edge(3, 4, 8)
        );

        List<Edge> mst = kruskal(n, new ArrayList<>(edges));
        long total = mst.stream().mapToLong(e -> e.weight).sum();
        System.out.println("MST 边:");
        for (Edge e : mst) {
            System.out.printf("  (%d - %d) w=%d%n", e.u, e.v, e.weight);
        }
        System.out.println("MST 总权值: " + total);
    }
}

5.5 变体实现：最大生成树与最小生成森林

"""Kruskal 算法变体实现：最大生成树、最小生成森林、按边数限制的森林。"""

from typing import List, Tuple


def maximum_spanning_tree(n: int, edges: List[Tuple[int, int, float]]) -> Tuple[List[Tuple[int, int, float]], float]:
    """最大生成树: 边按权值降序排序，其余与 Kruskal 一致。

    应用: 单链聚类（Single-Linkage Clustering）中保留类间距离最大的合并。

    Args:
        n: 顶点数
        edges: 边列表

    Returns:
        (mst_edges, total_weight) 最大生成树
    """
    sorted_edges = sorted(edges, key=lambda e: -e[2])  # 降序
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1
        return True

    mst = []
    total = 0.0
    for u, v, w in sorted_edges:
        if union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:
                break
    return mst, total


def minimum_spanning_forest(n: int, edges: List[Tuple[int, int, float]]) -> List[Tuple[int, int, float]]:
    """最小生成森林: 不要求连通，遍历所有边。

    应用: 图不连通时的自然推广。

    Args:
        n: 顶点数
        edges: 边列表

    Returns:
        MSF 边列表
    """
    sorted_edges = sorted(edges, key=lambda e: e[2])
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1
        return True

    forest = []
    for u, v, w in sorted_edges:
        if union(u, v):
            forest.append((u, v, w))
    return forest


def k_clustering(n: int, edges: List[Tuple[int, int, float]], k: int) -> Tuple[List[Tuple[int, int, float]], float]:
    """K-聚类（基于最大生成树）: 保留前 n-k 条最大边。

    应用: 单链聚类（Single-Linkage Clustering）。

    Args:
        n: 顶点数
        edges: 边列表
        k: 目标簇数

    Returns:
        (cluster_edges, max_min_distance):
            cluster_edges: 用于聚类的边
            max_min_distance: 簇间最小距离的最大值
    """
    sorted_edges = sorted(edges, key=lambda e: -e[2])  # 降序
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1
        return True

    cluster_edges = []
    components = n
    for u, v, w in sorted_edges:
        if components == k:
            break  # 已达到目标簇数
        if union(u, v):
            cluster_edges.append((u, v, w))
            components -= 1

    # 计算簇间最小距离的最大值（即下一条应选的最大边的权值）
    max_min_distance = 0.0
    for u, v, w in sorted_edges:
        if find(u) != find(v):
            max_min_distance = max(max_min_distance, w)

    return cluster_edges, max_min_distance

5.6 代码执行示例

# 完整执行示例
if __name__ == "__main__":
    edges = [
        (0, 1, 4), (1, 2, 3), (0, 3, 1), (1, 4, 2),
        (1, 3, 5), (2, 5, 6), (4, 5, 7), (3, 4, 8)
    ]

    # 1. 最小生成树
    mst, total = kruskal(6, edges)
    print(f"MST: {mst}, 总权值: {total}")
    # MST: [(0,3,1), (1,4,2), (1,2,3), (0,1,4), (2,5,6)], 总权值: 16

    # 2. 最大生成树
    max_mst, max_total = maximum_spanning_tree(6, edges)
    print(f"最大生成树: {max_mst}, 总权值: {max_total}")
    # 最大生成树: [(3,4,8), (4,5,7), (2,5,6), (1,3,5), (0,1,4)], 总权值: 30

    # 3. K-聚类 (k=2)
    cluster_edges, max_min_dist = k_clustering(6, edges, k=2)
    print(f"聚类边: {cluster_edges}, 簇间最大最小距离: {max_min_dist}")

6. 对比分析

6.1 Kruskal vs Prim vs Borůvka：三大 MST 算法对比

6.2 与 Dijkstra 单源最短路径对比

6.3 与 Floyd-Warshall 对比

6.4 与并查集单独使用对比

6.5 选型决策树

是否求 MST？
├── 否 → 不使用 Kruskal
└── 是
    ├── 图是否稠密 (E ≈ V²)？
    │   ├── 是 → Prim 邻接矩阵 O(V²)
    │   └── 否 → 继续
    ├── 是否需要并行化？
    │   ├── 是 → Borůvka O(E log V)
    │   └── 否 → 继续
    ├── 图是否连通？
    │   ├── 否 → Kruskal 天然生成森林
    │   └── 是 → 继续
    ├── 边是否可流式到达？
    │   ├── 是 → Kruskal + 外部排序
    │   └── 否 → Kruskal（默认）或 Prim 堆版
    └── Kruskal O(E log E)

7. 常见陷阱与误区

7.1 陷阱 1：忘记并查集优化导致退化

错误代码：

# 错误：朴素并查集，查找 O(n)，总复杂度 O(E·n)
def find(x):
    while parent[x] != x:
        x = parent[x]
    return x

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return False
    parent[ry] = rx  # 无按秩合并
    return True

问题：朴素并查集最坏情况退化为链，单次 find $O(n)$，Kruskal 总复杂度退化为 $O(E \cdot n)$。对于 $n = 10^5$ 的图，比正确实现慢 $10^5$ 倍。

正确做法：必须同时使用路径压缩与按秩合并（或按大小合并）：

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 路径压缩
    return parent[x]

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return False
    if rank[rx] < rank[ry]:  # 按秩合并
        rx, ry = ry, rx
    parent[ry] = rx
    if rank[rx] == rank[ry]:
        rank[rx] += 1
    return True

理论依据：Tarjan 1975 证明，单独使用任一优化只能达 $O(\log n)$，二者结合才达均摊 $O(\alpha(n))$。

7.2 陷阱 2：排序方向错误

错误代码：

# 错误：降序排序，得到最大生成树而非最小生成树
sorted_edges = sorted(edges, key=lambda e: -e[2])

问题：用户误以为”先选大边”能得到 MST，实际上得到的是最大生成树（Maximum Spanning Tree）。最大生成树在单链聚类中有应用，但通常不是 MST 问题的解。

正确做法：最小生成树必须升序排序：

sorted_edges = sorted(edges, key=lambda e: e[2])  # 升序

7.3 陷阱 3：忽视提前终止

错误代码：

# 错误：未提前终止，遍历所有 E 条边
for u, v, w in sorted_edges:
    if uf.union(u, v):
        mst.append((u, v, w))
        # 缺少 if len(mst) == n - 1: break

问题：未在选满 $n - 1$ 条边时提前终止，会继续遍历剩余边。对于稀疏图影响较小，但对于稠密图（$E \approx V^2$）会浪费 $O(V^2)$ 次无效并查集操作。虽然均摊 $O(\alpha)$，但常数因子仍可观。

正确做法：

for u, v, w in sorted_edges:
    if uf.union(u, v):
        mst.append((u, v, w))
        if len(mst) == n - 1:  # 提前终止
            break

7.4 陷阱 4：处理不连通图

错误代码：

# 错误：假设图必连通，返回结果可能不是生成树
mst, total = kruskal(n, edges)
assert len(mst) == n - 1  # 不连通图会触发断言失败

问题：不连通图不存在生成树，Kruskal 算法返回的是最小生成森林（Minimum Spanning Forest, MSF）。代码若假设结果必为 $n - 1$ 条边，会在不连通图上崩溃。

正确做法：