算法与数据结构 · 第 24 课
最小生成树:为什么选一条最轻的跨割边,永远不会选错?
2026 年 11 月 12 日|第 4 周 · 第 4 天|讲授约 17 分钟(自测另计)
前三节讨论 Bellman–Ford、Dijkstra 和 Johnson:目标是让两个顶点之间的路径尽量短。今天的目标不同——用总权重尽可能小的边,把整个无向图连接起来。MST 的核心不是松弛,而是一个可以严格证明的贪心规则:割性质。
一、学习目标与定义(约 2 分钟)
学完应能:①区分最短路径树与最小生成树;②解释割、跨割边和安全边;③用交换论证证明割性质;④手工追踪 Kruskal 和 Prim;⑤分析并查集、最小堆的复杂度,以及负边、等权、非连通图的边界。
考虑连通、无向、加权图 (G=(V,E)),顶点数 (n),边数 (m)。生成树 (T\subseteq E) 连接全部顶点且没有环,因此恰好有 (n-1) 条边。最小生成树(MST)使 (\sum_{e\in T}w(e)) 最小。允许负权、零权和相同权值。若图不连通,则不存在覆盖全部顶点的一棵生成树;对应问题是最小生成森林(MSF)。
二、动机:MST 不是从源点出发的最短路树(约 2 分钟)
看三角形:(w(A,B)=2,\ w(B,C)=2,\ w(A,C)=3)。若要求从 A 到每个顶点的距离最短,保留 A–B 和 A–C,可得到距离分别为 2 和 3,树的总边权为 5。但如果目标是整个网络的铺设成本最低,可以采用 A–B 和 B–C,总成本 4;此时 A 到 C 的树上路径长度是 4,并不是原图中的最短距离 3。
所以最短路优化的是路径代价,MST 优化的是所选所有边的代价总和。后者不会指定源点。它适用于连通网络铺设、聚类等问题,但不能直接代替最短路算法。
三、割性质:看似局部的选择为何安全?(约 3 分钟)
一个割把顶点划成两个非空部分 ((S,V\setminus S))。一条边若一个端点在 S、另一个端点在外侧,就叫跨割边。假设已经选定一组不成环的边 (A),且至少存在一棵 MST 包含 A。若割没有被 A 中任何边跨越,就说这个割尊重(respects)A。
割性质: 在一个尊重 A 的割上,任选一条权重最小的跨割边 e,都可以把它安全加入 A:仍然存在某棵 MST 包含 (A\cup{e})。
flowchart LR
subgraph S["割的左侧 S"]
A((A))
B((B))
end
subgraph R["割的右侧 V∖S"]
C((C))
D((D))
end
A ---|"3"| C
B ---|"5"| D
B ---|"8"| C
图中跨割边的权重为 3、5、8。割性质关心的是跨越某个割的最轻边,不是随便找某个顶点相邻的最轻边。内部边可以在割的任意一侧,且不影响这一条规则。
交换证明: 取一棵包含 A 的 MST,记作 T。若 e 已在 T 中,无需调整。否则把 e 加入 T,会形成一个环;因为 e 跨越这个割,环中必定还有另一条跨割边 f。由于割尊重 A,f 不可能属于 A。又因为 e 是跨割最轻边,(w(e)\le w(f))。将 f 从环中删掉,得到另一棵生成树 (T’=T+e-f),其总权重不大于 T。T 已是 MST,故 T’ 也必是 MST,而且包含 (A\cup{e})。
这里证明的是“至少存在一棵 MST 可以包含 e”,并不是说等权时所有 MST 都必须包含它。这个量词区别非常重要。
四、Kruskal:从全局最轻边开始,避免形成环(约 3 分钟)
Kruskal 将全部边按权重升序排序。依次考虑每条边:若两个端点还不属于同一个连通块,就选入;否则跳过,因为加入会构成环。连通块可以用并查集 DSU 高效维护。
KRUSKAL(V, E):
sort E by nondecreasing weight
DSU.INIT(V)
chosen = []
for (u,v,w) in E:
if DSU.FIND(u) != DSU.FIND(v):
chosen.append((u,v,w))
DSU.UNION(u,v)
return chosen
手工看一个有 6 个顶点的例子(所有边均为无向边):
graph LR
A((A)) ---|"2"| B((B))
A ---|"3"| C((C))
B ---|"1"| C
B ---|"4"| D((D))
C ---|"5"| D
C ---|"6"| E((E))
D ---|"2"| E
D ---|"7"| F((F))
E ---|"3"| F
按权重扫描的关键步骤:
| 边(权重) | 处理 | 处理后的连通块 |
|---|---|---|
| B–C (1) | 选入 | {B,C}、{A}、{D}、{E}、{F} |
| A–B (2) | 选入 | {A,B,C}、{D}、{E}、{F} |
| D–E (2) | 选入 | {A,B,C}、{D,E}、{F} |
| A–C (3) | 跳过(成环) | 不变 |
| E–F (3) | 选入 | {A,B,C}、{D,E,F} |
| B–D (4) | 选入 | 六个点连通 |
已选 5 条边,总权重 (1+2+2+3+4=12),得到 MST。权重相等的边可以采用任意一致的排序顺序,最优总权重不受影响,但所选边集合在一般图中可能不同。
为什么 Kruskal 的选择满足割性质?每次选择连接两个不同 DSU 分量的最轻剩余边 e。令 S 为 e 其中一端所在的整个分量,所有此前选边均在某个当前分量内部,所以割尊重已选边;任何更轻的跨割边若存在,本应早已被扫描并合并这两个分量,矛盾。因此 e 是这个割上的最轻边,可以安全加入。循环不变量是:已选边无环,而且能扩展成某棵 MST。
五、Prim:从一个连通区域向外扩张(约 2 分钟)
Prim 的思考顺序不同:先选一个起点,例如 A;已访问顶点集合为 S,每次挑选连接 S 与外部顶点的最轻边,把新顶点加入 S。使用最小堆维护候选跨割边:
PRIM(G, start):
visited = empty set
pq = min_heap([(0, start, NIL)])
chosen = []
while pq not empty:
(w, u, from) = pq.pop_min()
if u in visited: continue
visited.add(u)
if from != NIL: chosen.append((from,u,w))
for each edge (u,v,cost):
if v not in visited:
pq.push((cost,v,u))
return chosen
在同一张图从 A 出发,Prim 依次选 A–B(2)、B–C(1)、B–D(4)、D–E(2)、E–F(3),最终也是总权重 12。Prim 的选边次序不必按全局权重升序:因为它只能选择从当前 S 跨到外部的边。每一步的割 ((S,V\setminus S)) 尊重已选树边,故由割性质保证安全。
对不连通图,上述 Prim 只覆盖起点所在的分量;如需 MSF,应对每个尚未访问的顶点重新启动一次。
六、正确性、复杂度与实现选择(约 2 分钟)
Kruskal 每一步用割性质保持“已选边可扩展成 MST”,并查集阻止成环;在连通图中最终选到 n−1 条边,得到的树自身就是一棵 MST。Prim 每一步通过当前已访问集合形成一个尊重已选边的割,选择最轻跨割边;最终访问所有顶点,得到 MST。
| 方法 | 主要操作 | 典型时间 | 额外空间 |
|---|---|---|---|
| Kruskal + DSU | 边排序、FIND/UNION | (O(m\log(m+1)+(n+m)\alpha(n))) | DSU (O(n)),排序另计 |
| Prim + 二叉堆(重复入堆) | 每边生成堆候选、跳过旧项 | (O(n+m\log(m+2)))(连通图) | 堆 (O(m)),访问标记 (O(n)) |
| Prim + 邻接矩阵 | 每次线性找最轻跨割边 | (O(n^2)) | 邻接矩阵 (O(n^2)) |
这里 (\alpha(n)) 是反 Ackermann 函数,增长极慢;Kruskal 若用按大小合并加路径压缩,DSU 总操作具有近常数的分摊界。对连通简单图,常把 Kruskal 简写为 (O(m\log m))。表格的额外空间不包含保存输入边或邻接表;Prim 重复入堆时,堆操作的对数依赖 m,而不是直接假定每个顶点只在堆中出现一次。
七、前提、反例与下一课(约 2 分钟)
负边可以用于 MST。 割的交换证明仅比较两条边的大小,从来没有要求权重非负;这与 Dijkstra 截然不同。等权时 MST 可能不唯一,但割性质仍保证任选一条最轻跨割边是安全的。非连通图只能产生 MSF。标准 MST 面向无向图;有向图若要求从某根可达所有点的最小树状结构,属于有向最小树形图(arborescence),不能直接套用这里的割性质和 Kruskal。
还有一个典型陷阱:“把每个顶点最便宜的邻边都选进来”可能形成环,或漏掉连接两个区域必需的较贵边。Kruskal 的“不能成环”和 Prim 的“必须跨当前割”是正确算法的重要约束。
下一课(2026-11-13,第 25 课):最短路与 MST 的正确性证明专题。 比较 Bellman–Ford 的边数归纳、Dijkstra 的定型不变量、Johnson 的势函数保序,以及 MST 的交换论证,为第 4 周综合考核做准备。
八、四级自测(100 分;首次不公布答案)
前 3 题可客观判分,Lv4 为开放推导。以下只提供中立提示,不公布标准答案或逐题解析。
Lv1|割性质的安全性与量词|15 分|预计 2 分钟|单选
设 A 是一组已选、无环、且存在某棵 MST 包含它的边。关于尊重 A 的割与跨割最轻边 e,下列哪项严格正确?
A. e 必须属于原图的每一棵 MST,即使存在相同权值的跨割边。
B. 将 e 加入 A 后,仍存在至少一棵 MST 包含所有 (A\cup{e}) 中的边。
C. e 只有在权重严格大于零时才是安全边。
D. 只要 e 是某个顶点的最便宜邻边,就完全不需要考虑割或是否成环。
中立提示:特别区分“存在一棵”与“每一棵”,并检查割需要尊重哪些已选边。
Lv2|Kruskal 完整扫描与数值 Trace|20 分|预计 4 分钟|数值
无向连通图有顶点 A、B、C、D、E、F,边为 A–B(1)、A–C(4)、B–C(2)、B–D(5)、C–D(3)、C–E(7)、D–E(6)、E–F(2)、D–F(8)。用 Kruskal 按权重升序处理,成环的边跳过;求最终 MST 的总权重(只提交一个数值,可附计算过程)。
中立提示:维护每一步的连通块;较轻的边若两端已经连通,就不能再加入。
Lv3|负边、等权与非连通边界|25 分|预计 4 分钟|多选
关于无向加权图的 MST,下列哪些结论成立?(多选,选出全部正确项)
A. 边权允许为负数;Kruskal 的割性质证明不要求所有边权非负。
B. 只要图中有两条权重相等的边,MST 就一定不唯一。
C. 对非连通图运行 Kruskal,可以得到各连通分量的最小生成树所构成的最小生成森林。
D. 对任意连通非负权图,从某个源点建立的最短路径树一定也是该图的 MST。
中立提示:区分算法使用的权值前提、不同生成树可能的总权重,以及“路径最短”和“所有边总和最小”的目标。
Lv4|割性质交换证明与双算法设计|40 分|预计 10 分钟|开放推导
给定连通、无向加权图 G=(V,E),允许负边和等权。(a)(12 分)严格定义割、跨割最轻边以及割尊重已选边 A 的含义;使用“向某棵包含 A 的 MST 加边形成环,再删去一条跨割边”的交换论证证明割性质,特别处理等权情形。(b)(10 分)写出 Kruskal 的伪代码,证明已选边无环且始终能扩展为一棵 MST,并说明为什么最终得到 MST。(c)(10 分)说明 Prim 怎样用当前访问集合形成一个割,写出堆版本关键步骤,并分别分析 Kruskal+DSU 与 Prim+堆的时间、额外空间复杂度。(d)(8 分)构造一个最短路径树不是 MST 的小图,解释负边、等权和非连通图对 MST 算法及结果的影响。
中立提示:证明时先选一棵包含 A 的最优树 T;加入跨割边会形成环,留意环上另一条跨割边及其权重关系。复杂度分别计算排序、并查集、堆入出次数。
九、提交与反馈
请回复 Lv1:选项;Lv2:数值与选边过程;Lv3:全部正确选项;Lv4:(a)–(d) 分步证明。我会按 15/20/25/40 分逐题批改:80–100 分按课表继续;60–79 分补一道定向练习;低于 60 分重点复习割性质的交换证明与 Kruskal/Prim 的状态不变量。补练不修改自然日课号。