动机
要把多个地点连起来,可以选择一组无向线路,使线路总成本尽量小。从某个起点到每个地点都最便宜的一组路径,未必给出总成本最低的网络:网络问题选择的是共享边集,每条选中的边只计一次。
两种贪心算法按不同次序建网。Kruskal 按权重扫描所有边;Prim 则逐步扩大一个连通区域。两者共用一个关键解释:跨越合适割的最轻边,可以通过交换放进一个最优解而不增加成本。边权相等或已经选过一些边时,“合适”这一条件尤其重要。
定义与范围
定义 5.4.1
(生成森林与最小生成森林)
令 为有限无向多重图,有 个顶点和 个各自具有身份的边。允许平行边和自环。每条边有有限实权,权可以为负、为零或相等。生成森林包含所有顶点,并在 的每个连通分支上限制为一棵生成树。孤立顶点贡献单点树,不贡献边。最小生成森林是在这些森林中总边权最小的一个。若 非空且连通,它就是最小生成树(MST)。当 时,空森林总权为零;我们不把空图称作连通。
定义 5.4.2
(割、跨割边与尊重)
割由非空真子集 及其补集指定。边的两个端点分别在两侧时,它跨越该割。若森林 没有边跨割,就说该割尊重 。自环不跨任何割,也不能属于森林。一个圈可以由两条不同平行边构成;提到圈或边时,都需保留边的身份。
有限图存在生成森林,例如在每个分支取一棵生成树。边子集只有有限多个,因此至少存在一个最小生成森林。这个存在性论证也适用于任意有限实权,无需非负假设。
定理 5.4.3
(尊重已有选择的割上最轻边安全)
设森林 包含在某个最小生成森林中。若一个割尊重 ,且边 在所有跨割边中权最小,则存在一个最小生成森林包含 。允许同权;结论是存在包含所选边的最优解,而不是每个最优解都包含它。
割交换证明
证明
(沿 产生的圈交换)
取包含 的最优森林 。若 已在 中,无需交换。否则 的端点位于原图同一个连通分支, 在该分支的树中有连接两端点的唯一路径。这条路径必跨越该割。加入 后得到由路径和 构成的圈;从其余圈边中再选一条跨割边 。
由于割尊重 ,边 不在 中。删去 破圈后,该原分支仍有一棵生成树,其余分支不变。由于 是最轻跨割边,。新生成森林包含 ,权不超过最优森林 ,因此它也是最优的。证明允许平行边和同权,从未假设最优解唯一。
证明透视
交换必须保留先前选择
证明只做一次交换,而每个假设控制新森林的一个不同性质。 的两端点位于割的两侧,迫使它们之间的 -路径含有一条跨割边 ;这是割本身被用到的地方。从 与该路径构成的圈中删去一条边,分支仍连通且无圈,所以结果仍是生成森林;这只需要 在圈上。
在跨割边中最轻,给出 ,所以成本不上升。最后,割尊重 保证 ,因此先前每次选择都在交换后保留。缺少最后这一性质,交换便可能删去 中的边,Kruskal 与 Prim 所用的归纳就会失去其不变量。同权只把严格改进变为不增加,而结论只需要不增加。
定理 5.4.4
(圈上的排除与同权)
若一条边严格重于某个圈上的所有其他边,它不属于任何最小生成森林。更一般地,圈上一条最大权边即使与其他边同权,也至少有一个最小生成森林不使用它。
证明
(以跨越分割的边替换圈边)
对于两条结论,假设某个最优森林含所指定圈边 。删除 后,其所在树分为两侧。原圈的其余部分有一条边 跨越这个分割。它不在原树中,因为一棵树删除 后没有其他树边跨越该分割。以 替换 后仍是生成森林。若 严格更重,总权下降而矛盾;若 只是最大权,新森林不更重,因而也是不含 的最优解。同权最大边仍可能出现在另一个最优解中。
Kruskal:按权重扩展森林
按非递减权重排序所有边身份,同权次序任取且固定。初始不选边。依次扫描排序后的边;仅当边的端点位于当前已选森林的不同分支时选取它。自环自动被丢弃。继续直至所有边都已检查。
定理 5.4.5
(Kruskal 算法的正确性)
对每个有限加权多重图及任何固定的同权次序,Kruskal 算法选出的边构成一个最小生成森林。
证明
(已选森林始终包含在某个最优解中)
选出的边始终无圈:连接两个不同森林分支的边不可能闭合圈。在接受 前,取其一个端点所在当前森林分支的顶点集为 。该割尊重已选森林。任何更轻的跨割边早已扫描;它当时不可能被拒绝,因为分支只会合并,而它的端点到现在仍分离。因此不存在更轻跨割边, 是最轻跨割边。割定理保证“已选森林包含在某个最优森林中”的不变量继续成立。
扫描结束时,没有原图边连接两个不同的已选森林分支:这样的边在检查时会被选取,或其端点届时早已合并。因此已选森林在每个原分支上都生成一棵树。它包含在一个最优森林中,且已生成每个分支,所以它本身就是最优森林。
并查集可支持分支判断。按大小合并且不压缩路径时,每条父指针链长度为 :每次根接到另一根下,其分支大小至少翻倍。比较排序与这些操作合计使用 次比较与索引操作,存储包括输入共 。更快的并查集界需要另行分析。这里假设权重比较精确且每次费用为常数;任意二进制权重表示另有位成本。
概念视角结构
把森林看成拟阵的独立集
若一个边集不含圈(环边除外),就称它是独立的。森林的子集仍是森林。若 、 都是森林且 ,则在同一顶点集上 的连通分支较少,所以 有某条边连接 的两个分支,可以加入 。这两个性质使森林成为一个拟阵的独立集,其极大成员正是生成森林。Kruskal 就是拟阵上的贪心算法,而这个扩充步骤正是上面的交换论证。
Prim:扩展区域,再重新开始
在原图的一个连通分支任选起点。设 为当前已到达顶点, 为已选边。只要存在从 到其外侧的边,就添加一条最轻跨割边及它的外侧端点。已选边始终是 上的一棵树,该割尊重这些边。交换定理保持“某个最优森林包含全部已选边”。没有跨割边时, 恰好是整个原连通分支。
图不连通时,在任意尚未到达的顶点重新开始,对其分支执行同样规则。所得各树的并是一个生成森林,且包含在某个最优森林内,因此自身最优。孤立顶点不需要边。同权可任意打破,并可能得到不同的有效森林。
一种直接实现为每个未到达顶点维护一条已知的、来自当前到达区域的最便宜边。数组扫描选择最小有限键;没有有限键时,在未到达顶点重新开始。每个新到达顶点的邻接表扫描一次。对全图,初始化及数组扫描用 ,查边用 ,包含输入的存储为 。键是单条跨割边的权,不是路径长度。无穷大用独立的“无候选”标记表示;负边不会造成问题。
检查整个候选森林的证书
定理 5.4.6
(路径最大权的最优性判据)
设 是 的一片生成森林。它最小,当且仅当对于每条不在 中的非自环边 ,其权至少是两端点之间唯一 -路径上边权的最大值。
证明
(必要性用一次交换,充分性用反复交换)
必要性:加入一条森林外边 。如果它比路径上某条边更轻,就可用 替换该路径边,得到更便宜的生成森林。平行边同样适用;排除自环是因为其端点间路径为空,且自环不能改进森林。
充分性:设显示的不等式成立,任取一个生成森林 。若它不同于 ,选 。从 的相应树中删去 ,把原分支分成两部分。向 加入 得到一个圈,圈中剩余路径必跨越这个分割;取路径上一条这样的边 。除 外, 中没有边跨越该分割,所以 。 两端在 中的路径含 ,由假设得 。在 中以 换 不增加总权,而且增加它与 的共同边数。有限次重复后森林变成 。因此 的权不超过任何竞争森林,它就是最小的。
这是可检查的刻画,并不自动给出线性时间验证器。直接实现可以先检查生成森林性质,再对每条森林外边遍历树路径;在直接的邻接表模型下使用 次基本操作。更快的路径最大值数据结构属于另一算法问题。判据也适用于负权:应取非空路径上真正的最大值,不能把初始最大值设为零。
例题
例题 5.4.7
(次序不同,最优结果相同)
取顶点 ,边权为 、、、、。Kruskal 依次选 、、,总权 。从 开始的 Prim 依次选 、、,总权相同。Kruskal 的首边不必接触 Prim 的起点,负权也是允许的。
例题 5.4.8
(同权带来多棵最优树)
一个四边圈的四条边权都为一,删去任意一条边都得到权为三的最小生成树。某条所选边可以是某个割上的最轻边,却不必属于每个最优解。如果再加一条权为二的对角线,它在包含它的任一三角圈上都严格最重,因此不属于任何最小生成树。
例题 5.4.9
(断开图与平行边)
设 之间有两条权分别为 、 的平行边, 为孤立顶点, 处有权 的自环。最小生成森林使用权为 的边,把 作为单点,并忽略自环和较重的平行边。总权为 。负自环虽然能降低不受约束的边权和,也不允许选入森林。
反例模式
最短路树未必使网络总权最小
取三角形,边权 、、。从 到两点都取直接边可得到最短路树,其总权为四。最小生成树使用 与一条权为二的边,总权为三;但从 到另一端的路径成本为三,所以它不是以 为源的最短路树。
常见错误与范围
常见错误
(割上最轻边未必属于每个最优解)
有同权时,不要断言每条割上最轻边都属于每个最优解。在四条边权都为一的四边圈中,每条边都是某个割上的最轻边,但删去该边所得的生成树就不含它。
常见错误
(不尊重先前选择的割)
声称先前所有选择均可保留时,不要把尊重已有森林的割换成任意割。在 、 的三角形中,森林 包含在最小生成树 中。割 不尊重 ,而 是跨越它的最轻边之一,但 的权为 ,而每棵最小生成树的权都是 。
常见错误
(在断开图上只运行一次 Prim)
对于断开图,若 Prim 只运行一次,就只得到一个分支的树,而非全图生成森林。自环即使为负也不能选:它从不跨越任何割,所以 Prim 永远不会把它当作候选。
以上权重比较都是精确的。我们不声称浮点鲁棒性、特定堆实现或最短路保证。按边权总和优化的网络,与固定源点最短距离是不同目标。
小结
割交换引理安全扩展一个部分最优选择;圈上严格最重边则不可能出现。Kruskal 与重新启动的 Prim 按不同次序使用这些事实,都给出最小生成森林。路径最大值条件独立刻画最优性,其验证实现成本需另行说明。
练习
快速检查
(对第一个例题中的加权图运行 Kruskal 和从 出发的 Prim,写出各自选边与总权。)
解答 · 答案
Kruskal 依次选 、、;从 开始的 Prim 依次选 、、。两者总权均为 。Prim 的每一步都选当前到达割上最轻的边,即使新暴露的 是负边也无妨。
快速检查
(三角形三条边权为一、二、二。找出所有最小生成树,并解释圈规则对任一权为二的边能推出什么、不能推出什么。)
解答 · 答案
每棵最小生成树由权一的边和两条权二的边中的恰好一条组成,总权为三。每条权二的边都在某个最小生成树中缺席,也在另一个中出现。它们都不是严格重于圈上所有其他边,所以严格排除规则对二者都不适用。
快速检查
(三角形边权为 、、。由 与 构成的树是否最小?使用路径最大值判据;若失败,给出更便宜的树。)
解答 · 答案
从 到 的树路径经过权为 的 和权为 的 ,最大值为 。但森林外边 的权为 ,更小,因此判据失败。用 替换 ,得到总权 ,而原树为 。若把路径最大值初始化为零,会错误计算这条全负权路径。
快速检查
(一个图有两个非平凡连通分支,大小分别为三和二,另有一个孤立顶点。生成森林必须有多少条边?重新启动的 Prim 如何处理孤立顶点?)
解答 · 答案
三顶点树有两条边,二顶点树有一条,孤立顶点没有边,所以每片生成森林都有三条边。Prim 在孤立顶点重新开始时找不到跨割边,该单点分支立即完成。