5.2 最小生成树：Prim 与 Kruskal

动机

假设需要用电缆连接多个地点。如果要求只是任意地点都能到达其他地点，就不一定要从 某个指定起点分别铺设最短路线；多条路线可以共享一部分连接，从而降低整个网络的建造 总成本。这正是最小生成树（minimum spanning tree，MST）所解决的问题。

本节最关键的区别是：局部便宜不等于全局最优。一条边的权重很小，并不意味着可以不经 判断就选它；把所有便宜边都加入可能形成环。环表示连接存在冗余，因为删去环上的一条 边以后，环中的顶点仍然连通。Prim 和 Kruskal 都是贪心算法，但它们并不是简单地说 “每次选择最轻的边”。两种算法都会明确当前哪些边有资格被选，并拒绝破坏树结构的边。

以下设 G=(V,E) 是有限、非空、连通、无向的加权图，每条边 e 都有实数权重 w(e)。连通性是必要假设：不连通的图不可能有一棵包含所有顶点的树。权重不必互不 相同，也不必非负；相同权重可能使同一张图拥有多棵形状不同、总权重相等的 MST。

定义

定义

树与生成树

树是连通且无环的无向图。G=(V,E) 的生成树是子图 T=(V,E_T)： 它保留 G 的所有顶点，所选边集合 E_T 是 E 的子集，并且 T 本身是一棵树。

只有一个顶点的图以空边集为生成树。如果 G 不连通，就不存在生成树；此时最多只能 得到生成森林（spanning forest），每个连通分量对应一棵树。

定义

最小生成树

生成树 T 的权重定义为

$$w(T)=\sum_{e\in E_T} w(e).$$

如果 T 的总权重不大于 G 中任何其他生成树的总权重，T 就是最小生成树。 “最小”比较的是所选边的权重之和，而不是边数；所有生成树本来就具有相同的边数。

定义

切割、跨越边与安全边

一个切割（cut）把 V 分成两个非空集合 S 和 V\setminus S。如果一条边 的两个端点分别位于两侧，它就跨越该切割。如果当前森林 F 中没有任何已选边跨越 切割，就称这个切割尊重 F。

如果把一条边加入 F 后，仍然存在某棵 MST 包含所有已选边，这条边对 F 就是 安全边。安全不只是“暂时没有形成环”；它把避免环与最终的全局最优性联系起来。

MST 还不同于最短路径树。最短路径树先指定源点 s，要求树中从 s 到每个 可达顶点的路径都保留原图中的最短距离。MST 没有指定源点，只最小化树边的总权重。 因此，MST 中两个顶点之间的路径不一定是原图中的最短路径。

定理 / 命题

定理

树的边数

任何顶点集合为 V 的树都恰好有 |V|-1 条边。因此，只要一个生成子图连通、无环， 并且已经有 |V|-1 条边，它就是完整的生成树。反过来，连通且有 |V|-1 条边的无向图 一定是一棵树。

这个事实为两种算法提供了精确的停止条件。在接受 |V|-1 条边之前，当前结构仍然是 森林；如果再多接受一条边，就一定会形成环。

定理

最轻跨越边的安全原则

设森林 F 包含在某棵 MST 中，并且某个切割尊重 F。在所有跨越这个切割的边中， 如果 e 的权重最小，那么 e 对 F 是安全的：存在一棵 MST 同时包含 F 的 全部边和 e。

Prim 把该原则用于“已进入当前树的顶点”和“尚未进入的顶点”之间的切割。Kruskal 则把它用于当前森林中某个连通分量周围的切割。两者对候选边的定义不同，但保证最优性 的理由是相同的。

证明思路

先证明树的边数。对顶点数进行归纳：一个顶点的树有零条边。任何至少含有两个顶点的 有限树都有叶节点。删去一个叶节点及其唯一的关联边后，剩余图仍然是一棵树，只是少了 一个顶点。根据归纳假设，它有 |V|-2 条边；把删除的边放回，就得到 |V|-1 条边。

再证明安全边原则。设 MST M 已包含 F。如果 M 本来就有 e，则不需要改动。 否则，把 e 加入 M；由于 M 是树，这会恰好产生一个环。这个环必须进出切割的 两侧，因此环上还存在另一条跨越边 f。切割尊重 F，所以 f 不属于 F。因为 e 是最轻跨越边，所以 w(e) ≤ w(f)。用 e 替换 f 后，所得图仍是生成树， 仍包含 F，总权重也没有增加。原来的 M 已经是最小的，因此替换后的树仍是 MST。 这个交换论证说明贪心选择能够扩展成全局最优解。

对 Prim 来说，每条接受边恰有一个端点位于当前树内，所以它跨越相关切割且不会成环。 对 Kruskal 来说，如果候选边 (u,v) 的两个端点属于不同森林分量，就考虑包围 u 所在分量的切割。按照非递减权重处理边，使该候选成为仍然相关的最轻跨越边，因此可以 应用交换论证。

