图系列第 12 篇：最小生成树——Kruskal 与 Prim

开场：把前面的知识串起来

欢迎来到图系列第 12 篇。在前面十一篇文章里，我们已经把图的存储、遍历、拓扑排序、单源最短路和多源最短路都系统地走了一遍。今天要解决的是一个全新的问题：怎样用总代价最小的边把所有点连成一张网？ 这个问题的答案叫最小生成树（Minimum Spanning Tree，简称 MST），今天的主角是两位大名鼎鼎的贪心算法——Kruskal 和 Prim。

在正式开始之前，先把前置知识串一遍。图系列第 2 篇讲过生成树的概念：一棵生成树是包含图中全部 n 个顶点、恰好 n-1 条边的无环连通子图；这篇我们还复习过「树是边数最少的连通图」。图系列第 3 篇讲过图的存储：邻接表和边数组（边集），今天两种存储方式都会用到——Kruskal 天然喜欢边数组，Prim 天然喜欢邻接表。树系列第 18 篇讲的并查集（Union-Find）是 Kruskal 的发动机，它能在近乎常数的时间内回答「两个点当前是否已经连通」。树系列第 16 篇讲的小根堆（优先队列）是 Prim 的核心数据结构，它负责在每一次扩张时快速找出当前最便宜的一条候选边。

如果你对上面这些内容印象已经模糊，也不用担心。本篇会在用到的地方把最小必要的细节重新讲一遍，保证你能直接读懂。整篇文章真正要传达的重点只有一个：贪心在这里为什么是对的？ 很多同学背得下 Kruskal 的排序和 Prim 的优先队列，却说不清它们为什么不会选错。读完本篇，你会用一条「切分定理」把两个算法统一起来：它们内里其实是同一句话。

flowchart TD
    A["图系列第 2 篇：生成树与连通性"] --> D["最小生成树：n 个点选 n-1 条边，总权最小"]
    B["图系列第 3 篇：邻接表与边集存储"] --> D
    C["树系列第 18 篇：并查集"] --> E["Kruskal：边贪心 + 并查集判环"]
    F["树系列第 16 篇：小根堆 / 优先队列"] --> G["Prim：点贪心 + 优先队列挑边"]
    D --> E
    D --> G

另外说一句阅读建议：本篇内容多、走查细，建议准备一张纸一支笔。Kruskal 和 Prim 的每一步我们都会带着并查集 parent 表、候选边列表走一遍；你跟着在纸上同步画，会比单纯读文字深刻得多。下面我们开始。

动笔之前，先把全文的术语约定说清楚，避免后面产生歧义：

• 顶点数用 n 表示，边数用 m 表示。 本篇所有复杂度都写在这两个记号上，例如 O(m log m)。
• 权重 w(e) 默认非负。 现实中距离、造价、时间都是非负的；负权在 MST 里其实也能处理，第六节会专门提一句。
• 切分：把顶点集 V 分成两个非空子集 S 和 V-S，叫做一个切分；跨堆边指一个端点在 S、另一个端点在 V-S 的边。
• 生成树：连通且无环，包含全部 n 个顶点，恰好 n-1 条边。
• MST 边集：我们说的「选中边」在算法过程中会逐渐变化，但每一步都是某个合法森林；算法结束时的选中边集就是 MST。

全文的路线图是：先明确问题（第一节）→ 讲透切分定理（第二节）→ Kruskal 完整走查与证明（第三节）→ Prim 完整走查与证明（第四节）→ 对比与选择（第五节）→ 应用（第六节）→ 速查表与自测（第七节）。每一节都建立在前一节之上，建议顺序阅读。

一、问题：用最少的线连通所有点

1.1 三个真实场景

场景一：网络布线。公司搬进新办公室，有 n 台设备需要互相通信。工程师要拉网线：从交换机到交换机、从交换机到设备，每根网线的造价各不相同（取决于长度、穿墙难度、走线路径等）。目标是让所有设备之间都能互相通信——注意，不要求每两台设备都直接相连，中间通过其它设备中转完全可以接受——并且总造价最低。如果每两台设备之间都拉一根线，要拉 C(n,2) 根，成本爆炸；我们需要的是一张「恰好连通、尽量便宜」的网络。

场景二：公路建设。n 个村庄之间可以修路，任意两个村庄之间修路的造价可能差别很大：平原便宜，山区贵，遇到河流更贵。政府预算有限，希望用最少的钱让所有村庄互通。这个问题几乎和网线布线一模一样，只是把「设备」换成了「村庄」。

场景三：集群划分（先埋一个伏笔）。假设平面上散落着 n 个点，我们希望把它们分成若干个簇，让簇内点距离近、簇间点距离远。一个经典做法是：先求最小生成树，再删掉树上最长的几条边，剩下的连通块自然就是簇。为什么这个做法合理？本篇第六节会专门展开。现在先记住一句话：MST 与聚类之间有天然联系，因为最小生成树本质上就是在「尽量用短边把点粘在一起」。

1.2 形式化：最小生成树问题

把上面的场景抽象成图论语言。给定一张无向连通图 G = (V, E)，每条边 e 有一个权重 w(e)（现实中是距离、造价等，通常非负）。我们要选出一个边集 T ⊆ E，满足两个条件：

1. T 覆盖并连通所有顶点；
2. T 的总权重 ∑ w(e) 在所有满足条件 1 的边集中最小。

满足条件的 T 就是一棵最小生成树。注意关键词：无向、连通、带权。如果图本身不连通，任何边集都不可能连通所有顶点，此时不存在严格意义上的生成树；算法退而求其次，求的是「最小生成森林」——每个连通分量一棵树，后面我们会提到这一点。

1.3 为什么最优解一定是树

这是整篇文章的第一个关键结论：最优解一定是一棵生成树，不多不少 n-1 条边。 分两层理解：

第一层，少于 n-1 条边不可能连通。这是树系列的基础结论：n 个顶点的连通图至少有 n-1 条边；少于这个数，边数不足以把所有点「串」起来，必然存在两个点之间没有路径。所以任何合法方案都至少需要 n-1 条边。

第二层，多于 n-1 条边一定可以删掉一条。如果边集里出现了环，环上任意删掉一条边，图的连通性不会改变——环本来就不提供「额外的连通能力」。删掉后总权重下降（权重非负时至少不上升），所以最优解里不可能有环。

把两层合起来：最优解连通、无环、边数恰好 n-1，这正是生成树的定义。这个结论非常重要，因为它把搜索范围从「任意边集」缩小到了「生成树集合」，而且告诉我们：一旦选够了 n-1 条边且无环，就可以停下来了。

1.4 为什么不能暴力枚举

既然问题是在所有生成树里找总权最小的一棵，那能不能把所有生成树列出来比较？不行。n 个顶点的完全图有 n^(n-2) 棵生成树（这是著名的 Cayley 公式），对 n=10 就有 10^8 量级，n=20 已经超过 10^20，宇宙毁灭也算不完。更一般地说，从 m 条边里选 n-1 条的组合数是 C(m, n-1)，同样是天文数字。最小生成树问题需要多项式算法——今天要讲的两个算法都是 O(m log m) 级别的，在大规模图上跑起来飞快。

顺便说一点历史：最小生成树问题可能是最早被系统研究的图论问题之一。捷克数学家 Borůvka 在 1926 年为了解决摩拉维亚电网的布线问题提出了第一个算法；随后 Jarník 在 1930 年、Kruskal 在 1956 年、Prim 在 1957 年分别独立提出了其它算法。我们只讲其中流传最广、最好写的两个：Kruskal 和 Prim。

1.5 贯穿全文的例子

为了后面走查方便，本篇固定使用同一张图。它有 6 个顶点 A、B、C、D、E、F 和 9 条带权无向边：

边	权重
A-B	4
A-C	2
B-C	1
B-D	5
C-D	8
C-E	10
D-E	2
D-F	6
E-F	3

整张图画出来长这样（边上的数字是权重）：

flowchart LR
    A((A)) ---|4| B((B))
    A ---|2| C((C))
    B ---|1| C
    B ---|5| D((D))
    C ---|8| D
    C ---|10| E((E))
    D ---|2| E
    D ---|6| F((F))
    E ---|3| F

先剧透答案：这棵图的最小生成树总权重是 13，由边 B-C(1)、A-C(2)、D-E(2)、E-F(3)、B-D(5) 组成。你现在可以自己先找一找、算一算，然后我们分别用 Kruskal 和 Prim 完整走一遍，看看两个算法如何殊途同归地得到 13。

1.6 两个容易混淆的邻居问题

第一次接触 MST 的人很容易把它和另外两个问题弄混，这里提前划清界限。

第一个邻居是「最短路问题」。最短路关心的是某两个点之间的代价，即使全图最短路树已经连成一片，它也不保证总连通代价最小；反过来，MST 的总代价最小，但树上任意两点的路径不一定最短。打个比方：最短路像「打车 App 给你规划一条从家到公司的最近路线」，MST 像「市政部门决定修哪些路、让全城连通且总预算最小」。两个目标不同，算法也不同。

第二个邻居是「最小斯坦纳树」（Steiner Tree）问题：允许额外引入一些不在原图中的辅助点，来进一步降低连通代价。比如三个城市构成等边三角形，直接连三条边的总长是 3a，但如果允许在三角形中心建一个枢纽，再向三个城市各拉一条线，总长只有约 2.6a。MST 不允许引入新点，所以它是最小斯坦纳树的一种受限版本；后者是 NP 难问题，而 MST 有多项式算法——这是「允许的自由度」带来的巨大复杂度差距。

第三个邻居是「有向图版本」：如果边有方向，连通所有点的问题变成「从某个根能到达所有点」或「所有点互相可达」，前者叫最小树形图（有向 MST），后者根本没有简单的树形解。本篇只处理无向图，方向问题留给第 13 篇强连通分量打底。

1.7 权重与连通性：几个被默认的细节

如果所有权重都是 1。 任何生成树都有 n-1 条边、总权 n-1，所有生成树都是 MST。此时 Kruskal 和 Prim 依然正确，但结果没有区分度。这提醒我们：MST 的意义来自权重的差异——权重差异越大，算法选边的取舍越有信息量。

如果权重允许为负。 MST 的定义依然成立，两个算法也不需要任何修改。直观理解：树必须恰好 n-1 条边，负权只会让你更想选某些边，但「不成环」的约束不变。所以 Kruskal 和 Prim 都天然支持负权，这与最短路算法（Dijkstra 怕负权）形成有趣的对比。

图不连通怎么办。 本篇大多数讨论假设输入连通。如果输入不连通，Kruskal 自然输出最小生成森林（每个连通分量一棵树），Prim 一次只长出一个分量。工程上经常遇到不连通输入，所以这个边界情况不是「题目刁难」，而是真实需求。

