假设连线有成本,我们要连通原网络中每一对本来就能互相到达的顶点。先选便宜的边似乎合理,但如果不检查结构,可能把一条边浪费在环上。Kruskal 算法结合两个想法:按成本非递减的顺序考虑边,再用并查集判断一条边是否连接两个不同的分量。
数据结构回答的是结构问题,而不是最优性问题。我们会分别证明所选边构成所需的森林,以及它们的总成本最小。这样也更容易正确处理不连通的图、相同权重的边和负成本。
为每种输入图规定输出
设 为有限无向加权多重图。平行边是不同的输入边,允许自环,每条边的整数权重可以为负。顶点编号为 ,允许 。每条边都有输入索引,因此权重相同的平行边仍可区分。
定义 14.1.1
(生成森林与最小成本)
生成森林包含所有顶点、没有环,并且与 有相同的连通分量。因此每个非平凡的原图分量都由一棵树生成;孤立顶点是一棵没有边的单顶点树。自环不能属于森林;在本节的多重图约定下,同时选两条平行边会形成长度为二的环。
森林的成本是所选边权重之和。最小生成森林是在所有生成森林中成本最小的一个。若 连通且非空,它就是最小生成树。当 时,空森林的成本为零。
我们不要求输入连通,也不声称最优解唯一。固定权重相同的边的顺序,可以使一次实现的结果可重现,但并不意味着所有最小森林都相同。
先排序,只接受连接不同分量的边
起初没有选边,每个顶点各自构成一个并查集集合。按 (权重, 输入索引) 对边排序。依序考虑每条边 :比较 find(u) 与 find(v)。根不同就选 并合并两个集合;根相同则跳过。检查完全部边后,返回所选的边及其成本。
自环的两端是同一个顶点,所以即使权重为负也一定跳过。较后出现的平行边并不会因为“平行”就自动跳过,而是在被考虑时,若两端已被所选边连通才跳过。
常见错误
(不做环检查就取最便宜的边)
取顶点 0、1、2、3,边 0–1、1–2、0–2 的权重为 1,边 2–3 的权重为 5。最便宜的三条边恰好是那个三角形:它含有环,并使顶点 3 与其余部分断开,成本为 3。最小生成树必须使用 2–3 和三角形中的两条边,成本为 。只数边的条数而不检验分量,会得出错误的答案。
命题 14.1.2
(Kruskal 选出生成森林)
每检查完一条边之后,所选的边构成一个森林,它的连通分量恰好就是并查集中的各个集合。扫描结束时,所选的边是 的一个生成森林。
证明
(所选边与并查集有相同的分量)
起初所选图没有边,并查集中都是单点集合,所以两种分量一致。若一条边的端点在不同集合,由归纳假设,它们也在所选图的不同分量中。加入这条边会合并两个分量而不产生环;union 恰好合并相应的集合。若两端已在同一集合,所选边已经提供了一条连接它们的路径,再加这条边就会形成环。跳过它不改变任何一种划分。
因此所选边始终是森林,而每一步中 find 恰好代表它的连通分量。这证明了环检查是正确的,但还没有证明权重最小。
扫描结束后,每条原图边的两端都在同一个所选分量中:被选中的边合并了两端,被跳过的边在当时两端已经连通,此后也不会被拆开。每条原图路径都由这样的边组成,所以路径两端在同一个所选分量中。反过来,所选边都是原图的边,不可能连接原图的不同分量。两种分量划分因此一致,结果是一个生成森林。
概念视角结构
把森林看成边次序上的规则
Kruskal 的选择可以不借助过程来陈述:按 这一对把边排好;边 被选中,当且仅当只用排在它前面的边找不到连接 与 的路径。自环永远不会被选中,因为它的两端本来就相连。由此可知,输出只取决于边的次序,而不取决于权的数值本身:把每个权 换成严格递增的 ,选出的边完全相同。
为什么贪心选择能属于某个最优解
定理 14.1.3
(Kruskal 的森林成本最小)
对每个有限无向加权多重图,包括带有负权、平行边、自环以及多个连通分量的图,Kruskal 算法返回的森林都是最小生成森林。
证明
(跨割交换,同时允许相同权重及负权)
用归纳法证明:存在一个最小生成森林 ,包含目前已选的全部边。起初成立,因为有限图只有有限多个候选森林,所以最优解存在。
假设算法接下来选 。令 为选 之前所选森林中包含 的分量; 在 之外。考虑任意跨越这个割的原图边 。若 ,扫描早已考虑过 。它的两端现在仍在不同的所选分量中,因为一端在 、另一端在外;分量只会合并,所以当时两端也不同,算法就会选中它,与现在的割矛盾。因此每条跨割边的权重至少为 。
选一个包含所有先前已选边的最优森林 。若它已含有 ,归纳步骤即成立。否则 属于同一个原图分量,所以 在该分量中的树里有唯一的 – 路径;这条路径必在某条边 处跨越这个割。先前已选的边都没有跨越这个割,因为 是所选森林的一个分量,所以删去 不会丢失先前已选的边。在 中加入 产生一个环,再删去 得到另一个生成森林;由 ,成本不会增加。
由于 已经成本最小,新森林也是最优的,并且包含先前已选的边及 。归纳成立。最后,所选森林本身已经生成原图的各个分量,而包含它的最优森林在每个分量中也是树,不能再多含一条边而不产生环;两者因此相同。所以返回的森林成本最小。
证明透视
排序在哪里发挥作用
真正起作用的一步,是对每条跨割的边 都有 。它依赖两件事:扫描按权重顺序进行,并且分量只会合并,所以较轻的跨割边早已被接受。交换论证本身只用到 是所选森林的一个分量,因此被移除的边 以前从未被选过。权重的正负从不出现。如果没有排序,第一件事就不成立,如下面的例子所示。
证明只比较权重,没有假设权重为正。权重相同的边可以互相交换而保持成本,因此可能有多个不同的最小森林;输入索引只决定本实现在权重相同时选哪一个。
反例模式
只做环检查而不排序并不够
取顶点 0、1、2,边按输入顺序为:0–1 权重 5、1–2 权重 1、0–2 权重 1。按这个顺序只做环检查:接受 0–1,再接受 1–2,并因为 0 与 2 已经连通而跳过 0–2。成本为 。仅由两条权重为 1 的边就已构成成本为 2 的生成树,所以结果并非最小。环检查只保证无环;按 (权重, 索引) 排序,才使每条跨割边都至少与被接受的边一样重。
权重相同、自环、平行边和孤立顶点
例题 14.1.4
(不连通的输入仍有明确的最优森林)
使用顶点 及下表中带索引的边,其中顶点 4 是孤立点。
| 索引 | 边 | 权重 | 结果 |
|---|---|---|---|
| 0 | 0–1 | 1 | 选取 |
| 1 | 0–2 | 1 | 选取 |
| 2 | 1–2 | 1 | 跳过:成环 |
| 3 | 1–3 | 3 | 跳过:已连通 |
| 4 | 2–3 | 2 | 选取 |
| 5 | 3–3 | -5 | 跳过:自环 |
| 6 | 0–1 | 4 | 跳过:平行边会成环 |
按权重及索引处理的顺序是 。所选索引为 ,成本是 。最后的分量是 与 ,与原图一致。若对权重相同的边采用另一种顺序,三条权重为 1 的边中可以选不同的两条,成本仍为 4。
例题 14.1.5
(平行边:较轻的一条胜出)
取顶点 0、1、2 及带索引的边:0 号是 0–1 权重 3,1 号是 0–1 权重 2,2 号是 1–2 权重 4,3 号是 0–2 权重 4。处理顺序是索引 。选中 1 号边。0 号边是平行的副本,两端已经连通,所以虽然在输入中排在前面,仍被跳过。2 号边把顶点 2 连到 ,被选中;3 号边会形成环,被跳过。所选索引为 ,成本 。2 号与 3 号边的并列由索引决定;若改选 3 号边,会得到另一个成本相同的最小森林。
常见错误
(按输入顺序删去平行边)
只保留若干平行边中的第一条并不安全。上例中 0–1 的第一条副本权重为 3,若只用各组的第一条副本建图,最小森林的成本是 ,而用较轻的副本则是 6。平行边必须全部参与排序。
实现并查集
下面的实现使用按大小合并,不做路径压缩。每个根保存其集合的大小;非根节点的大小字段不必保持最新。find 沿父指针走到根。合并不同的根时,较小的树的根成为较大的树的根的子节点;大小相等时偏向传给 union 的第一个根。
class DisjointSets:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, vertex):
while self.parent[vertex] != vertex:
vertex = self.parent[vertex]
return vertex
def union(self, left, right):
a, b = self.find(left), self.find(right)
if a == b:
return False
if self.size[a] < self.size[b]:
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
return True
def minimum_spanning_forest(n, edges):
if n < 0:
raise ValueError("vertex count must be nonnegative")
indexed = []
for index, (u, v, weight) in enumerate(edges):
if not 0 <= u < n or not 0 <= v < n:
raise ValueError("edge endpoint outside the vertex range")
indexed.append((weight, index, u, v))
indexed.sort()
sets = DisjointSets(n)
selected = []
cost = 0
for weight, index, u, v in indexed:
if sets.union(u, v):
selected.append(index)
cost += weight
return cost, selected
输入是非负整数 n 和由 (u, v, weight) 三元组构成的可迭代对象,端点和权重为整数。代码检查端点的范围,但假设类型和三元组的结构符合约定。它另外建立带索引的列表,不修改调用者的边集合。返回的索引对应原输入边,顺序就是贪心处理的顺序。n=0 时边列表必须为空,返回 (0, [])。
命题 14.1.6
(按大小合并使父链保持较短)
使用按大小合并而不做路径压缩时,在 个顶点上,每次 find 至多沿 条父链接前进,所以 find 与 union 各需 步。
证明
(按大小合并为什么使父链不长)
每当一个根变成子节点,它的整棵树不大于新的伙伴。于是深度增加的每个顶点,其所在集合的大小至少变成原来的两倍。顶点从单点集合开始,集合最多有 个顶点;当 时,它的深度最多增加 次。
因此 find 和一次 union 使用 个父链步骤。这个简单的界不依赖路径压缩的定理。大小指合并时整个集合的大小;过时的非根大小不会用来选择新的父节点。
对 条输入边,建立索引与初始化需要 ;比较排序需要 。 次合并尝试共需 ,因此总时间为
额外空间为 ,包括带索引的列表及输出。这是操作次数的界;任意大小整数的比较与加法另有按位计算的成本。配合路径压缩的更精细的并查集可以有更精确的摊还界,但并不是这段代码所实现的方法。
例题 14.1.7
(四个顶点上的按大小合并,及最小的输入)
在四个顶点的图上依次处理边 0–1、2–3、0–2。union(0,1) 连接大小相等的根 0 与 1,所以根 1 成为 0 的子节点,size[0] 变为 2。union(2,3) 使 3 成为 2 的子节点。union(0,2) 比较相等的大小 2 与 2,所以根 2 成为 0 的子节点,size[0] 变为 4。最深的顶点是 3,深度为 2,与 吻合。
在最小的输入上, 且没有边时,函数返回 (0, []); 且只有一条权重为 的自环时也是如此,因为 union(0,0) 找到相同的根而返回 false。
练习与解答
快速检查
(1. 为什么负权自环会被跳过,即使它可以减少所选边的权重和?)
解答 · 解答 1
生成森林必须无环,而自环本身就是环。它的两端是同一个顶点,union 返回 false,Kruskal 因此跳过它。目标是在合法的生成森林中最小化成本,而不是在任意边子集中取最小的总和。
快速检查
(2. 五个顶点的例子中,所选边的索引和最后的分量是什么?孤立顶点会使结果无效吗?)
解答 · 解答 2
所选索引是 [0, 1, 4],总成本为 4;分量为 和 。孤立顶点作为单顶点树保留下来,结果是最小生成森林,而不是整个不连通图的一棵生成树。
快速检查
(3. 三个顶点的 0–1、1–2、0–2 权重都是 1。最小生成树唯一吗?)
解答 · 解答 3
不唯一。任选两条边都能连通三个顶点且没有环,总成本为 2。确定的输入索引顺序会选出其中一个最优解,但不会消除其他有效的最优树。
快速检查
(4. 为什么被跳过的边不必重新考虑,仍能保证最后生成原图的各个分量?)
解答 · 解答 4
边被跳过时,两端已经在同一个所选分量中。之后的合并只会把分量并在一起,不会拆开,所以两端持续连通。最后每条原图边、因而每条原图路径的两端都在同一个所选分量中;所选边又不能连接原图的不同分量。
贪心证明与数据结构证明各有分工:交换论证证明权重最小;并查集的不变量使环的判断高效。只检查其中一个,不能代替另一个。