例题详解

例题

MST 不是最短路径树

考虑一个三角形：s-a 的权重为 2，s-b 的权重为 2，a-b 的权重为 1。 一棵 MST 会选择 a-b，再从 s-a 与 s-b 中选择一条，总权重为 3。

但是，如果源点是 s，最短路径树必须同时使用两条权重为 2 的边。从 s 直接到 a 或 b 的距离都是 2，经过另一个非源点顶点则需要 3。这棵最短路径树的 树边权重之和为 4。它解决的是源点距离问题，而 MST 解决的是整个网络的总连接成本 问题。

Prim 算法

Prim 维护已经进入树的顶点集合 S，每次接受恰有一个端点在 S 内的最轻边。 Tutorial 9 使用边优先队列，所以下面的版本与课件中的状态相匹配：

PRIM_WITH_EDGE_QUEUE(G, start):
    inTree[v] ← false，对每个顶点 v
    T ← 空边集合
    pq ← 保存 (weight, from, to) 的最小优先队列

    inTree[start] ← true
    把所有 (start, x) 且 x 尚未 inTree 的边加入 pq

    当 pq 非空并且 |T| ≠ |V| - 1：
        (weight, u, v) ← pq.popMin()
        如果 inTree[v]：
            跳过                 // 过期边；两个端点都在 S 内
        否则把 (u, v) 加入 T
        inTree[v] ← true
        对每条边 (v, x)：
            如果 x 尚未 inTree，把 (weight(v,x), v, x) 加入 pq

    如果 |T| ≠ |V| - 1，报告“图不连通”；否则返回 T

例题

Tutorial 9 的完整 Prim 追踪

课件图的顶点为 A,B,C,D,E，加权边为

AB=1, BD=2, BC=3, AD=5, DE=6, DC=7, CE=8。

从 A 开始。下表同时记录已接受的树边和优先队列中的关键动作。

步骤	当前顶点集合 S	队列动作与决定	已接受边
0	{A}	放入 AB(1), AD(5)	无
1	{A,B}	取出 AB(1)；放入 BD(2), BC(3)	AB
2	{A,B,D}	取出 BD(2)；放入 DE(6), DC(7)	AB, BD
3	{A,B,C,D}	取出 BC(3)；放入 CE(8)	AB, BD, BC
4a	不变	取出 AD(5) 并拒绝：两端已经在 S 中	不变
4b	五个顶点都在内	取出并接受 DE(6)	AB, BD, BC, DE

所得树有四条边，符合五个顶点的要求，总权重为 1+2+3+6=12。拒绝 AD 并不是 可有可无的队列清理，而是边优先队列版本的防环步骤；如果接受 AD，就会闭合 A-B-D-A 这个环。

使用邻接表时，每条边会在其中一个端点加入树时被检查，压入和弹出的队列项总数至多为 O(E)。二叉 heap 最多保存 O(E) 个项，因此时间为 O(E log E)，空间为 O(V+E)。对简单图有 log E=O(log V)，所以也常写成 O(E log V)。这个分析 针对的是上面的边队列版本；如果改用邻接矩阵并在每一轮扫描所有顶点，时间将是 O(V^2)。

Kruskal 算法

Kruskal 不需要起点。开始时每个顶点各自构成一个分量；算法把所有边按照权重非递减 排序，并且只有当候选边的两个端点当前属于不同分量时才接受它。

下面这个课程层次的实现在当前森林中搜索，以判断两个端点是否已经连通；它不假设任何 额外的分量数据结构。

KRUSKAL_WITH_FOREST_SEARCH(G):
    edges ← 所有边，按权重非递减排序
    F ← 包含全部顶点但没有边的图
    如果 F 已有 |V| - 1 条边，返回 F    // 处理单顶点图

    依次处理 edges 中的 (u, v)：
        如果 HAS_PATH_BY_DFS_OR_BFS(F, u, v)：
            跳过                 // 加入 (u,v) 会形成环
        否则把 (u, v) 加入 F
        如果 F 已有 |V| - 1 条边，返回 F

    报告“图不连通”

例题

同一来源图的完整 Kruskal 追踪

排序结果为

AB(1), BD(2), BC(3), AD(5), DE(6), DC(7), CE(8)。

候选边	决定前的端点状态	决定	决定后的森林
AB(1)	A、B 分离	接受	{AB}
BD(2)	B、D 分离	接受	{AB,BD}
BC(3)	B、C 分离	接受	{AB,BD,BC}
AD(5)	已有路径 A-B-D	拒绝：否则形成 A-B-D-A	不变
DE(6)	E 与其余分量分离	接受并停止	{AB,BD,BC,DE}

总权重同样为 12。接受四条边以后无需再处理 DC(7) 和 CE(8)。在这个例子中， 边权重使有效选择的先后顺序没有歧义，所以 Prim 与 Kruskal 得到同一棵树；存在等权边 时，两者可能返回形状不同但总权重相同的 MST。