权重相同怎么办。 整数、浮点、甚至字符串权重都行，只要可比较。但「可比较」和「稳定」是两回事：多条边同权时，MST 可能不唯一，输出顺序可能因排序稳定性而不同。5.4 节会详细展开唯一性问题。

稠密与稀疏的直觉。 完全图有 m = n(n-1)/2 条边；树有 n-1 条边；真实网络通常介于两者之间，但往往更接近稀疏。比如一个城市的道路图，平均每个路口只连 3-4 条路。记住「m ≈ n 稀疏，m ≈ n² 稠密」这个尺度感，后面选算法时才不会纠结。

1.8 怎么确认自己写对了：对拍与暴力验证

学算法最容易出现的情况是「写出来感觉对，一提交就错」。MST 的两个算法都不长，但正好适合用对拍（随机数据 + 暴力答案对比）来验证。方法很简单：

1. 写一个暴力求解器：枚举所有含 n-1 条边的无环子图（n 很小时可行，比如 n ≤ 7），取总权最小者；
2. 生成随机小图：随机 n、随机边权（0 到某个上限），保证连通；
3. 让暴力求解器、Kruskal、Prim 三个程序分别跑同一组数据，断言总权全部相等；
4. 一旦发现不一致，把触发数据缩到最小，逐行调试。

对拍的价值在于：它不检查「选边集合是否一致」（等权时本来就可能不同），只检查总权是否一致——这正是 MST 定义里唯一硬性的指标。做上一两百轮随机测试，并查集的写法、堆的比较器方向、惰性删除是否漏写，都会被暴露出来。图系列一直建议的对拍习惯，在 MST 上尤其好用，因为暴力求解器只要十几行。

另一个轻量验证是切分定理抽查：随便选一个切分，断言 MST 里跨堆边的最小权等于全局跨堆边的最小权——不对就说明你的「MST」根本不是 MST。这条性质比总权相等更容易定位错误边。

二、切分定理：两个算法的共同根基

2.1 一个极其简单的直觉

在介绍两个算法之前，先讲一条贯穿全文的定理。它非常简单，但力量巨大，是整个最小生成树理论的基石。这条定理叫切分定理（Cut Property，也叫割定理、切割性质）。

先把图的所有顶点任意分成两堆 S 和 V-S，两堆都非空。想象一下：S 这边是一个国家，V-S 那边是另一个国家。要让整张图连通，两个国家之间必须至少修一条路——否则两边的人永远无法往来。现在，跨在两堆之间的所有边里，最便宜的那条，值不值得选？直觉给出的答案非常干脆：值得。

为什么？因为不管你最后建成什么样的连通网络，两个国家之间总得至少有一条路。与其选一条贵的跨堆边，不如选这条最便宜的。随便拿一个最终方案出来，把方案里任意一条跨堆边换成这条最便宜的跨堆边，连通性不会变差（两个国家之间仍然有路），而总造价只会更低。所以，最便宜的跨堆边不可能被「所有」最优方案排除在外。

这个直觉就是切分定理的内容。用规范的话说：把顶点集 V 任意分成两个非空集合 S 和 V-S，令 e 是所有跨堆边（一个端点在 S、另一个端点在 V-S）中权重最小的一条，那么一定存在一棵包含 e 的最小生成树。

2.2 配图理解

拿我们贯穿全文的例子来说。把顶点分成 S = {A, B, C} 和 V-S = {D, E, F} 两堆。S 内部有 A-B、A-C、B-C 三条边；V-S 内部有 D-E、E-F、D-F 三条边；跨在两堆之间的边有三条：B-D(5)、C-D(8)、C-E(10)。

flowchart LR
    subgraph S["切分 S = {A, B, C}"]
        A((A)) ---|4| B((B))
        A ---|2| C((C))
        B ---|1| C
    end
    subgraph T["切分另一侧 V-S = {D, E, F}"]
        D((D)) ---|2| E((E))
        E ---|3| F((F))
        D ---|6| F
    end
    B ---|5| D
    C ---|8| D
    C ---|10| E

跨堆边里最小的是 B-D，权重 5。切分定理告诉我们：存在一棵 MST 包含 B-D 这条边。 事实也确实如此——前面剧透的 MST 边集 {B-C, A-C, D-E, E-F, B-D} 里正好有 B-D。你可以试试换一种切分，比如 S = {A, B, D}，V-S = {C, E, F}，跨堆边有 A-C(2)、B-C(1)、C-D(8)、D-E(2)、D-F(6)。最小的是 B-C(1)，它同样出现在 MST 里。每试一次，你都会发现定理「算得准」。

2.3 证明：一次漂亮的交换论证

直觉再强，也得有证明。切分定理的证明是图论里最经典的「交换论证」（exchange argument）之一，请务必看懂，因为 Kruskal 和 Prim 的正确性证明都是它的变体。

任取一棵最小生成树 T。分两种情况：

情况一：e 本来就在 T 里。那结论已经成立，无事可做。

情况二：e 不在 T 里。这是核心。把 e 加入 T，得到一个 T ∪ {e}。树有一个著名性质：在树上任意加一条不在树里的边，会恰好形成一个环（因为 T 中 e 的两个端点 u、v 之间本来就有一条唯一路径，加上 e 后这条路就变成了环）。记这个环为 C。

现在观察这个环和切分的关系。e 的两个端点一个在 S、一个在 V-S，所以环 C 从 S 出发、跨到 V-S、最终还要回到 S 才能闭合。这意味着环上除了 e 之外，必然还至少有一条边 f 也是跨堆的（如果环上只有 e 这一条跨堆边，那环从 S 走到 V-S 后就再也回不到 S 了，不可能闭合）。

因为 e 是跨堆边里权重最小的，所以 w(f) ≥ w(e)。现在做一次交换：构造 T’ = T − {f} + {e}，把 f 从树上拿掉，把 e 放上去。

第一步确认 T’ 还是一棵树。T 是一棵树，加 e 形成唯一环 C，删掉环上的 f 恰好破坏这个环；T’ 依然连通、无环，边数还是 n-1，所以它是一棵生成树。

第二步比较总权重。w(T’) = w(T) − w(f) + w(e) ≤ w(T)。而 T 已经是最小生成树，T’ 的权重不可能比它更小，于是只能有 w(T’) = w(T)。所以 T’ 也是一棵最小生成树，而且它包含 e。

证毕。顺带收获一个推论：在上面的论证里，如果 w(f) > w(e)，那么 T’ 的权重严格小于 T，直接与 T 是最小生成树矛盾。因此在 MST 里，环上与 e 相对的跨堆边 f 必然满足 w(f) = w(e)。这个推论在讨论「MST 何时唯一」时会派上用场。

2.4 常见误区

切分定理表述简短，但非常容易用错，列出三个最常见的误区：

误区一：把「存在一棵 MST 包含 e」理解成「所有 MST 都包含 e」。这是错的。定理只保证存在性。只有当 e 是跨堆边中唯一的最小边（严格小于其它所有跨堆边）时，才能推出每棵 MST 都包含 e。想想就知道：如果跨堆边里有两条权重相同的边 e1、e2，选 e1 或选 e2 可能都能构成 MST，那 e1 就不在「所有」MST 里。

误区二：以为某条边只要在某个切分里是最小的，就必须选它。请记住，切分定理是一个「充分条件」而不是「必要条件」：不满足条件的边也可能出现在 MST 里。它说「选它不亏」，没说「不选它就错」。

误区三：以为切分只能是静态的。实际上切分可以是任意的，特别包括算法运行过程中动态出现的切分，比如「当前已选边形成的某个连通块 vs 其余所有点」。这正是两个贪心算法每一步都能安全决策的钥匙。

2.5 两个算法原来是同一句话

把切分定理放在心里，再看 Kruskal 和 Prim，你会发现它们的正确性骨架一模一样：

• Kruskal 的每一步：按权重从小到大考察边 (u, v)。如果 u、v 当前不在同一个连通块里，把 u 所在连通块 S 和其余顶点 V-S 看成切分。此刻 (u, v) 就是跨堆边里最小的——因为所有权重比它小的跨堆边都已经被考察过，要么被选中（那 u、v 就已经连通了）、要么因为两端已在同一连通块而被跳过（那它根本就不是跨堆边）。于是切分定理保证：选它，一定可以扩展到某棵 MST。

• Prim 的每一步：已经长出的树内集合 S 和树外集合 V-S 天然构成一个切分。Prim 用优先队列找出跨堆边里的最小值，同样由切分定理保证正确。

所以，尽管 Kruskal 表面上是「边排序贪心」，Prim 表面上是「点扩张贪心」，它们内里是同一句口诀：永远选择当前某个切分的最小跨堆边。 后面两节我们把这句话分别翻译成可运行的代码。

flowchart TD
    C["切分定理：任意切分的最小跨堆边一定属于某棵 MST"] --> K["Kruskal：每次考察的合法边 = 当前切分的最小跨堆边"]
    C --> P["Prim：每次扩张的候选边 = 树内外切分的最小跨堆边"]
    K --> R["结论：两个贪心算法都不需要回溯"]
    P --> R

2.6 切分定理的实战练习：用它找 MST 边

切分定理不只是证明工具，它还能直接指导人工求 MST：每次找一个切分，把最小跨堆边钉进答案，重复直到选满 n-1 条边。拿一个小例子练手：四个点 A、B、C、D，五条边 A-B(1)、A-C(4)、A-D(3)、B-C(2)、C-D(5)。

flowchart LR
    A((A)) ---|1| B((B))
    A ---|4| C((C))
    A ---|3| D((D))
    B ---|2| C
    C ---|5| D

第一步，选切分 S = {A}，V-S = {B, C, D}。跨堆边是 A-B(1)、A-C(4)、A-D(3)，最小的是 A-B(1)，钉进答案。

第二步，选切分 S = {A, B}，V-S = {C, D}。跨堆边是 A-C(4)、B-C(2)、A-D(3)，最小的是 B-C(2)，钉进答案。

第三步，选切分 S = {A, B, C}，V-S = {D}。跨堆边是 A-D(3)、C-D(5)，最小的是 A-D(3)，钉进答案。

三刀切完，选中的边 {A-B, B-C, A-D} 总权 1+2+3=6，恰好就是 MST。注意每次切分都是「当前已确定连通块 vs 其余」——这其实就是 Prim 的人工版。你也可以试试别的切分顺序，比如先切 {C} vs {A,B,D}：跨堆边 A-C(4)、B-C(2)、C-D(5)，最小 B-C(2)，同样能推进。切分的顺序和选择不影响最终结果，这正是切分定理比「灵机一动」可靠的地方。

还有一个逆向用法：如果想快速判断某条边 e 是不是「每棵 MST 都必须包含」，可以寻找一个切分，使得 e 是跨堆边里唯一的最小边。能找到这样的切分，e 就必然在每棵 MST 里；找不到，e 仍然可能在部分 MST 里，但无法用这个条件断定。这种「用切分给边贴标签」的技巧在次小生成树和敏感性分析里非常有用。

