1. 背景与问题
设 是一个有限、连通、无向、无自环的简单图,且 。设 为权函数。权重可以为负,多条边也可以具有相同的权重。固定整数 ,满足 。
定义
(生成森林及其权)
生成森林是一个无圈的边集 ,视为定义在全部 个顶点上的子图。它的权为 。
问题。 在所有恰有 个连通分量的生成森林中,求出一个权最小者。
2. 边数刻画
引理
(森林的连通分量)
个顶点上的森林 恰有 个连通分量。
证明
(逐条边计算连通分量数)
从没有边的状态出发,此时共有 个连通分量。将 的边逐条加入。每条加入的边都属于无圈集合 ,因此在它被加入的时刻,其两个端点位于不同的连通分量中;否则它会构成一个圈。所以每加入一条边,连通分量数恰好减少一。
因此,森林恰有 个连通分量当且仅当它恰有 条边。可行森林总是存在的:由于 连通,它有一棵含 条边的生成树,删去其中任意 条边,便得到一个含 条边的森林。若一个森林在所有含 条边的森林中权最小,则称之为最优森林。
3. 算法与平局规则
平局规则。 将边任意但固定地编号为 。然后按二元组 的字典序对边排序。这是一个严格全序 。下文中所有“ 排在 之后”的说法都是相对于 而言的,并且它蕴含 。
算法 。
- 初始化一个并查集结构,每个顶点各自构成一个单元素集合。令 。
- 按 顺序扫描各边。对每条边 ,若 ,则立即停止。否则,若 ,则将 加入 并执行 ;若两次查找结果相同,则拒绝 。
- 返回 。
若 ,算法不接受任何边,直接返回 。
终止时边数足够。 假设扫描结束时 。则 有多于 个连通分量。由连通性,存在某条边 连接两个不同的最终连通分量。连通分量只会随时间合并,所以在扫描 时, 与 位于不同的连通分量中。此时算法本应接受 ,矛盾。因此 ;并且 是森林,因为每条被接受的边都连接两个不同的连通分量。
4. 正确性:交换不变量
定理
(提前停止 Kruskal 算法的正确性)
设 为有限、连通、无向的简单图, 为任意实数权函数(允许负权和平局),,并按 排列各边。则 返回一个恰有 个连通分量的生成森林,其权在所有这类森林中最小;也就是说,它返回一个最优森林。
证明
(建立交换不变量)
设 为按接受顺序排列的被接受边,并令 。
不变量 。 存在某个最优森林包含 。
显然成立。当 时,某个最优森林包含 ,而两者都有 条边,所以该最优森林等于算法的输出。剩下只需证明:对 , 蕴含 。
假设 是最优森林且 。令 。若 ,则已得证。否则,适用下面的关键引理。
引理
(最优森林中的边排在较后)
设 为最先被接受的 条边, 为满足 的森林, 为下一条被接受的边,且 。则每条 在 中都排在 之后。
证明
(较早被拒绝的边会形成圈)
假设 。在扫描 之前被接受的边恰好是 。由于 , 曾被拒绝。在那一时刻,它的两个端点已由某个 中的一条路径相连。这条路径与 一起在 中构成一个圈,这与无圈性矛盾。此外,由于 ,有 。
证明
(分两种情形的交换步骤)
现在考虑 。以下两种情形恰有一种发生。
情形 A: 连接 的两个不同连通分量。 此时 仍是森林,因为没有产生圈,并且它有 条边。我们需要删去一条边。计数:,故可任取 。从森林中删去一条边后仍是森林。于是 是含 条边的森林,且 。由后继边引理,,因此 。所以 是最优的。
注意,这种情形在通常的生成树证明中不会出现,因为那里的 是连通的。而这里 可能有 个连通分量,因此必须处理这一情形。
情形 B: 的两个端点位于 的同一个连通分量中。 此时 含有一个经过 的唯一圈 。集合 是森林,所以 。取 。则 ,故 。删去圈上的一条边不会破坏该连通分量内部的连通性。因此 是一个与 具有相同连通分量的森林,它有 条边,并且包含 。由后继边引理,。
两种情形下 均成立。
证明中没有用到 的符号。负权和平局情形都已完全涵盖。
证明透视
为什么交换论证适用于森林
保持一个包含当前已选边的最优森林。如果下一条接受边在该森林中形成环,就删除环上的另一条边;如果它连接最优森林的两个分量,加入后不会形成环,可以删除已选前缀之外的任意一条边。两种情况下,被删除边都比新接受边更晚被考虑:若它更早且被拒绝,就会在最优森林中形成环。因此被删除边的权重不小于新边,交换仍得到最优森林。
5. 运行示例
例题
(含负权与平局的提前停止 Kruskal)
取 ,顶点为 ,并取 。目标边数为 。
| 编号 | 边 | 权 |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 |
顺序为 。 与 之间的平局按编号 打破, 与 之间的平局按编号 打破。
| 步骤 | 边 | 查找结果相同? | 操作 | 连通分量 | |
|---|---|---|---|---|---|
| 1 | 否 | 接受 | 1 | ||
| 2 | 否 | 接受 | 2 | ||
| 3 | 否 | 接受 | 3 | ||
| 4 | 是 | 拒绝 | 3 | 不变 | |
| 5 | 否 | 接受 | 4 |
扫描在 时停止。输出为 ,其权为 。
例题
(相反的平局规则给出另一个最优森林)
平局规则影响返回哪一个森林,而不影响其权。 若对权为 3 的边采用相反的平局规则,算法将接受 而非 。这会得到 ,其连通分量为 和 ,权同样为 。两个森林都是最优的,固定的平局规则只是使输出具有确定性。
例题
( 的两个极端值)
沿用追踪中的图。当 时,目标为 条边,所以扫描在接受任何边之前就停止,返回权为 的 :六个单点分量。当 时,目标为 条边,扫描会越过追踪中的停止点。、、 被接受, 被拒绝, 如前被接受。由于 ,扫描继续:(权 ,编号 )把 接到大分量上,于是 ,扫描停止。输出 是权为 的最小生成树。最后被接受的边权为正;恰有一个连通分量时,算法必须接受它。
常见错误
(在 k 条边而不是 n-k 条边时停止)
扫描在接受 条边时停止,而不是 条。在 、 的追踪中,若接受两条边就停止,会返回 ,它有四个连通分量。只有 时两个数目才相同。
常见错误
(因为权为正而拒绝一条边)
由于问题要求恰有 个连通分量,算法必须不断接受边直到有 条,即使下一条可接受的边权为正。在追踪中, 的权为 但被接受;若把它舍弃,就只剩三条边、三个连通分量的森林,那是另一个问题。
6. 恰好、至多与至少 个连通分量
每个 执行相同的扫描,区别仅在于何时停止。因此 的输出是在 的输出上添加下一条被接受的边。记 为恰有 个连通分量时的最优权。在本例中,完整运行依次接受 ,由此得到:
| 6 | 5 | 4 | 3 | 2 | 1 | |
|---|---|---|---|---|---|---|
概念视角结构
最优森林就是去掉最重边的生成树
由于 是 的延伸,具有 个连通分量的最优森林,就是把最小生成树中最后接受的 条边删去所得的森林。在这里,树 删去 便得到两个连通分量的最优森林,权重为 ;再删去 ,便得到三个连通分量的最优森林 ,权重为 。因此停止规则只是对同一棵树的一次截断,而序列 记录的是这棵树各个前段的权重。
该序列先下降后上升。存在负权时, 与最优值之间没有单调关系。每多加一条边就加上该边自身的权,而这个权可能为负,也可能为正。
- 至多 个连通分量意味着至少 条边。最优值为 。当 时,它等于 。
- 至少 个连通分量意味着至多 条边。最优值为 。当 时,它等于 ,在 时由 取得。
被接受边的权按接受顺序单调不减,所以这些最小值很容易定位。对于“至多 ”,先运行 ,然后只要下一条被接受的边权为负就继续接受。对于“至少 ”,在达到 条边时停止,或者在第一条权为正的被接受边之前停止,以先发生者为准。权为零的边加或不加均可,不改变总权。
反例模式
恰有 k 个连通分量不等于至多 k 个连通分量
断言: 返回的森林,在所有至多有 个连通分量的森林中也是权最小的。取追踪中的图与 ,则 , 返回权为 的 。集合 同样是森林,它有 个连通分量,权为 。所以 对于“至多五个连通分量”并不最优。定理讲的是恰好的个数,因为交换论证把边数固定为 。修正办法就是上文对“至多 个”的规则:运行 之后,只要下一条被接受边的权为负就继续接受。这里会接受 (权 ),然后停止,因为下一条被接受边的权 不是负数,得到 。
7. 复杂度与注意事项
- 初始化: 次建集操作耗时 。
- 排序: 按 对 条边做比较排序的代价为 。当 时,由简单性有 ,所以这也是 。提前停止并不会降低最坏情况下的排序代价,因为排序在扫描开始之前就已完成。对于 ,可以跳过排序,直接返回 。
- 并查集: 采用按秩合并与路径压缩时,至多 次查找和 次合并共耗时 。若不采用任何平衡规则,单次查找在最坏情况下可能耗时 。因此上述界依赖于具体实现。
- 总计: :初始化贡献 ;对于 的连通图,排序项吸收了并查集扫描的代价。单顶点图没有边,耗时 。非比较排序(例如对有界整数权使用基数排序)可以做得更好,但不属于比较模型的范围。
8. 即时检查
快速检查
(在 10 个顶点上的一个森林有 7 条边。它有多少个连通分量?)
解答 · 答案
由连通分量数引理,它有 个连通分量。
快速检查
(对追踪中的图与 , 返回什么?它的权是多少?)
解答 · 答案
目标为 条边。扫描接受 、 和 之后停止,返回 ,权为 ,等于表中的 。
快速检查
(所有边的权都是 ,且 。 返回哪个森林?)
解答 · 答案
目标为一条边。所有权都相同,所以 就是编号的顺序,扫描接受编号为 的边。返回 ,权为 ;第一条被扫描的边必定被接受,因为单独一条边不会形成圈。
快速检查
(每个权都增加 。 的输出会改变吗?)
解答 · 答案
不会。顺序 不变,所以扫描接受同样的边。每个候选森林都恰有 条边,所以所有权都平移同一个量 ,最小者不变。对“至多 个”的问题这就不成立,因为边数是变化的。