排序成本为 O(E log E)。在这里描述的实现中，已接受边始终构成森林，边数少于 V；因此，在该森林中执行一次 DFS 或 BFS 最坏需要 O(V)，而每条候选边都可能 触发一次搜索。总时间为 O(E log E + EV)，空间为 O(V+E)，其中包括排序边表和 森林。如果只给出 O(E log E)，就忽略了文中明确执行的遍历式成环测试，与实际实现 并不匹配。

常见错误

常见错误

Prim 直接选择全图中剩余的最轻边

Prim 只能选择从当前树跨到外部顶点的边。连接两个外部顶点的便宜边不会扩展当前树； 连接两个内部顶点的边已经过期，接受它会形成环。

常见错误

Kruskal 看到所有顶点后就停止

多个互不连通的分量合在一起也可以提及所有顶点。只有接受 |V|-1 条边后才可以停止； 对于连通输入，此时森林才合并为一棵生成树。

常见错误

把 MST 中的路径当成最短路径

MST 只最小化一个全局总和，不保证其中指定两点之间、或从指定源点出发的路径，是原图 中成本最低的路径。

常见错误

误以为 MST 要求权重非负

非负限制属于 Dijkstra 的贪心确定论证，而不是 MST。即使存在负权边，Prim 和 Kruskal 仍然有效；切割与交换论证只比较权重大小，从未假设权重非负。

总结

• 无向图连通时才有生成树；生成树包含全部顶点和恰好 |V|-1 条边。
• MST 最小化所选边的总权重，但它不是最短路径树。
• Prim 使用跨越当前切割的最轻边，逐步扩展一棵连通树。
• Kruskal 按照权重顺序扩展森林，如果候选边的两个端点已经连通就拒绝它。
• 最轻跨越边的交换论证说明两种贪心选择为何安全；显式成环检查则保持树结构。
• 复杂度必须匹配表示方法和数据结构：文中的 Prim 边队列为 O(E log E)；Kruskal 若用遍历检查成环，则为 O(E log E + EV)。

练习

思考检查

检查 1：一张连通图有 9 个顶点。它的任何生成树必须有多少条边？为什么不能更多？

同时使用“树”的两个条件：连通且无环。

思考检查

检查 2：在 Tutorial 9 图中，Prim 已接受 AB、BD 和 BC。接下来会检查哪条队列边、如何处理，然后接受哪条边？

检查候选边的两个端点是否都已经在当前树中。

思考检查

检查 3：为什么只写 O(E log E)，不足以描述本节使用遍历测试成环的 Kruskal 实现？

除排序之外，还需要计算每次 HAS_PATH 的成本。

1. 在 Tutorial 9 图中删去 BD(2)，对剩余六条边执行 Kruskal。记录每次接受或 拒绝，并计算最终总权重。
2. 证明 Kruskal 使用的成环判据：把 (u,v) 加入森林会形成环，当且仅当森林中 原来已经有一条从 u 到 v 的路径。
3. 构造一张存在两棵不同 MST 的连通加权图，并指出哪个权重相等情形允许两个答案。
4. 解释为什么 Prim 在不连通图上必须报告失败，即使优先队列的实现完全正确。

答案与解答

解答 · 检查 1 解答

必须有 9-1=8 条边。连接九个顶点至少需要八条边，而树恰好达到这个下界。如果再 加入第九条边，它会连接两个在树中已经有唯一路径的顶点，因此形成环。

解答 · 检查 2 解答

队列的下一项是 AD(5)。A 和 D 都已经在树中，所以该项已经过期，必须拒绝； 否则会形成 A-B-D-A。然后 Prim 接受 DE(6)，把 E 加入树并完成四边 MST。

解答 · 检查 3 解答

排序需要 O(E log E)，但每个候选都可能在有 V 个顶点、少于 V 条边的森林中 触发一次 DFS 或 BFS。一次搜索为 O(V)，最多执行 E 次，另外贡献 O(EV)。 因此与本文实现匹配的界为 O(E log E + EV)。

解答 · 较长练习的引导解答

1. 新顺序为 AB(1), BC(3), AD(5), DE(6), DC(7), CE(8)。依次接受 AB、 BC、AD、DE；此时四条边已经连接五个顶点，总权重为 1+3+5+6=15，停止 之前没有候选边被拒绝。
2. 如果原来已有从 u 到 v 的路径，那么这条路径和 (u,v) 一起构成一个环。 反过来，如果新增 (u,v) 后出现环，从该环中删去新边，剩余部分就是原森林里的 u 到 v 路径，因此两个条件等价。
3. 令一个三角形的三条边权重都为 1 即可。任意两条边都构成总权重为 2 的生成树， 因此共有三棵 MST。权重相同时，安全的最轻边不一定唯一。
4. Prim 只能到达起点所在的连通分量。最终优先队列会变空，但接受边仍少于 |V|-1。 已到达分量与其余顶点之间不存在跨越边，这恰好证明整张图不存在生成树。