三、Kruskal：把边按权重从小到大慢慢挑

3.1 核心思想

Kruskal 的思想一句话就能说清楚：把所有的边按权重从小到大排序，然后一条一条看，能选就选，不能选就跳过。 这里的「能选」是指：这条边连接的两个顶点目前还没有被已经选中的边连通——如果已经连通，加上它就会形成环，选了必然多余。

把它拆成三个动作：

1. 排序：把 m 条边按 w(e) 从小到大排好。
2. 判环：维护一个并查集，记录「已经选中的边把哪些点连成了一块」。对当前边 (u, v)，查 u 和 v 是否在同一集合：不在同一集合 → 选它；在同一集合 → 它会形成环，跳过。
3. 合并：选了一条边后，把 u、v 所在的两个集合合并，表示它们从此连通。

为什么从小到大？道理朴素得可爱：便宜的机会要优先抓住。如果一条便宜的边现在不选，将来两个端点被别的路径连通了，这条边就永远没有机会了；而如果它现在被选，即使后面发现更好的组合，MST 的「可选空间」也不会因此变差——这一点切分定理已经替我们做了担保。贪心的怀疑者一定会问：万一先选了便宜边，把后面更重要的便宜机会堵死了怎么办？这正是本篇要解决的疑问，3.5 节我们用切分定理给出严格答案。

3.2 并查集：判环的利器

回顾树系列第 18 篇的内容。并查集维护若干个不相交集合，支持两个操作：

• find(x)：返回 x 所在集合的代表元素（根）。
• union(x, y)：把 x、y 所在的两个集合合并。

判环只需要一行判断：find(u) === find(v)。如果相同，说明 u、v 已经通过已选边连通，再加 (u, v) 必然形成环。

为了让 find 足够快，通常加上两个优化：路径压缩（find 时把沿途节点直接挂到根上）和按秩合并（小树挂到大树上）。加上这两个优化后，并查集单次操作的均摊复杂度是反阿克曼函数 α(n)，在一切实际规模下都可以看成常数。所以 Kruskal 的总复杂度几乎完全由排序决定。

下面给出一个精简的并查集实现，稍后 Kruskal 主函数直接使用它：

class DisjointSet {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
  }

  find(x) {
    // 路径压缩：沿着父链找到根，并把沿途节点直接挂到根下
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }

  union(a, b) {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra === rb) return false; // 已经连通，说明这条边会形成环
    // 按大小合并：小树挂到大树上，控制树高
    if (this.size[ra] < this.size[rb]) {
      this.parent[ra] = rb;
      this.size[rb] += this.size[ra];
    } else {
      this.parent[rb] = ra;
      this.size[ra] += this.size[rb];
    }
    return true;
  }
}

注意 union 返回布尔值：合并成功返回 true，说明两个点之前不连通、这条边可以选；返回 false 说明它们已经连通、这条边会形成环。这个返回值让主函数写起来非常干净。

3.3 完整走查：一图走到底

理论说得再多，不如亲手走一遍。回到我们贯穿全文的那张图。先把 9 条边按权重从小到大排好：

顺序	边	权重
1	B-C	1
2	A-C	2
3	D-E	2
4	E-F	3
5	A-B	4
6	B-D	5
7	D-F	6
8	C-D	8
9	C-E	10

权重相同（A-C 和 D-E 都是 2）时顺序随意，这里按字母序排。我们规定初始时每个点自己一个集合：{A}、{B}、{C}、{D}、{E}、{F}。接下来一步一步走。

第 1 步：边 B-C，权重 1。 B 和 C 不在同一集合，选中。当前选中边：{B-C}，总权 1。连通块变成：{A}、{B, C}、{D}、{E}、{F}。

第 2 步：边 A-C，权重 2。 A 和 C 不在同一集合（A 自己一块，C 在 {B, C} 里），选中。当前选中边：{B-C, A-C}，总权 1+2=3。连通块：{A, B, C}、{D}、{E}、{F}。

第 3 步：边 D-E，权重 2。 D 和 E 不在同一集合，选中。当前选中边：{B-C, A-C, D-E}，总权 5。连通块：{A, B, C}、{D, E}、{F}。

第 4 步：边 E-F，权重 3。 E 在 {D, E}，F 自己一块，不在同一集合，选中。当前选中边：{B-C, A-C, D-E, E-F}，总权 8。连通块：{A, B, C}、{D, E, F}。

到这里，图被分成了两大块，中间还差一座桥。看第 5 步。

第 5 步：边 A-B，权重 4。 A 和 B 现在都在 {A, B, C} 里——已经在第 1、2 步被 B-C 和 A-C 连起来了。加 A-B 会形成 A-B-C-A 这个环，所以跳过。这是 Kruskal 第一次展示「判环」的威力：虽然 A-B 权重不大，但它属于多余的一根线。

第 6 步：边 B-D，权重 5。 B 在 {A, B, C}，D 在 {D, E, F}，不在同一集合，选中。这是两块之间的第一座桥，也是整个算法最关键的一步。当前选中边：{B-C, A-C, D-E, E-F, B-D}，总权 13。至此 6 个点全部连通，已经选够 n-1 = 5 条边，可以提前结束。

后面三条边 D-F(6)、C-D(8)、C-E(10) 如果继续考察，会发现两端都已经连通，全部跳过。算法结束，MST 总权 13，和我们 1.5 节剧透的一致。

把全过程汇总成一张决策表：

步骤	边(权重)	两端已连通?	动作	选中边集合	总权
1	B-C(1)	否	选	{B-C}	1
2	A-C(2)	否	选	{B-C, A-C}	3
3	D-E(2)	否	选	{B-C, A-C, D-E}	5
4	E-F(3)	否	选	{B-C, A-C, D-E, E-F}	8
5	A-B(4)	是（A、B 已被 B-C、A-C 连通）	跳过	同上	8
6	B-D(5)	否	选	{B-C, A-C, D-E, E-F, B-D}	13
7	D-F(6)	是	跳过	同上	13
8	C-D(8)	是	跳过	同上	13
9	C-E(10)	是	跳过	同上	13

3.4 配图：并查集状态与树的生长

光看表还不够，我们用图把「树的生长」和「并查集 parent 的变化」分别展示出来。

前两步之后，选中的边是 B-C 和 A-C，形成一棵以 A、B、C 为中心的小树：

flowchart LR
    A((A)) ---|2| C((C))
    C ---|1| B((B))
    D((D))
    E((E))
    F((F))

第 4 步之后，右边也长出了一棵小树 D-E-F：

flowchart LR
    A((A)) ---|2| C((C))
    C ---|1| B((B))
    D((D)) ---|2| E((E))
    E ---|3| F((F))

第 6 步之后，B-D 这座桥把两棵树拼成一整棵 MST：

flowchart LR
    A((A)) ---|2| C((C))
    C ---|1| B((B))
    B ---|5| D((D))
    D ---|2| E((E))
    E ---|3| F((F))

再看并查集内部。以「把较小的集合挂到较大的集合下」为合并规则，每一步之后 parent 数组长这样（箭头表示 parent 指向）：

时刻	parent[A]	parent[B]	parent[C]	parent[D]	parent[E]	parent[F]	集合根
初始	A	B	C	D	E	F	A, B, C, D, E, F
选 B-C 后	A	B	B	D	E	F	A, B, D, E, F
选 A-C 后	A	A	B	D	E	F	A, D, E, F
选 D-E 后	A	A	B	D	D	F	A, D, F
选 E-F 后	A	A	B	D	D	D	A, D
选 B-D 后	A	A	B	D	D	D	A

注意最后一行：parent[D] 仍然是 D，D 是右侧子树的根；真正把两个集合合并的是 union 时把 A 的根和 D 的根连在一起——我们这里的合并规则是「大的挂小的」还是「小的挂大的」，取决于 size。实际代码中 union(B, D) 会把 size 较小的树根挂到较大的树根下，上面的表展示的是「逻辑集合」而非每次的具体挂法，读者只需抓住一点：parent 表永远在回答「每个点属于哪个根」。用 find 查 B 会得到 A，查 F 会得到 D，而最终 union 后 B 和 F 的根都归一到同一个根上。

把最终并查集结构画成森林图，长这样：

flowchart TD
    A((A)) --> B2((B))
    B2 --> C2((C))
    D2((D)) --> E2((E))
    D2 --> F2((F))
    A -. 合并后同根 .- D2

3.5 一个值得停下来想的问题

第 5 步我们跳过了 A-B(4)，理由是它会形成环。有人可能会问：环 A-B-C-A 里明明有更贵的边吗？没有，环里是 B-C(1)、A-C(2)、A-B(4)，A-B 是环里最贵的。删掉最贵的边、保留便宜的两条，这正是 MST 的逻辑。如果反过来问：假设 A-B 的权重不是 4 而是 0.5，会发生什么？排序后 A-B 会排到最前面，第 1 步就选中它，之后 A-C(2)、B-C(1) 里只会选一条，另一条被跳过，MST 的边集和总权都会不同——但算法依然正确。这提醒我们：边权的大小顺序改变了「谁先被考虑」，但算法本身不挑食，任何图都能处理。

还有一层值得体会：Kruskal 在选第 6 步 B-D 之前，并不知道自己最终要选 5 条边；它只是忠实执行「从小到大，能选就选」。前面四步选出的两条小树，恰好为 B-D 成为桥做好了铺垫。整个过程中没有一步回头，也没有一步后悔——贪心的魅力就在于此。

3.6 Kruskal 的完整代码

把 3.2 节的 DisjointSet 和主函数拼在一起，Kruskal 的 TypeScript 实现大约 40 行：

interface Edge {
  u: number; // 端点 1
  v: number; // 端点 2
  w: number; // 权重
}

function kruskal(n: number, edges: Edge[]): { total: number; mst: Edge[] } {
  // 1. 所有边按权重从小到大排序（权重相同顺序任意）
  const sorted = [...edges].sort((a, b) => a.w - b.w);

  const dsu = new DisjointSet(n);
  const mst: Edge[] = [];
  let total = 0;

  for (const e of sorted) {
    // 2. 判环：两端已连通则跳过
    if (dsu.union(e.u, e.v)) {
      // 3. 选中这条边，并合并两个集合
      mst.push(e);
      total += e.w;
      // 提前终止：n 个点的树只需要 n-1 条边
      if (mst.length === n - 1) break;
    }
  }

  return { total, mst };
}

代码里最关键的一行是 dsu.union(e.u, e.v)：它同时完成了「判环」和「合并」两件事。union 返回 true 时这条边被选入 MST；返回 false 时跳过。mst.length === n - 1 的提前终止是可选的优化——当图连通时，选够 n-1 条边就一定已经是一棵生成树，后面不可能再选中任何边。

如果把顶点编号从 0 到 n-1，那么对 1.5 节的例子，调用方式是这样：

