11.4 生成树与最小生成树

第 11.1–11.3 节建立了图模型、识别了连通分量，并优化了单条路线。现实中的通信、公路与电缆网络往往含有额外边。这些边提供备用路线，因此会产生环。现在要问：哪些边已经足够连接全部位置？在足够的选择中，哪一种总代价最低？

图论语言现在已经准备完毕。生成树保留连通图中的全部顶点，同时删除足够多的边，只留下树形连接骨架。

一般连接网络

一个有限无向网络由两部分组成：

• 顶点集合 $V$，表示位置或对象；
• 无向边集合 $E$，表示允许的直接连接。

这个二元组写作 $G=(V,E)$。这样的对象称为图，但本节不会假设定义之外的图论知识。

连通、路径和环沿用第 11.2 节的定义。与树不同，一般图可以含环，而且两个顶点之间可能存在多条路径。

例如，令

以及

外侧四条边形成一个环，$\{A,C\}$ 又提供一条捷径。这个网络有多种连接全部四个顶点的方法。

生成树保留全部顶点并去除冗余

连通网络 $G=(V,E)$ 的一棵生成树是一棵树

它使用 $G$ 的全部顶点，并且只使用原边集的一个子集：

“生成”表示全部原始顶点都被覆盖。我们可以删除边，却不能删除顶点或凭空创造新边。

因为 $T$ 是树，它必须通过三项检查：

1. $V$ 中每个顶点都出现； 2. 选中的边把全部顶点连通； 3. 选中的边不含环。

若 $|V|=n$，每棵生成树都有

条边。边数是快速检查，但不能代替连通性或无环性检查。

为什么每个连通网络都有生成树

从连通网络的全部边开始。如果存在环，就从环中删除一条边。环中的其余边仍然为被删边的两个端点提供备用路径，所以连通性不会被破坏。

只要还有环就继续删除。边集有限，因此过程必定终止。最终结构连通且无环，所以是一棵生成树。

这个论证本身也是一种算法：删环法把连通网络变成生成树。删除选择不同，可能得到不同生成树。

生成树是最小连接骨架

选出生成树以后，每条已选边都是桥。删除任意一条已选边都会把树分成两个连通部分。反过来，每条未选择的原网络边都连接着两个已经存在唯一路径的顶点，因此把它加入会恰好产生一个环。

这些事实给出两种建造生成树的视角：

• 删除视角：从连通网络开始，不断删除环上的边；
• 添加视角：从空边集开始，只添加能够连接不同部分且不产生环的边。

两种方法最终都用 $n-1$ 条边连接全部 $n$ 个顶点。

通过启用或停用真实链路来修复城市网络。动态连通区域会显示哪些站点仍然分离，环警报会识别冗余回路。目标不只是让边尽量少，而是用全部站点构成连通、无环的骨架。

带权网络与总代价

在带权网络中，每条边 $e$ 都附有数值权重 $w(e)$。权重可以表示电缆长度、建设成本、行驶时间或其他需要最小化的量。

生成树 $T$ 的总权重为

这个求和把每条已选树边的权重恰好相加一次。

最小生成树简称 MST，它是一棵总权重不大于同一网络中任何其他生成树的生成树。

“最小”指总权重，而不是边数。每棵生成树本来就都有 $n-1$ 条边。问题是在这些边数相同的方案中选择总代价最低的一种。

只要网络有限、无向、带权且连通，MST 就一定存在，但不一定唯一。相同权重可能允许多棵不同生成树具有相同最小总代价。如果全部边权互不相同，MST 一定唯一；边权全异是唯一性的充分条件，但不是必要条件。

负权边也不会造成逻辑困难：只要不破坏树结构，MST 会优先使用代价很低的负权边。

Kruskal 算法逐步合并森林

森林是允许拥有多个连通部分的无环结构，其中每个连通部分本身都是树。

Kruskal 算法从全部顶点互相隔离的状态开始，因此已选边构成一片森林。它按权重从小到大扫描边：

KRUSKAL(G)
    按权重非递减顺序排列全部边
    selected = 空集
    依次处理边 {u,v}
        若 u 与 v 位于不同的已选连通部分
            把 {u,v} 加入 selected
        否则
            跳过 {u,v}，因为它会产生环
    选中 n-1 条边后停止

“权重非递减”表示下一条边的权重至少和上一条相等。权重相同的边可以按任意顺序处理。

为什么连通部分检查等价于环检查？如果 $u,v$ 已经位于同一已选连通部分，二者之间已有路径，加入 $\{u,v\}$ 会把路径闭合成环。如果它们位于不同部分，二者之间没有路径，新边只会合并两棵树，不可能产生环。

一个小型 Kruskal 轨迹

假设边已经按权重排好：

• 选择 $AB:1$。
• 选择 $BC:2$，此时 $A,B,C$ 已连通。
• 跳过 $AC:3$，因为它会闭合环 $A-B-C-A$。
• 选择 $CD:4$，四个顶点全部连通。

MST 总权重为

割性质解释贪心选择为什么安全

一个割把顶点集合分成两个非空部分 $S$ 与 $V\setminus S$。如果一条边的两个端点分别位于两侧，就说这条边跨越该割。

割性质指出：

> 对任意一个割，跨越它的最小权边对于至少一棵 MST 是安全的。

可以用交换思想理解它。取一棵不含所选轻边 $e$ 的 MST。把 $e$ 加入会形成一个环，这个环必然通过另一条边 $f$ 再次跨越该割。由于 $e$ 是跨越这个割的最轻边，

删除 $f$ 后仍然得到生成树，而且总权重没有增加。因此，至少有一棵 MST 包含 $e$。

Kruskal 下一条接受的边是连接当前两个连通部分的最轻边，所以它也是某个分隔这些部分的割上的轻边。割性质证明了每次贪心接受都是安全的。

Prim 算法只生长一棵树

Prim 算法以另一种方式使用同一条割性质。任选起始顶点，用 $S$ 表示已经到达的顶点。每一步选择一条从 $S$ 跨越到 $V\setminus S$ 的最小权边，再把新端点加入 $S$。

PRIM(G, start)
    S = {start}
    selected = 空集
    当 S 尚未包含全部顶点时
        选择最小权边 {u,v}
        其中 u 属于 S，v 位于 S 外
        把 {u,v} 加入 selected
        把 v 加入 S

Kruskal 同时生长多棵树并不断合并它们；Prim 始终维护一棵连通树。在同一个连通带权无向网络上，两种算法都会返回 MST；存在权重并列时，它们可能返回不同但同样最优的 MST。

亲自在带权岛屿网络中选择桥梁。可以切换 Kruskal 与 Prim 规则，检查当前允许的前沿或连通部分合并，并挑战隐藏的最优总价。产生环或不在前沿的选择仍会保留显示，让拒绝原因变得具体。

本节检查表

• 生成树使用全部原始顶点，而且只能选择原始边。
• 生成树连通、无环，并且有 $n-1$ 条边。
• 删除环上的边可以保持连通，直到得到树。
• MST 最小化的是边权总和，而不是边数。
• Kruskal 添加合并不同连通部分的轻边。
• Prim 添加从当前生长树跨向未到达顶点的轻边。
• 割性质解释了每条被接受的轻跨越边为什么安全。
• 权重并列时可能存在多棵总代价相同的 MST。

第 11.5 节会从选择最低成本骨架转向路线覆盖：能否用一次行程恰好走过每条边，或恰好访问每个顶点？