📚 Kruskal's Algorithm for Minimum Spanning Trees | 最小生成树 Kruskal 算法
In A-Level Computer Science, graph optimisation problems often ask for the cheapest way to connect every node in a network: laying fibre-optic cable between towns, wiring components on a circuit board, or linking routers in a subnet. Kruskal's algorithm is a greedy method that builds a minimum spanning tree (MST) by repeatedly adding the lowest-weight edge that does not create a cycle. This revision guide explains the underlying definitions, walks through the algorithm step by step, gives a fully worked trace, justifies why the greedy choice is safe, analyses complexity, compares Kruskal with Prim's algorithm, and highlights the mistakes that cost marks in exams.
在 A-Level 计算机科学中，图优化问题经常要求找到连接网络中所有节点的最便宜方式：在城市之间铺设光缆、在电路板上布线，或在子网中连接路由器。Kruskal 算法是一种贪心方法，它通过反复添加不形成环的最低权重边来构建最小生成树 (MST)。本复习指南将解释相关定义，逐步讲解算法流程，给出完整的示例追踪，论证贪心选择为何安全，分析复杂度，将 Kruskal 与 Prim 算法进行比较，并强调考试中容易失分的常见错误。
1. What Is a Minimum Spanning Tree? | 什么是最小生成树
A spanning tree of a connected graph with V vertices is a connected subgraph that contains all V vertices and exactly V - 1 edges, with no cycles. Because it has V - 1 edges, no cycle, and every vertex, any two vertices are joined by exactly one simple path. If the original graph is weighted, a minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. Note that the MST may not be unique: if two edges share the same weight, several different spanning trees can all achieve the same minimum total.
对于含有 V 个顶点的连通图，生成树是包含全部 V 个顶点、恰好有 V - 1 条边且没有环的连通子图。由于它只有 V - 1 条边、无环且包含所有顶点，任意两个顶点之间有且仅有一条简单路径。如果原图带权，最小生成树 (MST) 就是总边权尽可能小的生成树。需要注意，MST 可能不唯一：如果两条边权重相同，可能存在多棵总权重并列最小的生成树。
If the graph is not connected, no spanning tree exists. Instead, running Kruskal's algorithm to exhaustion produces a minimum spanning forest: one minimum spanning tree for each connected component of the graph. This is a favourite exam extension.
如果图不连通，则不存在生成树。此时把 Kruskal 算法运行到底，得到的是最小生成森林：图的每个连通分量各对应一棵最小生成树。这是考试中常见的延伸考点。
Edges in an MST = V - 1
Total weight = Σ of the chosen edge weights
2. The Core Idea of Kruskal's Algorithm | Kruskal 算法的核心思想
Kruskal's algorithm is edge-based and greedy. It sorts all edges into non-decreasing order of weight, then scans them once. Each vertex starts in its own separate component. For each edge (u, v) in sorted order, the algorithm checks whether u and v currently lie in different components. If they do, adding the edge cannot create a cycle, so the edge is selected and the two components are merged. If u and v are already in the same component, the edge would close a cycle, so it is discarded and never reconsidered.
Kruskal 算法是"基于边"的贪心算法。它先把所有边按权重非递减排序，然后只扫描一遍。初始时每个顶点各自构成一个独立分量。对于排序后的每条边 (u, v)，算法检查 u 与 v 当前是否位于不同分量。如果在不同分量，加入这条边不会形成环，因此选择它并合并两个分量。如果 u 与 v 已在同一分量，这条边会构成环，于是丢弃它，且之后不再重新考虑。
The algorithm terminates when V - 1 edges have been accepted, because at that point the tree is complete. As a safety check for disconnected input, it also terminates when all edges have been scanned.
当已接受 V - 1 条边时算法即可终止，因为此时生成树已完整。为了兼容不连通输入的检查，扫描完全部边时也终止。
Accept edge ⇌ endpoints in different components
Reject edge ⇌ endpoints already connected (cycle)
3. The Disjoint-Set (Union-Find) Structure | 并查集结构
The efficiency of Kruskal's algorithm depends on how quickly we can test "are these two vertices in the same component?" and then merge two components. The standard tool is a disjoint-set structure, also called union-find. Each component has one representative element, and every vertex stores a pointer to its parent; the root of each tree is the representative of that component.
Kruskal 算法的效率取决于两件事有多快：判断"这两个顶点是否在同一分量"，以及合并两个分量。标准工具是并查集 (disjoint-set / union-find)。每个分量有一个代表元素，每个顶点保存指向其父节点的指针；每棵树的根节点就是该分量的代表。
- Find(x): follow parent pointers from x to the root, which identifies x's component. | Find(x)：沿父指针从 x 走到根节点，从而确定 x 所属的分量。
- Union(a, b): attach the root of the smaller tree under the root of the larger one (union by size/rank). | Union(a, b)：把较小子树的根挂到较大子树的根下（按大小/秩合并）。
- Path compression: during Find, re-point visited nodes directly to the root so later queries are faster. | 路径压缩：在 Find 过程中把途经节点直接指向根，使后续查询更快。
With both union by rank and path compression, a sequence of m operations costs about O(m · α(V)), where α is the inverse Ackermann function and is at most 4 for any realistic input. In exam answers it is enough to say the disjoint-set operations are "effectively constant time".
同时使用按秩合并和路径压缩时，m 次操作的总代价约为 O(m · α(V))，其中 α 是反阿克曼函数，对任何现实规模的输入都不超过 4。在考试作答中，写成"并查集操作近似常数时间"即可。
4. Kruskal's Algorithm Step by Step | Kruskal 算法步骤
The whole algorithm can be expressed as a short sequence of steps. Write them in this order in an exam to show clear method.
整个算法可以概括为几个简短步骤。考试中按此顺序书写，可以展示清晰的解题思路。
- Step 1: List every edge with its weight. | 第 1 步：列出每条边及其权重。
- Step 2: Sort the edges into ascending order of weight. | 第 2 步：将边按权重升序排序。
- Step 3: Create one component per vertex (V components, 0 edges chosen). | 第 3 步：为每个顶点建立一个分量（共 V 个分量，已选 0 条边）。
- Step 4: Take the next cheapest edge (u, v). If u and v are in different components, add it to the tree and merge the components; otherwise reject it. | 第 4 步：取下一条最便宜的边 (u, v)。若 u 与 v 分属不同分量，则加入树中并合并分量；否则丢弃。
- Step 5: Repeat Step 4 until V - 1 edges have been chosen or all edges have been examined. | 第 5 步：重复第 4 步，直到已选 V - 1 条边，或所有边都已检查完毕。
- Step 6: Output the selected edges and their total weight. | 第 6 步：输出所选边及其总权重。
A useful sanity check: the number of accepted edges must equal V - 1, and the accepted edges must touch every vertex exactly as a tree does, with no cycle anywhere.
一个有用的自检方法：被接受的边数必须等于 V - 1，并且这些边以树的方式覆盖每个顶点，任何位置都不能出现环。
5. A Complete Worked Trace | 完整示例追踪
D-E 2, E-F 4. There are V = 6 vertices, so a spanning tree needs exactly V - 1 = 5 edges.
考虑一个含六个顶点 A、B、C、D、E、F 的无向带权图，边表如下：A-B 4、A-F 2、B-C 6、B-F 5、C-D 3、C-F 1、D-E 2、E-F 4。这里 V = 6，因此生成树恰好需要 V - 1 = 5 条边。
Sorting by weight gives: C-F 1, A-F 2, D-E 2, C-D 3, E-F 4, A-B 4, B-F 5, B-C 6. Now scan them in order.
按权重排序得：C-F 1、A-F 2、D-E 2、C-D 3、E-F 4、A-B 4、B-F 5、B-C 6。下面按序扫描。
| Edge | 边 | Weight | 权重 | Decision | 判定 | Running total | 累计权重 |
|---|---|---|---|
| C-F | 1 | Accept: different components {C} and {F} | 接受：{C} 与 {F} 属不同分量 | 1 |
| A-F | 2 | Accept: A joins {C, F} | 接受：A 并入 {C, F} | 3 |
| D-E | 2 | Accept: new component {D, E} | 接受：新建分量 {D, E} | 5 |
| C-D | 3 | Accept: merges {A, C, F} with {D, E} | 接受：合并 {A, C, F} 与 {D, E} | 8 |
| E-F | 4 | Reject: cycle E-D-C-F | 丢弃：会形成环 E-D-C-F | 8 |
| A-B | 4 | Accept: B joins the large component | 接受：B 并入大分量 | 12 |
minimum spanning tree is C-F, A-F, D-E, C-D, A-B with total weight 1 + 2 + 2 + 3 + 4 = 12.
接受 A-B 后，树已有 5 条边并覆盖全部 6 个顶点，算法结束，剩余边 B-F 5 与 B-C 6 无需处理。最小生成树为 C-F、A-F、D-E、C-D、A-B，总权重 1 + 2 + 2 + 3 + 4 = 12。
MST weight = 1 + 2 + 2 + 3 + 4 = 12
6. Why the Greedy Choice Is Safe | 贪心选择为何安全
A greedy algorithm is only trustworthy if a locally best choice can never destroy global optimality. The justification for Kruskal's algorithm is the cut property. A cut partitions the vertices into two non-empty sets S and V − S. Any edge with one endpoint in S and the other in V − S is said to cross the cut. The cut property states that, for any cut, a minimum-weight edge crossing that cut belongs to some minimum spanning tree.
只有当局部最优选择不会破坏全局最优性时，贪心算法才可信。Kruskal 算法的依据是切割性质。一个切割把顶点划分为两个非空集合 S 与 V − S。一端在 S、另一端在 V − S 的边称为横跨该切割。切割性质指出：对任意切割，横跨它的最小权重边一定属于某一棵最小生成树。
Now consider the moment Kruskal accepts edge (u, v). At that instant u and v lie in two different components, so the vertex set of u's component defines a cut, and no cheaper edge crosses it (otherwise Kruskal would have processed that cheaper edge first and joined the components earlier). Edge (u, v) is therefore a minimum-weight edge crossing that cut, so it is safe to include. Repeating this argument for every accepted edge shows the final set of V - 1 edges is a minimum spanning tree.
现在考虑 Kruskal 接受边 (u, v) 的那一刻。此时 u 与 v 位于两个不同分量，因此 u 所在分量的顶点集合定义了一个切割，而不存在更便宜的边横跨该切割（否则 Kruskal 会先处理那条更便宜的边，更早把两个分量连通）。因此边 (u, v) 是横跨该切割的最小权重边，加入它是安全的。对每条被接受的边重复这一论证，即可说明最终的 V - 1 条边构成一棵最小生成树。
A second argument is the cycle property: the heaviest edge on any cycle cannot be in a minimum spanning tree, which is exactly why Kruskal rejects an edge whose endpoints are already connected.
第二种论证是回路性质：任意环上权重最大的边不可能属于最小生成树，这正是 Kruskal 丢弃两端点已连通的那条边的原因。
7. Time and Space Complexity | 时间与空间复杂度
Kruskal' at most V - 1 union operations, each of which is effectively constant time with path compression and union by rank. The overall time complexity is therefore O(E log E), which for a simple graph (where E ≤ V²) is also written as O(E log V).
Kruskal 算法的耗时主要由排序决定。设有 E 条边，排序代价为 O(E log E)。之后算法最多执行 E 次查找和最多 V - 1 次合并操作，在使用路径压缩与按秩合并时每次操作近似常数时间。因此总体时间复杂度为 O(E log E)；对于简单图（E ≤ V²），也可写作 O(E log V)。
| Aspect | 项目 | Cost | 代价 |
|---|---|
| Sorting the edges | 边排序 | O(E log E) |
| Disjoint-set operations | 并查集操作 | O(E · α(V)), effectively O(E) |
| Total time | 总时间复杂度 | O(E log E) |
| Space | 空间复杂度 | O(V + E) |
The space cost stores the edge list, the parent array of size V, and the output tree of V - 1 edges. If the input graph is given as an adjacency matrix instead of an edge list, converting it to a list of edges costs O(V²) time and space before sorting begins.
空间上需要存储边表、规模为 V 的父节点数组，以及含 V - 1 条边的输出树。如果输入图以邻接矩阵而非边表给出，则在开始排序之前，转换为边表需要 O(V²) 的时间和空间。
8. Kruskal vs Prim: Which to Use | Kruskal 与 Prim 的对比
Prim's algorithm also finds a minimum spanning tree, but it grows a single tree from a chosen start vertex, repeatedly adding the cheapest edge that connects a vertex already in the tree to a vertex outside it. Kruskal, by contrast, works globally across the whole edge list and can maintain several partial forests at once.
Prim 算法同样用于求最小生成树，但它从选定的起始顶点开始生长一棵树，反复加入连接"树内顶点"与"树外顶点"的最便宜边。相比之下，Kruskal 在整个边表上全局操作，可能同时维护多个部分森林。
| Feature | 比较项 | Kruskal | Kruskal | Prim | Prim |
|---|---|---|
| Grows | 生长方式 | Many components merging | 多个分量合并 | One tree from a start vertex | 从起点扩展一棵树 |
| Main data structure | 主要数据结构 | Sorted edge list + union-find | 排序边表 + 并查集 | Priority queue + visited set | 优先队列 + 已访问集合 |
| Time complexity | 时间复杂度 | O(E log E) | O(E log V) with a binary heap |
| Best for | 更适合 | Sparse graphs, given as edge lists | 稀疏图，且以边表给出 | Dense graphs, given as a matrix | 稠密图，且以矩阵给出 |
| Disconnected input | 不连通输入 | Produces a spanning forest | 产生生成森林 | Covers only the start component | 只能覆盖起始分量 |
Both algorithms give a minimum spanning tree of the same total weight when the MST is unique; when ties exist, they may return different trees of equal weight. This is a very common comparison question, so learn one concrete example where the two produce different edge sets.
当 MST 唯一时，两种算法得到总权重相同的最小生成树；存在等权边时，它们可能返回边集不同但总权重相等的树。这是极常见的比较题，建议准备一个两者结果不同的具体例子。
9. Sparse Graphs, Dense Graphs and Edge Cases | 稀疏图、稠密图与边界情况
Because Kruskal's cost depends on E log E and Prim's on E log V, the choice depends on how many edges the graph has. A sparse graph has E close to V, so E log E is modest and sorting is cheap. A dense graph has E close to V², so Kruskal must sort a very large list while Prim can work from an adjacency matrix in O(V²) time without sorting at all.
由于 Kruskal 的代价取决于 E log E，而 Prim 的取决于 E log V，选择哪种算法取决于图的边数。稀疏图的 E 接近 V，E log E 不大，排序成本低。稠密图的 E 接近 V²，Kruskal 需要排序一张极大的列表，而 Prim 可以直接在邻接矩阵上以 O(V²) 时间运行，完全无需排序。
Several edge cases are worth memorising. Negative edge weights are fine for Kruskal, because the algorithm only compares weights and never sums them along a path. Self-loops are always rejected, since a vertex is trivially in its own component. Parallel edges between the same pair of vertices are handled naturally: only the cheaper one can be accepted. And if the graph is disconnected, fewer than V - 1 edges will be accepted and the result is a forest.
有几个边界情况值得记住。负权边对 Kruskal 没有影响，因为算法只比较权重，从不沿路径累加权重。自环总是被丢弃，因为顶点显然与自身处在同一分量。同一对顶点之间的平行边也能自然处理：只有较便宜的那条可能被接受。如果图不连通，被接受的边会少于 V - 1 条，结果是生成森林。
10. Writing the Answer in an Exam | 考试作答规范
Examiners award marks for method, not just for the final tree. To maximise marks, show the sorted edge list first, then draw or list the accepted edges in the order they were chosen, and state the total weight as an explicit sum of the individual weights. If a question asks which edges you would not choose, name them and give a one-line reason such as "would form a cycle B-C-F".
考官给分看的是方法，而不只是最终的树。为拿到最高分，应先写出排序后的边表，再按被选中的顺序画出或列出接受的边，并把总权重写成各条边权重相加的明确式子。如果题目问哪些边不会被选，应写出这些边并给出一句话理由，例如"会形成环 B-C-F"。
- State V and check that your answer has exactly V - 1 edges. | 写出 V 的取值，并检查答案是否恰好有 V - 1 条边。
- Show the sorted list; unsorted reasoning usually loses the ordering mark. |
广告 / Sponsored现货 Cambridge International AS & ALevel IT Coursebook剑桥国际IGC…计算机 备考教辅 · 正版现货 · 与本文内容相关查看详情 / View on Taobao参考价 ¥467.0
更多咨询请联系16621398022（同微信）
备考资讯每日更新，关注不错过考纲变化 · 科目分析 · 学习方法
在微信里长按二维码识别关注
或截图后用「扫一扫 → 相册」选择本图公众号：tutorhao