const edges: Edge[] = [
  { u: 0, v: 1, w: 4 }, // A-B
  { u: 0, v: 2, w: 2 }, // A-C
  { u: 1, v: 2, w: 1 }, // B-C
  { u: 1, v: 3, w: 5 }, // B-D
  { u: 2, v: 3, w: 8 }, // C-D
  { u: 2, v: 4, w: 10 }, // C-E
  { u: 3, v: 4, w: 2 }, // D-E
  { u: 3, v: 5, w: 6 }, // D-F
  { u: 4, v: 5, w: 3 }, // E-F
];

console.log(kruskal(6, edges)); // { total: 13, mst: [B-C, A-C, D-E, E-F, B-D] }

3.7 复杂度分析

Kruskal 的时间复杂度分两部分：

1. 排序：对 m 条边排序，复杂度 O(m log m)。这是整个算法的主导项。
2. 并查集：每条边最多调用一次 union（内部包含两次 find），总共 O(m) 次操作；加上路径压缩和按秩合并后，单次操作均摊 O(α(n))，其中 α 是反阿克曼函数。对任何现实规模的 n，α(n) 都小于 5，可以看成常数。所以这部分是 O(m · α(n))，几乎可以忽略。

总时间复杂度：O(m log m)，其中 m 是边数。因为 m ≤ n(n-1)/2，也可以写成 O(m log n)。空间复杂度 O(n + m)：并查集要 O(n) 的 parent 和 size 数组，边数组本身要 O(m)。

几个值得注意的细节：

• 排序主导意味着：如果边已经有序（比如输入本身就按权重排好），Kruskal 可以跳过排序，直接变成 O(m α(n)) 的近乎线性算法。
• 如果图是稠密图，m ≈ n²，复杂度约为 O(n² log n)。这个量级对 n = 10^5 就完全不可行，所以稠密大图要另想出路——这就是后面 Prim 的朴素版本登场的原因之一。
• 反阿克曼函数虽然名字吓人，但它是「增长慢到几乎不增长」的函数。α(10^80) 也只有 4 左右，所以工程上完全可以把它当常数。

再补一句关于排序的细节。很多语言的标准排序（如 JavaScript 的 Array.prototype.sort）是不稳定的，也就是说权重相同的边可能以任意顺序进入主循环。前面说过，等权时选哪条都不影响总权，所以不稳定性不会导致错误；但如果你希望「同一输入永远输出同一结果」（比如用于回归测试、输出比对），就在比较器里追加端点编号作为次关键字，把隐式顺序变成显式规则。另外，如果边权重是浮点数且可能出现 NaN，任何涉及 NaN 的比较都会让排序结果不可预期，输入清洗阶段就应该把它们过滤掉。这些不是算法本身的坑，而是「把算法接进真实系统」时最常见的两类问题。

3.8 为什么贪心是对的：切分定理视角

现在回答那个一直悬着的问题：Kruskal 每一步都只选「当前能选的最便宜的边」，凭什么最后一定得到全局最优？证明用归纳法，核心工具就是切分定理。

设算法按权重从小到大考察边 e₁, e₂, …, eₘ，实际选中的边构成集合 K。我们要证明的更强命题是：算法每一步结束后，已选中的边集 K 都能被扩展成一棵 MST。 如果这个命题成立，算法结束时（选够 n-1 条边）K 本身就是一棵 MST。

归纳起点：第 0 步，K 为空集。任意一棵 MST 都是 K 的扩展，命题显然成立。

归纳步骤：假设考察边 e = (u, v) 之前，当前选中边集 K 能被扩展成一棵 MST，记这棵 MST 为 T*。分两种情况：

情况一：e 被跳过。 跳过意味着 u、v 已经在 K 的同一个连通块里。因为 K ⊆ T*，T* 里 u、v 之间本来就有一条路径。K 保持不变，仍然能被 T* 扩展，命题继续成立。

情况二：e 被选中。 这是关键。设 S 是 K 中 u 所在的连通块（包含 u 的所有顶点），那么 v 在 V-S 里（因为 u、v 不在同一连通块）。现在观察切分 (S, V-S)：

• e 是跨堆边，权重 w(e)；
• 所有权重小于 w(e) 的跨堆边都已经在 e 之前被考察过。它们当时要么被选中——那样 u、v 就早就连通了，矛盾；要么被跳过——被跳过说明两端当时已经在同一连通块里，而连通块会随时间只增不减，所以这条边现在两端也同块，它根本不是跨堆边。

因此，e 是跨堆边 (S, V-S) 中的最小边。切分定理登场：存在一棵包含 e 的 MST。

但这还不够，我们还要保证这棵 MST 同时包含之前的 K。回忆归纳假设：K 能被 T* 扩展。从 T* 出发，用切分定理的交换论证：如果 e 不在 T* 里，把 e 加入 T* 形成环，环上必有一条跨堆边 f（f ≠ e），且 w(f) ≥ w(e)。交换得到 T’ = T* − f + e，它依然是 MST 且包含 e。关键点在于：f 是跨堆边，所以 f 不可能在 K 里——K 中没有任何边跨过 (S, V-S)（K 的连通块划分里，S 和 V-S 之间没有 K 的边，否则 S 就不是独立连通块）。于是交换没有动 K 的任何边，T’ 同时包含 K ∪ {e}。归纳步骤完成。

这个证明的妙处在于：它不依赖「后面会发生什么」的具体知识，每一步只利用两条信息——当前边是当前切分的最小跨堆边（由排序保证），以及切分定理（保证最小跨堆边可以进 MST）。所以 Kruskal 本质上是一个「永远不后悔」的算法：它选的每一条边，在当时的切分视角下都是最划算的，而切分定理保证了局部最优能拼出全局最优。

3.9 实现细节与边界情况

图不连通时。 如果输入图有多个连通分量，循环结束后 mst.length < n-1。这时得到的不是一个 MST，而是每个连通分量各自一棵最小生成树，合称最小生成森林。总权仍然是「所有分量各自最优」的总和，这在工程上往往正是想要的：每个孤立集群内部最省，集群之间本来就不需要线。

自环和重边。 自环 (u, u) 的 union 一定返回 false，直接跳过，无需特判。重边（两个点之间有多条边）完全正常：排序后较便宜的重边先被考虑，较贵的自然会被跳过，不会出错。

浮点权重。 权重不一定是整数。只要比较大小有全序，Kruskal 都能工作；排序用 a.w - b.w 对浮点数也适用。真正要小心的是「相等权重」：比较结果完全相等时，先后顺序不影响总权，但可能影响具体选了哪些边（后面 5.4 节细讲唯一性）。

时间复杂度陷阱。 如果忘了路径压缩，find 最坏会退化到 O(n)，整个算法变成 O(mn)，在稀疏图上还凑合，在稠密图上直接超时。所以并查集的两种优化一个都不能省。

提前终止的收益。 对连通图，选够 n-1 条边后立刻 break，可以避免扫描完剩余的所有边。最坏情况下收益不大，但平均能省不少时间，代码也只多一行。

3.10 关于 Kruskal 的补充讨论

等权边的处理细节。 排序时权重相等的边顺序任意，但这会带来一个微妙的后果：如果两条等权边都能选，Kruskal 可能给出不同的 MST。工程上如果需要「可复现的答案」，可以在排序比较器里加一条辅助规则，比如按端点编号做二次排序。注意：这不改变总权，只让输出稳定。

为什么不需要「回退」。 有人担心：万一先选了 A-B(4)，后来发现它堵住了更优的组合怎么办？回答是：Kruskal 从不在「未来视角」下后悔，因为选边的时机由权重顺序决定。任何一条被跳过的边，在被跳过的那一刻就已经两端连通，而且连通它俩的路径上每条边权重都不大于它——把这条边硬塞回去只会更贵。数学上，这就是 3.8 节归纳证明的直观版本。

Borůvka 算法：Kruskal 的亲戚。 1926 年 Borůvka 提出的算法是另一个思路：每轮让每个连通块选出连接自己的最小边，然后同时合并，直到只剩一个块。它的妙处是天然适合并行：每轮所有连通块可以独立选边。Borůvka 算法复杂度 O(m log n)，是并行 MST 和分布式 MST（如 MapReduce 环境）的基础，很多大规模系统里跑的就是它的变体。Kruskal 没法这样并行，因为它强依赖全局排序后的顺序决策。

边权是负数怎么办？ 本篇假设权重非负，但 Kruskal 对负权完全免疫：只要图连通，无论权重多负，MST 的定义和切分定理都不受影响，算法照常工作。这和最短路问题形成鲜明对比——Dijkstra 遇到负权就失效，而 MST 根本不在乎。想一想原因：MST 的目标是总权最小，负权只会让「多选边」更有吸引力，但树结构仍然强制 n-1 条边，所以算法逻辑无需任何修改。

关于「最小生成森林」的补一句。 很多工程输入并不是连通的。Kruskal 在循环结束后自然给出每个连通分量的最小树，不需要额外处理。这也意味着：如果你只想连接「指定的几个点」，MST 帮不了你——那是斯坦纳树问题；如果你只想让所有点以最小代价连通，MST 就是终局答案。

3.11 一次容易忽略的排错练习

Kruskal 主循环的正确性几乎完全押在并查集上，而并查集最常见的坑不在「逻辑错」，而在「性能退化」。看下面这个看起来人畜无害的 union：

union(a, b) {
  const ra = this.find(a);
  const rb = this.find(b);
  if (ra === rb) return false;
  this.parent[ra] = rb; // 总是把 ra 挂到 rb 下
  return true;
}

这段代码逻辑上是对的：判环、合并都正确，小图上跑 Kruskal 一点问题都没有。但请注意它缺了什么——没有按大小或秩合并。考虑一组坏输入：边按 (1,2,1)、(2,3,2)、(3,4,3)、…、(k, k+1, k) 的顺序给出，每次都把新根挂到旧根下，parent 链会越来越长：1 → 2 → 3 → … → k+1。如果之后再反复查询 1 号点，find(1) 要沿着链走到底，单次 O(k)。

更糟的是，如果连路径压缩都没写，链永远不会缩短，整个 Kruskal 从 O(m log m) 退化到 O(mn)。n = 10^5 时，10^10 级别的操作直接超时。教训有两层：第一，判环逻辑正确 ≠ 性能正确，数据结构实现必须同时满足正确性和渐近复杂度；第二，写完并查集后，用一条「链状图」做压力测试，是发现这类退化最快的方法。

还有一种常见错误在合并规则的细节：写了按大小合并，却忘了更新 size。size 不更新不会让结果错误（大小只影响挂法），但会让「按大小」名存实亡，退化风险和上面一样。自查方法：union 里任何对 size 的读取都必须有对应的写入。

