📚 Kruskal’s Algorithm: Minimum Spanning Tree Construction | 克鲁斯卡尔算法：最小生成树的构建
Kruskal's algorithm is one of the fundamental greedy methods for finding a Minimum Spanning Tree (MST) of a connected, weighted, undirected graph. By repeatedly selecting the globally cheapest edge that does not create a cycle, it builds an optimal set of edges linking all vertices with minimum total weight. This article unpacks the algorithm step by step, examines the supporting union–find data structure, walks through a worked example, analyses complexity, and contrasts it with Prim's algorithm – all tailored to the Edexcel A-Level Computer Science specification.
克鲁斯卡尔算法是寻找连通、带权、无向图的最小生成树的经典贪心方法之一。它反复选取不会形成环的全局最便宜边，逐步构建起连接所有顶点的最小总权重边集。本文将逐步拆解该算法，剖析支撑它的并查集数据结构，演示完整示例，分析时间复杂度，并与普里姆算法进行对比——全部紧扣 Edexcel A-Level 计算机科学考纲。
1. Introduction to Minimum Spanning Trees (MST) | 最小生成树简介
A Minimum Spanning Tree of a connected undirected graph with weighted edges is a subset of the edges that forms a tree containing every vertex, such that the sum of the edge weights is as small as possible. In network design problems – laying cables, pipelines, or circuit interconnects – the MST provides the cheapest way to maintain connectivity without any redundancy. Kruskal's algorithm attacks this problem from the edge list perspective, ignoring any predetermined starting vertex.
对于一个带权连通无向图，最小生成树是包含所有顶点的无环连通子图（即树），且各边权重之和尽可能小。在铺设电缆、管道或电路互连等网络设计问题中，MST 给出了在不产生冗余的前提下保持连通的最低成本方案。克鲁斯卡尔算法从边列表的视角解决这一问题，不依赖任何预先选定的起始顶点点。
2. Kruskal’s Algorithm Overview | 克鲁斯卡尔算法概述
The core idea of Kruskal's algorithm is deceptively simple: sort all edges of the graph in non-decreasing order of weight, then iterate through this sorted list. An edge is added to the growing spanning forest if it connects two different components; otherwise it is discarded. By always choosing the smallest viable edge, the algorithm follows a greedy strategy that globally yields an optimal MST.
克鲁斯卡尔算法的核心思想看似简单：将图中所有边按权重非递减排序，然后依次扫描排序后的列表。若当前边连接两个不同的连通分量，则将其加入生成森林；否则丢弃。总是选择可行的最小边，这一贪心策略最终能全局地构造出最优的最小生成树。
3. Step-by-Step Process | 算法步骤详解
The algorithm can be formalised into the following stages:
- Create a forest F, initially consisting of |V| isolated vertices (each vertex is its own tree).
- Sort all edges E in order of increasing weight.
- For each edge (u, v) taken from the sorted list:
- If u and v belong to different trees in F, add the edge to F and merge the two trees.
- If u and v are already in the same tree, skip the edge (it would create a cycle).
- Stop when n−1 edges have been added, where n = |V|, or when all edges have been examined.
该算法可形式化为以下步骤：
- 创建一个森林 F，初始时包含 |V| 棵孤立的树（每个顶点点自成一树）。
- 将所有边 E 按权重递增排序。
- 对排序列表中的每条边 (u, v)：
- 若 u 与 v 在 F 中分属不同的树，则将该边加入 F，并合并这两棵树。
- 若 u 与 v 已在同一棵树内，则略过此边（否则会形成环）。
- 当已添加 n−1 条边（n = |V|），或所有边均已处理完毕，算法终止。
4. Data Structures: Disjoint Set / Union-Find | 数据结构：不相交集/并查集
Efficiently testing whether two vertices lie in the same component and merging components is crucial. The disjoint-set (or union–find) data structure tracks a partition of the vertices. It supports two operations: find(v) returns the representative (root) of the set containing v, and union(u, v) merges the sets containing u and v. With path compression and union by rank, both operations run in near-constant amortised time, O(α(n)), where α is the extremely slow-growing inverse Ackermann function.
高效判断两个顶点点是否在同一连通分量以及合并分量至关重要。不相交集（或称并查集）数据结构维护着顶点点的一个划分。它支持两个操作：find(v) 返回包含 v 的集合的代表元（根），union(u, v) 合并包含 u 与 v 的集合。借助路径压缩和按秩合并，两个操作均摊时间接近常数，为 O(α(n))，其中 α 是增长极慢的阿克曼反函数。
5. Greedy Strategy and Correctness | 贪心策略与正确性
Kruskal's algorithm is a textbook example of the greedy method: at each step it picks the lowest-weight edge that does not violate feasibility (no cycles). The correctness proof rests on the Cut Property: for any cut (a partition of vertices into two sets), the minimum-weight edge crossing the cut must belong to some MST. By always merging two components with the cheapest connecting edge, the algorithm implicitly respects this property and constructs the MST incrementally.
克鲁斯卡尔算法是贪心方法的典例：每一步选取不会破坏可行性（不产生环）的最小权重边。其正确性证明依赖于“割性质”：对于顶点点的任意一个划分（割），横跨该割的最小权重边必定属于某个 MST。算法在每一步都用最便宜的连接边合并两个连通分量，本质上就是遵循这一性质，逐步构建起 MST。
6. Worked Example Part 1: Graph Setup | 手工示例第一部分：图设置
Consider a simple undirected graph with 6 vertices (A, B, C, D, E, F) and the following weighted edges:
考虑一个简单的无向图，包含 6 个顶点点 (A, B, C, D, E, F) 和以下带权边：
| Edge | Weight |
|---|---|
| A–B | 4 |
| A–F | 2 |
| B–C | 6 |
| B–F | 5 |
| C–D | 3 |
| C–F | 1 |
| D–E | 2 |
| E–F | 4 |
The edges sorted by weight are: C–F (1), A–F (2), D–E (2), C–D (3), A–B (4), E–F (4), B–F (5), B–C (6). We will apply Kruskal's algorithm to this edge list.
边按权重排序后的顺序为：C–F (1), A–F (2), D–E (2), C–D (3), A–B (4), E–F (4), B–F (5), B–C (6)。我们将对这一边列表应用克鲁斯卡尔算法。
7. Worked Example Part 2: Applying Kruskal | 手工示例第二部分：应用算法
Initialise six singleton sets: {A}, {B}, {C}, {D}, {E}, {F}. Process edges in sorted order:
- C–F (1): different sets, add edge. Merge {C} and {F} → {C, F}.
- A–F (2): A in {A}, F in {C,F} → different, add edge. Merge → {A, C, F}.
- D–E (2): D and E are in separate sets, add edge. Merge → {D, E}.
- C–D (3): C in {A,C,F}, D in {D,E} → different, add edge. Merge → {A, C, D, E, F}.
- A–B (4): , B in {B} → different, add edge. Merge → {A, B, C, D, E, F} (all vertices now connected).
- E–F (4): both in same set → skip (would form cycle E–F–A–C–D–E).
- (Remaining edges B–F, B–C also skipped as they would create cycles.)
初始化六个单元素集合：{A}, {B}, {C}, {D}, {E}, {F}。按排序顺序处理各边：
- C–F (1): 不同集合，加入边。合并 {C} 与 {F} → {C, F}。
- A–F (2): A 在 {A}，F 在 {C,F} → 不同，加入边。合并 → {A, C, F}。
- D–E (2): D 与 E 在不同集合，加入边。合并 → {D, E}。
- C–D (3): C 在 {A,C,F}，D 在 {D,E} → 不同，加入边。合并 → {A, C, D, E, F}。
- A–B (4): A 在大集合，B 在 {B} → 不同，加入边。合并 → {A, B, C, D, E, F}（所有顶点点已连通）。
- E–F (4): 已在同一集合 → 跳过（加入将形成环 E–F–A–C–D–E）。
- （剩余边 B–F、B–C 均因会形成环而跳过。）
8. Complexity Analysis | 复杂度分析
h E ≤ V², log E is O(log V), thus the sorting step can also be expressed as O(E log V). After sorting, E operations of union/find are performed. With optimal union– E) or equivalently O(E log V). The space complexity is O(V + E) for storing the graph and union–find structures.
算法的开销主要由边的排序主导，使用基于比较的高效排序（如归并排序）需 O(E log E) 时间。对于简单图，E ≤ V²，故 log E 是 O(log V)，排序阶段也可表示为 O(E log V)。排序之后，执行 E 次并查集操作。采用优化的并查集，合计时间接近 O(E α(V))，这对任何实际规模的图几乎是线性的。因此整体时间复杂度为 O(E log E) 或等效的 O(E log V)。空间复杂度为 O(V + E)，用于存储图和并查集结构。
9. Comparison with Prim’s Algorithm | 与普里姆算法的比较
and Prim produce an MST, but they differ in approach and efficiency depending on the graph's density. Prim' priority queue. Kruskal considers the global edge order and works with a forest of components. For sparse graphs (E ≈ V), Kruskal’s O(E log E) performs well. For dense graphs (E ≈ V²), Prim’s O(V²) with an array, or O(E log V) with a binary heap, may be more appropriate. Kruskal is often easier to explain from sorted edge lists, while Prim feels more intuitive when given an adjacency matrix.
克鲁斯卡尔算法和普里姆算法都能生成 MST，但在策略上不同，且在不同密度的图上效率各异。普里姆算法从某一顶点出发，逐步生长单棵树，选取连接树与外部顶点的最便宜边，常见实现借助优先队列。克鲁斯卡尔则考虑边的全局顺序，维护一个由多棵子树构成的森林。对于稀疏图（E ≈ V），克鲁斯卡尔的 O(E log E) 表现良好；对于稠密图（E ≈ V²），普里姆的 O(V²)（数组实现）或 O(E log V)（二叉堆实现）可能更合适。从边的排序列表出发解释克鲁斯卡尔通常更简明，而给定邻接矩阵时普里姆的直觉性更强。
10. Implementation Considerations and Pseudocode | 实现考虑与伪代码
Below is a high-level pseudocode for Kruskal's algorithm, assuming a UnionFind abstract data type with MakeSet, Find, and Union:
以下为克鲁斯卡尔算法的高层伪代码，假定有一个支持 MakeSet、Find 和 Union 操作的并查集抽象数据类型：
Kruskal(G):
A <- empty set
for each vertex v in G.V:
MakeSet(v)
sort G.E by weight ascending
for each edge (u, v) in sorted G.E:
if Find(u) != Find(v):
A <- A ∪ {(u, v)}
Union(u, v)
return A
In practice, the edges are often stored as objects with attributes 'u', 'v', and 'weight'. Sorting can be done using any O(E log E) algorithm. The union– on by rank to achieve the desired amortised complexity. Always remember to stop early once |A| = |V| − 1.
实践中，边通常存储为包含属性 ‘u’、‘v’ 和 ‘weight’ 的对象。排序可使用任何 O(E log E) 算法。并查集数据结构必须仔细实现，加入路径压缩和按秩合并，以获得所需的均摊复杂度。务必记住一旦 |A| = |V| − 1 就可以提前终止。
11. Applications of Kruskal’s Algorithm | 算法应用
Beyond theoretical graph problems, Kruskal's algorithm appears in many real-world systems. It is used in network infrastructure planning – such as laying fibre-optic cables across a city or connecting remote stations with minimum wiring. In computer vision, minimum spanning trees assist in image segmentation. The algorithm also serves as a critical subroutine inside approximation algorithms for the travelling salesman problem (e.g., the Christofides algorithm) and in cluster analysis where it helps construct dendrograms. Its reliance on edge sorting makes it adaptable to distributed systems where edges are naturally streamed in weight order.
除理论图论问题外，克鲁斯卡尔算法在许多实际系统中都有应用。它用于网络基础设施规划——如在城市中铺设光纤电缆，或以最少的布线连接偏远站点。在计算机视觉中，最小生成树帮助进行图像分割。该算法还作为关键子程序应用于旅行商问题的近似算法（如 Christofides 算法），以及在聚类分析中帮助构建谱系图。由于它依赖于边的排序，该算法也易于适配分布式系统，在这些系统中边天然地按权重顺序流式传输。
12. Summary and Exam Tips | 总结与考试技巧
For Edexcel A-Level exams, you should be able to trace Kruskal's algorithm on a small graph, explaining why an edge is rejected, and state the final MST and its total weight. Memorise the key steps: sort edges, initialise disjoint sets, iterate and add if no cycle. Be ready to compare Kruskal with Prim in terms of when each is more suitable. Practice writing pseudocode and discuss the efficiency gained by union–find. Remember to express time complexity as O(E log E) or O(E log V). Students often lose marks by missing the initial singleton sets or forgetting to stop after n−1 edges.
在 Edexcel A-Level 考试中，你应该能在一个小图上跟踪执行克鲁斯卡尔算法，解释某条边为何被拒绝，并给出最终的 MST 及其总权重。牢记关键步骤：排序边、初始化不相交集、遍历边并在无环时加入。准备好比较克鲁斯卡尔与普里姆各自适用于何种场景。练习书写伪代码，并讨论并查集带来的效率提升。记住时间复杂度表述为 O(E log E) 或 O(E log V)。考生常因遗漏初始单元素集合，或在达到 n−1 条边后忘记提前终止而失分。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图