最后提醒一个主循环里的小坑：有人习惯先写 if (find(u) === find(v)) continue; 再写 mst.push(e); union(u, v);，这当然正确；但千万不要在 union 之后再单独 find 一次来判断——白白多一次 O(α) 查询是小事，真正的风险是有人会把判断写反，变成「连通才选」，那就全盘皆错了。

Kruskal 到这里就完整了。它的代码短、思路直、不需要理解图的结构，只要会排序和并查集就能写对。接下来看另一种完全不同的思路：Prim 从一个点出发，让树自己长出来。

四、Prim：让树从一个点慢慢长大

4.1 核心思想

Kruskal 的视角是「边」：所有边排好队，一条条地过。Prim 的视角是「点」：随便选一个起点，让树从这一点开始，一步吞并一个点，直到吞并全部顶点。

更精确地说，Prim 维护两个东西：

1. 已经长出的树内顶点集合 S；
2. 一棵候选边集合：所有「一端在 S、另一端在 V-S」的跨堆边。

每一步，从候选边里挑权重最小的一条，把它的树外端点拉进 S，同时更新候选边。重复 n-1 次，S 变成全部顶点，选中的边恰好构成一棵 MST。

为什么只需要看跨堆边？因为 MST 里不允许成环，而任何「两端都在 S 内」的边加入后必然形成环（S 内部已经被树边连通）；任何「两端都在 V-S」的边加入后会让树悬空，连不到树上。真正合法的候选只有跨堆边。

和 Kruskal 一样，Prim 也是贪心：每次选当前跨堆边里的最小者。而切分定理告诉我们，当前 S 与 V-S 的切分上的最小跨堆边一定属于某棵 MST，所以贪心不亏。这个论证在 4.8 节展开。

4.2 和 Dijkstra 的亲密关系

如果你学过图系列第 9 篇的 Dijkstra，会觉得 Prim 长得非常眼熟：都是维护一个「已确定集合」，都用优先队列取最小，都是从起点向外扩散。两个算法确实同源，但有一个本质区别：

对比项	Dijkstra	Prim
目标	从起点到每个点的最短路径长度	连通所有点的最小总边权
队列里比较的值	起点到该点的累计距离 dist[v]	连接到该点的那条树边权重
更新规则	dist[v] = min(dist[v], dist[u] + w)	只比较边权 w，不累加
结果	一棵最短路树（各点到起点分别最优）	一棵全局总权最小的树

一句话记忆：Dijkstra 比的是「我到你有多远」，Prim 比的是「把你拉进树要花多少钱」。 后者不关心树内的路径，只关心边界上每条边的单价。

正因为如此，Prim 从任何一个起点出发，最终得到的总权都一样（都是 MST 的总权 13）；而 Dijkstra 换个起点，得到的距离表完全不同。这是区分两个算法的一个简单测试：如果问题问「总连通代价最小」，用 Prim；如果问「从某点到某点最短」，用 Dijkstra。

4.3 完整走查：同一张图，从 A 出发

还是那张 6 点 9 边的图，这次从 A 出发。初始 S = {A}，候选跨边就是从 A 伸出去的两条边：A-B(4) 和 A-C(2)。

第 1 步： 候选边里最小的是 A-C(2)，选中，C 进树。S = {A, C}，总权 2。

第 2 步： 现在跨堆边有 A-B(4)、C-B(1)、C-D(8)、C-E(10)。最小的是 C-B(1)，选中，B 进树。S = {A, C, B}，总权 3。

第 3 步： B 进树后，跨堆边变成 B-D(5)、C-D(8)、C-E(10)（A-B 两端都在树内了，退出候选）。最小的是 B-D(5)，选中，D 进树。S = {A, C, B, D}，总权 8。

第 4 步： 跨堆边有 D-E(2)、D-F(6)、C-E(10)。最小的是 D-E(2)，选中，E 进树。S = {A, C, B, D, E}，总权 10。

第 5 步： 跨堆边只剩 E-F(3)（其它边要么两端在树内，要么已经被更便宜的替代）。选中 E-F(3)，F 进树。S = 全部顶点，总权 13。完成。

全过程汇总成一张表：

步骤	树内 S	候选跨边（权重）	选择	新增边	总权
0	{A}	A-B(4), A-C(2)	A-C(2)	A-C	2
1	{A, C}	A-B(4), C-B(1), C-D(8), C-E(10)	C-B(1)	C-B	3
2	{A, C, B}	B-D(5), C-D(8), C-E(10)	B-D(5)	B-D	8
3	{A, C, B, D}	D-E(2), D-F(6), C-E(10)	D-E(2)	D-E	10
4	{A, C, B, D, E}	E-F(3)	E-F(3)	E-F	13
5	全部顶点	—	完成	—	13

注意到一个有趣的事实：Prim 从 A 出发选出的边是 {A-C, C-B, B-D, D-E, E-F}，和 Kruskal 选出的 {B-C, A-C, D-E, E-F, B-D} 是完全相同的五条边，只是顺序不同。这不是巧合，而是这张图恰好只有一棵 MST（所有边权互不相同，后面会讲为什么互异权重保证唯一）；但即使图有多棵 MST，两个算法也可能给出不同的合法结果，总权永远一样。

4.4 配图：树的生长过程

第一步之后，树还很小，只有 A 和 C 两个点：

flowchart LR
    A((A)) ---|2| C((C))
    A -.候选 4.-> B((B))
    C -.候选 1.-> B
    C -.候选 8.-> D((D))
    C -.候选 10.-> E((E))

第二步之后，B 被拉进树，树变成三叉的 Y 形：

flowchart LR
    A((A)) ---|2| C((C))
    C ---|1| B((B))
    B -.候选 5.-> D((D))
    C -.候选 8.-> D
    C -.候选 10.-> E((E))

第三、四步之后，D、E 相继进树，树已经覆盖五个点，只差 F：

flowchart LR
    A((A)) ---|2| C((C))
    C ---|1| B((B))
    B ---|5| D((D))
    D ---|2| E((E))
    E -.候选 3.-> F((F))
    D -.候选 6.-> F

第五步选中 E-F(3)，完成。最终结果和 Kruskal 的最终图完全一样：

flowchart LR
    A((A)) ---|2| C((C))
    C ---|1| B((B))
    B ---|5| D((D))
    D ---|2| E((E))
    E ---|3| F((F))

从这三张生长图可以看出 Prim 的「局部性」：树始终是连成一片的整体，从外围一圈一圈地长大；而 Kruskal 的选中边集在早期可能分成好几块，最后才连成一片。这个差别也决定了它们各自适合的存储方式和数据规模。

4.5 实现方式一：优先队列版（堆优化）

Prim 的正式实现通常分成两部分：邻接表存储图，小根堆维护候选边。为什么需要堆？因为每一步都要从不断变化的候选边集合里取最小值。朴素做法是每步扫描所有边，O(m) 一步、O(nm) 总共；而用小根堆，插入和取最小都是 O(log n)，总复杂度能降到 O((n+m) log n)。

先看一个小根堆的实现。树系列第 16 篇讲过堆的完整细节，这里只放一个够用的版本（用泛型比较器，方便按边权比较）：

class MinHeap<T> {
  private a: T[] = [];

  constructor(private less: (x: T, y: T) => boolean = (x, y) => x < y) {}

  size(): number {
    return this.a.length;
  }

  push(v: T): void {
    this.a.push(v);
    let i = this.a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.less(this.a[i], this.a[p])) {
        [this.a[i], this.a[p]] = [this.a[p], this.a[i]];
        i = p;
      } else {
        break;
      }
    }
  }

  pop(): T | undefined {
    if (this.a.length === 0) return undefined;
    const top = this.a[0];
    const last = this.a.pop()!;
    if (this.a.length > 0) {
      this.a[0] = last;
      let i = 0;
      const n = this.a.length;
      while (true) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < n && this.less(this.a[l], this.a[m])) m = l;
        if (r < n && this.less(this.a[r], this.a[m])) m = r;
        if (m === i) break;
        [this.a[i], this.a[m]] = [this.a[m], this.a[i]];
        i = m;
      }
    }
    return top;
  }
}

主函数用邻接表，并采用「惰性删除」策略：堆里可能会残留一些已经失效的候选边（两端都进了树），弹出时发现端点已被访问就直接丢弃。这样实现最简洁，代价是堆里最多同时存在 O(m) 条记录，空间换正确性。

interface AdjEdge {
  to: number;
  w: number;
}

function prim(
  n: number,
  adj: AdjEdge[][],
  start = 0
): { total: number; parent: number[] } {
  const visited = new Array<boolean>(n).fill(false);
  const parent = new Array<number>(n).fill(-1);

  // 堆元素：{ v: 目标点, w: 边权, from: 边来自哪个树内点 }
  const heap = new MinHeap<{ v: number; w: number; from: number }>(
    (x, y) => x.w - y.w < 0
  );
  heap.push({ v: start, w: 0, from: -1 });

  let total = 0;
  let count = 0;

  while (heap.size() > 0 && count < n) {
    const { v, w, from } = heap.pop()!;
    if (visited[v]) continue; // 惰性删除：这条边已经失效

    visited[v] = true;
    parent[v] = from;
    if (from !== -1) total += w; // 起点没有入树边
    count++;

    for (const e of adj[v]) {
      if (!visited[e.to]) {
        heap.push({ v: e.to, w: e.w, from: v });
      }
    }
  }

  return { total, parent };
}

这段代码和 Dijkstra 的堆优化版本几乎是一个模子刻出来的，差别只在比较的值：Dijkstra 入堆的是 dist 累计值，Prim 入堆的是单条边的权重。走查一下 4.3 节的过程：起点 A 入堆；弹出 A 后把 B(4)、C(2) 入堆；弹出 C(2) 后把 B(1)、D(8)、E(10) 入堆——注意 B 会以 4 和 1 两个不同权重各出现一次，弹出 4 那条时 B 已经被 1 那条访问过了，于是被惰性删除。这就是为什么堆里会有「重复项」，也是为什么弹出时一定要先检查 visited。

4.6 实现方式二：朴素 O(V²) 版本

如果图用邻接矩阵存储，或者图非常稠密（m 接近 n²），堆优化反而不如一个更简单的版本：维护数组 dist[v] = 当前树连接到 v 的最小边权，每轮线性扫描所有未入树的点，找 dist 最小的那个拉进树，然后更新它的邻居。

function primDense(
  n: number,
  g: number[][] // g[u][v] 为边权，无边时 Infinity
): number {
  const dist = new Array<number>(n).fill(Infinity);
  const used = new Array<boolean>(n).fill(false);
  dist[0] = 0;
  let total = 0;

  for (let i = 0; i < n; i++) {
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!used[v] && (u === -1 || dist[v] < dist[u])) u = v;
    }
    used[u] = true;
    total += dist[u];
    for (let v = 0; v < n; v++) {
      if (!used[v] && g[u][v] < dist[v]) dist[v] = g[u][v];
    }
  }
  return total;
}

这个版本每轮扫描 n 个点、更新 n 个邻居，共 n 轮，复杂度 O(n²)。在稠密图上，m ≈ n²，堆优化版 O((n+m) log n) ≈ O(n² log n)，反而不如朴素的 O(n²)——因为常数更小、没有堆操作。这就是「没有银弹」的典型例子：数据规模决定算法选择。

4.7 复杂度分析

堆优化版 Prim 的复杂度：

1. 每个顶点最多进堆一次、出堆一次（含重复入堆，也只需乘以常数），堆操作 O(log n)；
2. 邻接表每条边会被扫描常数次，最多产生 2m 次入堆操作；
3. 惰性删除会多弹出若干失效记录，但总量仍是 O(m) 次。

所以总复杂度 O((n + m) log n)。空间复杂度 O(n + m)：visited、parent、dist 数组 O(n)，堆和邻接表 O(m)。

如果使用斐波那契堆，可以把取最小和插入优化到均摊 O(1) 的级别（减小键 O(1)），总复杂度降到 O(m + n log n)。但斐波那契堆常数巨大、实现复杂，工程上几乎都用二叉堆，这里只作知识储备提一句。

朴素版 O(n²) 和堆优化版 O((n+m) log n) 怎么选？

• m 接近 n²（稠密图）：选朴素 O(n²)，常数小，代码短；
• m 接近 n（稀疏图）：选堆优化 O((n+m) log n)，因为 m log n 远小于 n²；
• m 处于中间地带：两者都可行，实测决定。

Kruskal 的 O(m log m) 在稀疏图上和堆优化 Prim 同阶；在稠密图上 Kruskal 是 O(n² log n)，比朴素 Prim 慢一个 log 因子。这个对比在第五节会整理成表格。

4.8 为什么贪心是对的：切分定理视角

Prim 的正确性证明比 Kruskal 还要直白，因为每一步的切分就是「树内 vs 树外」本身。

设当前树内集合为 S，已经选中的树边为 F。归纳假设：F 可以被扩展成一棵 MST。现在算法选的是跨堆边 (S, V-S) 中权重最小的 e。切分定理直接给出：存在一棵包含 e 的 MST。

但同样要确认这棵 MST 同时包含之前的 F。回顾交换论证：如果候选 MST T* 不含 e，把 e 加入 T* 形成环，环上必有一条跨堆边 f，且 w(f) ≥ w(e)。把 f 换成 e 得到新的 MST T’。这里的关键：F 里的边两端都在 S 内，没有一条跨过 (S, V-S)，所以 f 不可能是 F 中的边，交换不会破坏 F。因此 T’ 同时包含 F ∪ {e}，归纳继续成立。

归纳起点：S = {起点}，F = ∅，任何 MST 都是扩展。归纳终点：S = V，F 有 n-1 条边且可扩展成 MST，所以 F 本身就是 MST。

看出来了吗？Kruskal 和 Prim 的证明是同一个模板，只是切分的来源不同：

• Kruskal 的切分来自「当前边连接的两个连通块之一 vs 其余」；
• Prim 的切分来自「当前树 vs 其余」。

两者都依赖同一个事实——排序或优先队列保证了所选边是当前切分的最小跨堆边。所以本文开头那句话不是修辞：切分定理就是两个算法的同一个灵魂。

4.9 Prim 的实现细节与边界情况

起点随便选。 只要图连通，从任何一点出发，Prim 得到的总权都一样。算法不要求「从 1 号点开始」有什么特别之处；选起点唯一影响的是树的具体形态和遍历顺序。这在证明里也成立：任意 S 的切分定理都成立。

图不连通时。 堆会弹空，循环在 count < n 时结束。此时 parent 数组里那些仍为 -1 的点就是起点所在连通分量外的点，得到的是起点所在分量的最小生成树，不是整张图的结果。如果要做全图的最小生成森林，需要对每个未访问分量分别跑 Prim。

惰性删除的坑。 如果忘了在弹出时检查 visited，可能会出现同一顶点被入树两次，树边变成 n-1 之外的非法结构，结果完全错误。检查 visited[v] 必须在「处理」之前，这是最容易写漏的一行。

dist 的语义。 朴素版里 dist[v] 是「当前树连接到 v 的最便宜单边」，不是「起点到 v 的累计距离」。很多 Dijkstra 写顺手的人在这里犯错：把更新写成 dist[v] = dist[u] + w。一旦累加，Prim 就退化成了错误算法，得到的不再是 MST。请在心里反复强调：Prim 不比路，只比单价。

重边与自环。 邻接表里如果有重边，堆里会出现多个候选，惰性删除会保证只取到最小那个（因为小根堆先弹出小的）；自环不会入堆（起点和终点同一顶点，visited 已为真）。两种输入都不需要特殊处理。

4.10 从 parent 数组还原 MST 边

堆优化版 Prim 返回的 parent[v] 记录的是「v 是被哪条树边拉进树的」，具体说是树内那一端的编号。还原边集只需要一行遍历：

const edges: Array<{ u: number; v: number; w: number }> = [];
for (let v = 0; v < n; v++) {
  if (parent[v] !== -1) {
    const u = parent[v];
    const w = adj[u].find((e) => e.to === v)!.w;
    edges.push({ u, v, w });
  }
}

注意 find 每次线性扫描邻接表，总代价 O(m)。如果不想多花这趟扫描，可以在入堆时把权重一起存进 parent 的伴随数组 parentW[v]，或者干脆用一个 mstEdges 数组在选中时直接 push，更省事。还原出来的边集和 Kruskal 的 mst 数组一样，都是 MST 的边，只是顺序不同。

4.11 Prim 的变体与工程笔记

稠密图上的邻接矩阵版本其实还可以再优化常数：每轮扫描 dist 找最小点、扫描行更新邻居，两个循环都能写成缓存友好的顺序访问，实测在 n 到几千的稠密图上非常快。这也是很多科学计算库（比如聚类、图像分割场景）默认实现 O(n²) 版的原因。

在线的「加点」场景：假设已经跑完了一棵 MST，现在新增一个点 v 和若干条新边。Prim 的增量处理很自然：把新点的跨堆边直接塞进现有堆，弹出最小边即可；Kruskal 则需要把新边和旧边一起重新排序（除非维护有序结构），增量代价更高。反过来，如果批量新增的是「边」而不是点，Kruskal 配合动态并查集反而更好维护。这类「动态 MST」问题在竞赛里有专门的数据结构，工程上多数时候直接重算——因为 MST 的 O(m log m) 已经够快。

栈还是堆？ 如果你在写竞赛代码，很多语言的标准库自带堆：C++ 的 priority_queue、Python 的 heapq、Java 的 PriorityQueue、JavaScript 的库函数。用标准库时唯一要注意的是比较器方向：priority_queue 默认是大根堆，需要传入 greater 或取负权重；heapq 默认小根堆，直接可用。

和 Kruskal 的互补提醒：同一道题里，两个算法往往可以互相验证。写完一个实现后，用随机小图分别跑两个算法，断言总权相等——这是最省力的对拍手段。图系列一直强调的「对拍」习惯，在这里同样适用。

4.12 稠密图上的完整小例子：距离矩阵版

朴素 O(n²) 版本最常见的输入是距离矩阵。看一个 5 个点的完全图（下三角矩阵，∞ 表示没有边，这里全都有边）：

	A	B	C	D	E
A	0	2	9	10	7
B	2	0	1	6	8
C	9	1	0	5	4
D	10	6	5	0	3
E	7	8	4	3	0

从 A 出发，维护 dist 数组（未入树点的最小入树边权）：

轮次	选中点	dist[B]	dist[C]	dist[D]	dist[E]	说明
0	A	2	9	10	7	初始值取 A 的行
1	B(2)	—	1	6	7	B 行刷新 C、D；E 保持 7
2	C(1)	—	—	5	4	C 行刷新 D、E
3	E(4)	—	—	3	—	E 行刷新 D
4	D(3)	—	—	—	—	完成

总权 = 2 + 1 + 4 + 3 = 10，选中边是 A-B(2)、B-C(1)、C-E(4)、E-D(3)。用 Kruskal 验证：边排序后依次选 B-C(1)、A-B(2)、D-E(3)、C-E(4)，四步连通全部 5 个点，总权同样是 10，边集完全一致。

这个例子值得盯住两点：第一，dist 数组的更新只看单条边权，从不累加——D 的 dist 从 10 → 6 → 5 → 3，一路都是「当前树连到 D 的最便宜单边」；第二，A-D 直达边 10 从头到尾都没被用到，因为绕道 B-C-E-D 的三段加起来也只相当于「每次只付最便宜的一段」。这正是「连通总价」与「单对最短」两种目标的差异缩影。

五、Kruskal 与 Prim：全面对比

两个算法已经分别讲完，现在把它们放到同一张桌子上比一比。先说结论：它们解决同一个问题，正确性来自同一条定理，只是在「选边的顺序」和「依赖的数据结构」上分道扬镳。

5.1 一张对比总表

对比项	Kruskal	Prim
贪心视角	边贪心：全局排序，从小到大选	点贪心：从一个点出发向外扩张
核心数据结构	并查集（判环 + 合并）	优先队列/小根堆（取最小候选边）
图的存储偏好	边数组（排序友好）	邻接表（遍历邻居友好）
时间复杂度	O(m log m)，排序主导	堆优化 O((n+m) log n)；朴素 O(n²)
空间复杂度	O(n + m)	O(n + m)
是否需要先排序	需要	不需要（堆在过程中隐式排序）
是否依赖连通性	不连通也能得到生成森林	一次只覆盖一个连通分量
提前终止	选够 n-1 条边即可停	所有点入树即可停
实现难度	低（并查集 + 排序）	中（堆 + 惰性删除易出错）
典型适用	稀疏图、边集输入、离线场景	稠密图（朴素版）、在线扩张场景

这张表最后两行需要展开说明，因为它们决定了「什么时候用谁」。

5.2 稠密与稀疏：数据规模说了算

图的「密度」看边数 m 与顶点数 n 的关系。稀疏图 m ≈ n（比如公路网、电路板走线，每个点平均只有常数条边）；稠密图 m ≈ n²（比如完全图：每个城市到每个城市都有航线报价）。

• 稀疏图上，m log m ≈ n log n，Kruskal 的排序和并查集都极快；堆优化 Prim 同样 O(n log n)，两者同阶，但 Kruskal 常数更小、代码更短，通常更受欢迎。
• 稠密图上，Kruskal 是 O(n² log n)；朴素 Prim 是 O(n²)，少一个 log，而且没有堆操作、常数小。m ≈ n² 时朴素 Prim 完胜。
• 堆优化 Prim 在两种图上都可用，但在稠密图上不如朴素版，在稀疏图上不如 Kruskal 省事——它更像一个「两头都行、两头都不是最优」的均衡选项。

画成一张决策图：

flowchart TD
    Q["图有多稠密？"] -->|"m ≈ n，稀疏"| K["Kruskal：O(m log m)，代码短"]
    Q -->|"m ≈ n²，稠密"| P["朴素 Prim：O(n²)，常数小"]
    Q -->|"m 在中间"| B["堆优化 Prim 或 Kruskal，实测决定"]

关于「中间地带」，给一点实测经验：当 m 在 10n 到 50n 之间时，Kruskal 的排序常数通常比堆操作小，多数情况下更快；当 m 超过 100n 时，朴素 Prim 的优势开始显现。但常数受语言、缓存、内存布局影响很大，遇到关键性能需求时，正确姿势是跑基准测试而不是背结论。还可以利用图的结构：比如网格图、道路图天然稀疏，几乎无脑选 Kruskal；距离矩阵、全连接图则选朴素 Prim。把「渐近复杂度」和「常数因子」分开想，选择就不难了。

工程上还有一个常被忽略的因素：输入格式。如果数据本来就是「边的列表」（比如数据库里一张 (from, to, cost) 表），Kruskal 连建图都不需要，排序后直接跑；而 Prim 需要先花 O(m) 建邻接表。反过来，如果数据是邻接矩阵（比如距离矩阵），朴素 Prim 是零转换成本的选择。

5.3 实现难度与常见翻车点

Kruskal 的实现难点集中在并查集：路径压缩写没写、合并时大小判断写反没有。只要并查集正确，主循环逻辑几乎没有出错空间。Prim 的实现难点集中在堆：比较器方向写反（写成大根堆）、忘记惰性删除、把 dist 更新写成累加——每一个都是能静默产出错误结果的坑。

从「第一次就能写对」的角度看，Kruskal 通常更友好；从「不依赖排序稳定性」的角度看，两者都无所谓。面试和竞赛里，如果时间紧张，很多选手默认写 Kruskal，因为它需要的上下文最少：边数组 + 并查集 + 排序，三样东西都不容易出错。

5.4 结果是否唯一：权重全不同时，MST 唯一

一个高频问题：同一张图，Kruskal 和 Prim 会不会算出不同的 MST？答案分两种情况。

情况一：所有边权重互不相同。 此时 MST 是唯一的，Kruskal 和 Prim（无论从哪个点出发）必然得到同一棵 MST。证明思路：用切分定理和反证法。假设存在两棵不同的 MST T₁、T₂，取 T₁ \ T₂ 中权重最小的边 e。把 e 加入 T₂ 形成环，环上有一条边 f ∈ T₂ \ T₁（可以证明存在），且因为 e 是 T₁ \ T₂ 中最小的、f 是 T₂ \ T₁ 中的某条边，结合两个集合的最小性可以推出 w(f) > w(e)（这里需要仔细论证：如果 w(f) < w(e)，那 f 作为 T₂ \ T₁ 中比 e 小的边，交换 e 与 f 会得到更小的树，矛盾；所以 w(f) > w(e)）。于是把 T₂ 里的 f 换成 e，得到一棵比 T₂ 更小的生成树，与 T₂ 是最小矛盾。因此 T₁ = T₂。

更简洁的等价说法：权重互异时，每个切分的「最小跨堆边」都是唯一的，而切分定理能推出每条 MST 边都必须「是某个切分的唯一最小跨堆边」，所以 MST 被这些唯一选择钉死了。

情况二：存在相同权重的边。 MST 可能不唯一。比如三个点 A、B、C，边 A-B(1)、B-C(1)、A-C(2)：两棵 MST 分别是 {A-B, B-C} 和 {A-B, A-C}，总权都是 3。Kruskal 先遇到哪条 1 就选哪条（排序稳定与否会影响具体选择），Prim 从 A 出发会先选 A-B 再选 B-C，得到其中一棵。所有 MST 的总权一定相同，但边集可能不同。

这也是为什么算法描述里通常说「最小生成树」而不是「这棵」：它是一类最优解，算法负责给出其中一棵。如果业务上需要所有 MST（比如决策审查），那是一个更难的问题（枚举所有 MST），不在本篇范围。

5.5 什么时候用谁：给选择困难症的建议

按优先级给几条经验法则：

1. 输入是边数组、图稀疏、代码求短：Kruskal。
2. 输入是邻接矩阵、图稠密：朴素 Prim。
3. 输入是邻接表、图稀疏、想用堆：堆优化 Prim，注意惰性删除。
4. 需要逐步扩张的在线场景（比如「我已经有了前面 k 个点的树，新来一个点怎么接进来」）：Prim 的增量特性更自然。
5. 需要提前知道所有边的排序（比如后面要做「按边权从小到大处理」的其它事）：Kruskal 顺手。

两条算法没有绝对的胜负，它们共享的复杂度下限也让「更优」的空间很小——在比较模型下，求 MST 的下界是 Ω(m log m)（对一般图），Kruskal 已经达到最优渐近复杂度；Prim 的斐波那契堆版本达到 O(m + n log n)，在稠密图上更优。所以工程上选哪个，主要看代码可维护性和数据形态，而不是理论差距。

5.6 证明模板：把两个算法放在同一张图纸上

既然两个算法的正确性都来自切分定理，不妨把证明模板并排写出来，你会看到它们只是「切分来源」不同：

证明步骤	Kruskal	Prim
归纳命题	已选边集可扩展成一棵 MST	已选树边可扩展成一棵 MST
当前切分	u 所在连通块 S vs 其余	当前树内 S vs 树外
为什么选的是最小跨堆边	排序保证：更小的跨堆边都已被处理	优先队列保证：堆顶即跨堆最小
切分定理给什么	存在 MST 含 e	存在 MST 含 e
交换论证保护什么	f 不在已选边里（S 内无边跨堆）	f 不在已选边里（树边全在 S 内）
终点	选满 n-1 条边	所有点入树

这张表值得抄进笔记。以后遇到任何「贪心求 MST」的变体（比如边权带函数、部分边必须选、最小瓶颈生成树），第一件事就是问自己：它维护的切分是什么？选出的边是不是当前切分的最小跨堆边？ 能回答，贪心就站得住；回答不了，就要回到交换论证里找反例。

顺便一提，最小瓶颈生成树（MBST）是这条思路的经典推论：一棵 MST 同时也是最小瓶颈生成树——它最大边权的树中最小。证明只需要切分定理：MST 上任意一条边 e 都是某个切分的最小跨堆边，所以任何生成树都必须用至少 w(e) 的代价跨过这个切分，最大边不可能更小。

六、应用：从布线到聚类

最小生成树是图论里「出镜率」最高的算法之一，因为它解决的问题太常见：任何「用最少的线把东西连起来」的需求，本质上都是 MST。下面按从近到远的顺序看几个真实应用。

6.1 网络布线：MST 的原始动机

电信骨干网、电力输配电网、自来水管网、天然气管道、地铁轨道——所有这些基础设施都有一个共同特征：节点之间需要连通，而建设成本与线路长度或施工难度相关。MST 给出的方案就是「保证全网连通的最省钱方案」。

一个细节值得注意：现实网络往往还需要冗余。只按 MST 布线，任何一条线路断了，整个网络就分裂成两半。所以工程上通常的做法是：先求 MST 作为「保底骨架」，再在关键节点之间补几条冗余线路，兼顾成本与可靠性。MST 的价值不只是给出最终图纸，更是给「冗余应该补在哪里」提供基准——把 MST 上最脆弱、最关键的那些边找出来优先备份。

类似地，在广播场景里，如果一台服务器要向所有客户端推送数据，沿着 MST 转发可以让总传输代价最小：每条数据只沿着树边走一次，没有重复转发。这叫做最小生成树广播，虽然它不保证单条路径最短，但保证总流量最小。

flowchart LR
    subgraph 备选方案
        direction LR
        A1((机房)) ---|8| B1((楼A))
        A1 ---|3| C1((楼C))
        B1 ---|1| C1
        B1 ---|6| D1((楼D))
        C1 ---|2| D1
    end
    subgraph 最优方案
        direction LR
        A2((机房)) ~~~ B2((楼A))
        A2 ---|3| C2((楼C))
        B2 ---|1| C2
        B2 ---|6| D2((楼D))
        C2 ---|2| D2
    end

左边是「每对楼都拉线」的冗余方案，右边是 MST 方案：同样的四栋楼，总代价从 20 降到 12，网络依然连通。

6.2 聚类：Kruskal 的每次合并就是一次聚簇

这是很多教材轻描淡写、但非常迷人的应用。回忆 Kruskal 的过程：所有边按权重从小到大排序，能合并就合并。这个过程本质上就是层次聚类——具体说是单链接聚类（single-linkage clustering）：

1. 初始时每个点是一个簇；
2. 每次选「当前簇间最短距离」对应的那条边，把两个簇合并；
3. 选中的边按权重从小到大排列，正好是 Kruskal 选边的顺序。

所以 Kruskal 的前 k 次成功合并，等价于「把 n 个点聚成 n-k 个簇的单链接聚类结果」。如果想要 k 个簇，只要在 Kruskal 选满 n-k 条边时提前停止，剩下的连通块就是 k 个簇；如果想看聚类树（dendrogram），Kruskal 的每次合并节点就是树上的一个分叉。

为什么单链接聚类用 MST 合理？因为 MST 优先连接距离近的点，把「近亲」粘在一起；而簇与簇之间连接时，用的也是两个簇之间最短的那条边。删掉 MST 上最长的 k-1 条边，剩下的 k 个连通块就是「簇内边短、簇间边相对长」的划分——这正是聚类的目标。

flowchart TD
    P1((p1)) ---|1| P2((p2))
    P2 ---|2| P3((p3))
    P3 ---|9| P4((p4))
    P4 ---|1.5| P5((p5))
    P5 ---|2.5| P6((p6))
    P6 ---|8| P7((p7))
    P7 ---|1| P8((p8))

这棵 MST 上，最长的两条边是 p3-p4(9) 和 p6-p7(8)。删掉它们，8 个点自然分成三簇：{p1, p2, p3}、{p4, p5, p6}、{p7, p8}。你甚至不需要告诉算法「要几个簇」，看图上的长边就完成了可视化分群——这就是 MST 聚类的直观魅力。

当然，单链接聚类也有被批评的地方：它只看「两个簇之间最近的一对点」，如果这两个点是各自簇里的离群点，就可能把本不该合并的簇错误地粘在一起，形成细长的链状簇。弥补的办法是换用平均链接或 Ward 链接，但它们的每一步合并不再是「全局最短边」，也就不能再和 Kruskal 一一对应了。所以记住精确的表述：Kruskal 实现的是单链接聚类，而不是聚类本身——聚类方法有很多种，MST 只是其中一种的高效实现。

这个思路在很多领域有实际版本：图像分割里，基于图的区域生长算法把像素看成点、颜色差异看成边权，先求 MST 再按阈值断开；社交网络里，按互动频率建 MST，断开稀疏连接的边就能发现兴趣社群；基因表达数据里，单链接聚类也是常见的初步探索工具。

6.3 次小生成树：一句话带过

如果 MST 的某条边坏了，或者你想知道「除了最优方案，第二优的方案是什么」，就需要次小生成树（Second Best MST）。一句话思路：先求出 MST，再枚举每一条不在树里的边 e，把 e 加入树形成环，删掉环上权重最大的树边，得到的总权最小的那个候选就是次小生成树。

原理不复杂：任何生成树 T’ 与 MST T 之间，必然可以通过一系列「加入一条非树边、删除一条环上树边」的交换得到；而要让总权尽量小，每次交换的增量 w(e) − w(环上最大边) 要尽量小。次小生成树就是所有单次交换里增量最小的结果。实现上需要用树剖分或倍增预处理「路径上最大边」来支持快速查询，复杂度可以做到 O(m log n)，比重新跑一次 MST 优雅得多。

flowchart LR
    A((A)) ---|1| B((B))
    B ---|2| C((C))
    C ---|3| D((D))
    A -.非树边 4.-> D

上图 MST 是 A-B、B-C、C-D（总权 6）。加入非树边 A-D(4) 形成环 A-B-C-D-A，环上最大的树边是 C-D(3)，替换后总权 6−3+4=7，这就是唯一的次小生成树。

6.4 其它值得一提的应用

• 旅行商问题的下界：对城市距离图求 MST，MST 总权是任意哈密顿回路长度的下界（回路删掉一条边就变成一棵树，所以回路长度 ≥ MST 总权）。分支限界法常用它剪枝。
• 水电站与输电线规划：历史上 Borůvka 算法就是为了摩拉维亚电网的真实布线问题设计的，MST 至今仍是电力系统规划课程的必修内容。
• 网络可靠性分析：MST 上的边是「删除后代价最大的边」的候选，最小割/桥梁分析与 MST 常常配合使用。
• 近似算法组件：许多 NP 难问题（如 Steiner 树、k 中心聚类）的近似算法把 MST 当第一步骨架。

6.5 清醒一下：MST 不是万能的

最后泼一盆冷水。MST 保证的是「总连通代价最小」，它不保证任意两点之间的路径最短。比如一棵 MST 里 A 到 D 的路径可能要绕很远，而图中明明有一条直达的贵边。最短路径问题（图系列第 8-11 篇）和最小生成树问题是两个不同目标：一个优化「点对点代价」，一个优化「全局连通代价」。千万别在需要最短路的地方用 MST，反之亦然。

另外，MST 假设「连通」是唯一约束。如果问题还要求每个点度数不能超过 2（那就是一条哈密顿路径）、要求节点有容量限制（度约束 MST）、要求边只许单向（有向图最小树形图），MST 都不适用。本篇只解决最朴素的版本，但理解了朴素版本，这些变体的论文读起来就顺了。

6.6 动手体验：打开可视化实验室

理论走查再细致，也不如亲手拖几个点、改几条边。博客配套的「图算法可视化实验室」支持自定义节点、边权，并内置了多种图算法的逐步演示。你可以用它复现本篇的 6 点图，分别跑 Kruskal 和 Prim，观察两个算法每一步的选中边如何不同地生长，最后汇成同一棵总权 13 的树。

建议的动手实验顺序：先把 A-F 六个点按 1.5 节的表连好，权重照抄；然后分别用两种算法跑一遍，对照本文 3.3 节和 4.3 节的表格检查每一步；最后随机改一条边的权重，观察 MST 是否变化、总权如何变化。亲手改过一次，你就知道「权重互异 → MST 唯一」这个结论在真实交互里长什么样。

6.7 更多延伸：随机迷宫、图像分割与网络簇

再补充三个你可能听过、但没意识到和 MST 有关的场景。

随机迷宫。 有一种生成迷宫的方法叫「随机化 Kruskal」：把网格的每条相邻格子边随机打乱权重（或者干脆随机顺序），然后跑 Kruskal 的并查集合并逻辑。因为每次「合并」都打通两个此前不连通的区域，最终得到的 n-1 条打通边恰好构成一棵随机生成树，而树恰好保证「任意两个格子之间有且仅有一条通道」——迷宫的本质。类似的还有随机化 Prim，只是从起点一圈圈打通。两者生成迷宫风格略有差异：Kruskal 版本更「均匀随机」，Prim 版本更「树状走廊」。下次写小游戏时，这个技巧可以直接用。

图像分割。 经典算法「基于图的图像分割」（如 Felzenszwalb-Huttenlocher 算法）把每个像素看成顶点、像素间颜色差异看成边权，先按边权排序做类似 Kruskal 的合并，但合并条件不是「不成环」而是「簇内差异阈值」。它和 MST 聚类的血缘一目了然：都是在边权排序上做贪心合并。很多计算机视觉入门课会把它当成 MST 应用讲，其实它是 Kruskal 思想的「加了停止条件的亲戚」。

网络中的簇与社区发现。 在社交网络里跑 MST 再删长边，得到的是基于「互动强度」的簇；在蛋白质相互作用网络里，同样的做法可以找功能模块。虽然现代社区发现算法（如 Louvain）更复杂，但 MST 版本作为基线、可视化和教学工具至今仍有价值，因为它给「簇」提供了可解释的树状结构。

广播与组播的工程修正。 6.1 节说的最小生成树广播是理论最优；真实网络还有延迟约束、带宽约束、节点故障，所以工程上会退而求其次求「延迟有界的最小生成树」或「最小 Steiner 树近似」。理解基础 MST 是看懂这些变体的前提，这就是为什么每本图论教材都把它放在最前面。

6.8 历史花絮与延伸阅读

最小生成树的历史几乎是图论算法史的开篇。1926 年，捷克数学家 Otakar Borůvka 在解决西摩拉维亚电网规划问题时，写下了文献中最早的最小生成树算法，那是一个逐轮「每个连通块选自己最便宜的出边」的并行友好算法。之后 Jarník 在 1930 年给出了类似 Prim 的算法，但发表于捷克语的期刊，长期无人问津；直到 1957 年 Prim 在 Bell System Technical Journal 上重新发表、1956 年 Kruskal 在 Proceedings of the American Mathematical Society 上发表了基于排序的贪心算法，这两个名字才被后人记住。再后来，计算机科学家们还研究过「最小生成树能否在线性时间内求出」这个理论问题——2002 年左右的随机化算法接近线性，但确定性的严格线性算法至今仍是开放问题。对普通工程师来说，O(m log m) 的 Kruskal 已经是够用且好写的答案。

延伸阅读建议：CLRS《算法导论》第 23 章完整覆盖 MST 的贪心框架与证明；《算法》（Sedgewick）的图论卷用大量图示讲 Kruskal、Prim 和切分定理；如果想看 Borůvka 与并行 MST，Tarjan 的《Data Structures and Network Algorithms》是经典。学习路径上，接下来最自然的两个方向是：有向图的最小树形图（Chu-Liu/Edmonds 算法）和动态 MST，它们都以本篇的切分定理为思想原点。

七、总结：一条定理，两个算法

本篇信息量不小，最后把主线重新拎一遍：

问题：无向连通带权图，选 n-1 条边连通所有点，总权最小。最优解必然是一棵树，即最小生成树。

根基：切分定理——任意把顶点分成两堆，跨堆的最小边一定属于某棵 MST。证明靠交换论证：把 MST 环上与它相对的跨堆边换掉，总权不会增加。

Kruskal：边贪心。所有边排序，从小到大，用并查集判环，能选就选。复杂度 O(m log m)，适合稀疏图和边集输入。

Prim：点贪心。从一点出发，用优先队列维护跨堆候选边，每次取最小。堆优化 O((n+m) log n)，朴素 O(n²)，适合稠密图。

对比：一个「边视角」、一个「点视角」，正确性同源于切分定理；权重互异时 MST 唯一，有相等权重时可能多棵但总权相同。

7.1 两算法对比速查表

项目	Kruskal	Prim
一句话	排序边，能并则并	从点长树，挑最便宜入树
贪心对象	边	点
判环/选边工具	并查集 find/union	优先队列取最小 + visited 标记
存储偏好	边数组	邻接表 / 邻接矩阵
复杂度	O(m log m)	堆 O((n+m) log n)，朴素 O(n²)
稀疏图	★★★ 推荐	★★ 可用
稠密图	★ 一般	★★★ 朴素版推荐
不连通图	直接得到最小生成森林	一次只覆盖一个分量
正确性依据	切分定理（连通块切分）	切分定理（树内外切分）
最易踩坑	并查集忘压缩、union 写反	惰性删除漏检查、dist 写成累加
典型应用	稀疏网络布线、单链接聚类	稠密距离矩阵、在线扩张场景

7.2 自测题

7.4 如果你只有十分钟：最小必要知识

时间紧张的话，请至少带走这五句话：

1. MST 的定义：无向连通带权图里，选 n-1 条边连通所有点、总权最小，最优解必然是一棵树。
2. 切分定理：任意切分的最小跨堆边一定属于某棵 MST；Kruskal 和 Prim 每一步选的都是某个切分的最小跨堆边，所以贪心正确。
3. Kruskal：边排序 + 并查集判环，能并则并，O(m log m)，适合稀疏图；并查集务必写路径压缩和按大小合并。
4. Prim：从一点出发，优先队列维护跨堆候选边，每次取最小，堆优化 O((n+m) log n)，朴素 O(n²)，后者适合稠密图；注意惰性删除和「只比单边、不累加」。
5. 唯一性：权重互异时 MST 唯一；有等权边时可能多棵，但总权相同。

这五句话覆盖了面试和笔试 90% 的 MST 考点。剩下 10% 是应用和变体——本篇第六节已经替你把最常见的那部分都点到了。

7.5 下一篇预告

最小生成树解决的是「无向图怎么最省地连成一张网」，但现实里很多关系是有方向的：微博的「关注」不是「互关」，网页的「链接」不是「互相链接」，比赛的「胜负」没有对称性。当把方向引入图，一个新的问题出现了：在一张有向图里，哪些点之间能互相到达？把「互相到达」这种强关系抽出来，就得到了强连通分量。

下一篇《图系列第 13 篇：强连通分量》将走进有向图的世界：从强连通的定义出发，讲清楚 Tarjan 和 Kosaraju 两种经典算法，以及强连通分量在编译器、依赖分析、社交网络里的应用。到时候你会发现，DFS 的时间戳和栈这两个老朋友，又一次撑起了整个算法。

flowchart LR
    MST["第 12 篇：最小生成树<br/>Kruskal 与 Prim（无向图）"] --> SCC["第 13 篇：强连通分量<br/>Tarjan 与 Kosaraju（有向图）"]

本篇就到这里。记住那句话：Kruskal 看边，Prim 看点，切分定理是它们共同的灵魂。 我们下一篇见。