在有向图中,能从一个顶点走到另一个顶点,并不意味着也能返回。依赖图中可能有联系紧密的若干组,组与组之间则只有单向联系。在讨论这些组的顺序之前,我们需要找出哪些顶点恰好能相互到达。
强连通分量将这两种结构区分开:在同一分量内部,每个顶点都能到达其他所有顶点;把各分量收缩后,分量之间不再有有向环。所得的有向无环图,使我们能够把看似循环的依赖系统理解为若干内部可能有环的组所构成的无环结构。
我们将推导通常称为 Kosaraju 算法的两遍 DFS 方法。第一遍搜索原图并记录完成顺序;第二遍按该顺序的逆序搜索所有边均反向的图。正确性依赖于这些具体选择,两次任意的可达性搜索并不足够。
相互可达定义分量
设 为有限有向图,顶点为 ,其中 可以为零。允许平行弧和自环。若存在从 到 的有向路径,记作 ;当 时,也包括长度为零的路径。
定义 10.2.1
(作为等价关系的强连通性)
定义
一个强连通分量(SCC)就是这个关系的一个等价类。等价地,它是一个极大的顶点集合,集合内任意两点相互可达。孤立顶点本身构成单点分量,不需要自环。
由于允许零长度路径,关系具有自反性;根据定义,它也具有对称性。若 且 ,拼接路径可得到 和 ,证明了传递性。因此各分量把全部顶点划分开,而不会互相重叠。
同一分量中两个顶点之间的路径可以完全取在该分量内部。事实上,若顶点 位于从 到 的一条路径上,且 ,则 。所以 ,每个中间顶点也都属于该分量。
转置图 对 中每条弧 包含反向弧 。反转一条路径也会反转相应的可达关系,因此相互可达关系和 SCC 划分在转置后都不变。
收缩分量消除所有分量间有向环
定义 10.2.2
(缩点图)
缩点图为每个 SCC 设置一个顶点。当 且原图存在从 中某顶点指向 中某顶点的边时,缩点图有弧 。分量内部的边被省略;同一对分量之间的平行弧只需保留一个代表。
定理 10.2.3
(缩点图无环)
有限有向图的缩点图是有向无环图。
证明
(分量的环会使它们合并)
假设若干不同的分量顶点形成一个有向环。利用每个分量内部的强连通性,我们可以沿这个环在任意两个分量之间双向到达。它们就应属于同一个等价类,与分量互不相同矛盾。因此缩点图是有向无环图(DAG)。
这并不说明原图无环,而是说明所有有向环都包含在各自的强连通分量内部。缩点图保留的是这些分量之间的单向关系。
第一遍 DFS 记录返回,而不是发现
在 上运行普通的有向 DFS 森林:每当还有未访问顶点,就从其中一个顶点开始新一轮 DFS。当一个顶点的出弧全部检查完毕,且递归发现的所有后代均已返回时,给该顶点一个完成时间。在这一时刻把顶点添加到列表即可;列表中越靠后表示完成得越晚。
对分量 ,令 为 中所有顶点的最大完成时间。不同分量中的各顶点不一定以彼此分离的连续块完成。我们需要的是关于分量最大值的结论:
定理 10.2.4
(完成时间最大值沿缩点图的弧递减)
设 为强连通分量。若缩点图有弧 ,则
证明透视
跨分量边决定最大完成时间的先后
考虑 与 的并集中第一个被发现的顶点属于哪个分量。
若它属于 ,从该顶点开始的 DFS 可以到达 的全部顶点,沿跨分量边到达 ,再到达 的全部顶点。为此只需使用分量内部的路径。这些尚未发现的顶点都会在 中第一个顶点完成之前被搜索。该顶点的完成时间在 中最大,且晚于 中每个顶点,故 。
若第一个顶点属于 ,则从 不可能有路径到达 ,即使允许经过其他分量也不行:否则结合 ,两分量就会相互可达。从这个 中首个顶点开始的 DFS 会搜索 的全部顶点,并在发现任何 中顶点之前完成。因此 中每个完成时间都早于 中某个完成时间,同样得到 。
这个引理比“DFS 恰好先访问了某一组”更强:它通过完成时间最大值给出了每条分量间依赖边的方向。
常见错误
(比较单个完成时间而不是分量最大值)
取弧 、、,邻点按递增顺序尝试。分量为 与 ,完成顺序为 。弧 离开第一个分量,但该分量中的顶点 1 比顶点 2 先完成。只有最大值的比较是正确的: 的最大完成名次是 , 的是 。
第二遍搜索无法离开所选分量
按完成顺序递减扫描顶点。每当下一个顶点仍未分配,就以它为起点在 中做可达性搜索,只经过尚未分配的顶点。把新到达的全部顶点归为一个分量。第二遍使用栈或队列均可,不需要再次计算完成顺序。
定理 10.2.5
(两遍算法的正确性)
对 运行 DFS 并记录完成顺序。然后按完成顺序递减扫描顶点;在每个未分配的顶点,只经过未分配顶点在 中搜索,并给到达的全部顶点一个新编号。这些搜索恰好分配出 的强连通分量,而且不同分量之间的每条弧 都满足 component[u] < component[v]。
证明透视
下一个分量在转置前是源,转置后是汇
归纳假设此前选出的每个分量都已被完整分配,因此剩余分量都完全未分配。按完成顺序递减扫描时遇到的第一个未分配顶点,属于剩余分量中 最大的分量 。
原图中不可能存在从另一个剩余分量 指向 的边:否则引理要求 。因此转置后,不存在从 指向另一个未分配分量的边。忽略已分配顶点,搜索便无法离开 。
另一方面,在 中,从所选顶点沿完全位于 内的路径,仍可到达 的每个顶点。因此搜索会到达其中所有顶点,恰好分配整个 ,完成归纳步骤。重复直到没有剩余顶点,就得到准确的 SCC 划分。
采用上述两遍搜索的方向时,产生的分量按原缩点图中从源到汇的拓扑顺序排列。如果依次赋予 ID 0、1、2 等,则每条跨分量原图边 都满足 component[u] < component[v]。这一顺序结论依赖于先搜索 、再搜索 ;不能悄悄交换两遍搜索,却保留相同的解释。
反例模式
只有一条弧时,发现顺序和不转置都会失败
只考虑边 。从 0 开始的 DFS 按 的顺序发现顶点,却按 的顺序完成。若反转发现顺序,第二遍会在转置图中从 1 开始。由于转置图有 ,搜索会错误地把两个顶点合并。
正确的逆完成顺序是 。但如果用它搜索原图而不是转置图,第一次从 0 开始的搜索同样会到达两个顶点,从而错误合并。实际分量为 和 ,因为在原图中 1 无法到达 0。
完整追踪:包含一个孤立分量
例题 10.2.6
(孤立顶点可以排在一条分量链之前)
考虑以下邻接表,邻居按表中所写顺序检查,外层根顶点按递增顺序考虑:
| 顶点 | 出边的邻居 |
|---|---|
| 0 | 1 |
| 1 | 2, 3 |
| 2 | 0, 3 |
| 3 | 4 |
| 4 | 3, 5 |
| 5 | 6 |
| 6 | 5 |
| 7 | 无 |
第一遍从 0 开始的 DFS 依次沿发现链经过 1、2、3、4、5、6。返回时依次添加 。随后顶点 7 最后被添加,所以完整的完成列表为 。
第二遍按 的顺序检查根顶点,依次分配分量 、、、。因此 ID 数组为 。从第一个非单点分量指向下一个分量的两条边合并为一条缩点图边。其边集为 ,分量 0 则仍是一个孤立的 DAG 顶点。
从 1 开始为完成事件编号,、、 和 的最大完成序号分别是 7、4、2 和 8。沿每条缩点图边,这些最大值都递减;互不相关的分量之间不一定有特定的相对顺序。
例题 10.2.7
(带尾巴的有向环)
取 及弧 、、、。从 0 出发的 DFS 依次走 ,然后在 2 处,通向 0 的弧遇到已被发现的顶点,通向 3 的弧发现 3。返回事件依次追加 。转置图的弧为 、、、。第二遍按 考虑根。从 0 出发先到达 2,再到达 1,把 分配为编号 0。下一个未分配的根是 3;它在转置图中唯一的弧指向已分配的顶点 2,搜索就此停止,把 分配为编号 1。编号数组为 ,跨分量的弧 满足 。缩点图有一条边 。
用显式栈帧保留 DFS 返回事件
只用于可达性搜索的普通栈未必重现递归 DFS 的完成事件。第一遍中,栈帧必须记住下一个要检查的出弧。当栈帧耗尽其邻接表时,才将顶点添加到完成列表并弹出。下降到新子顶点之前,先推进父栈帧中保存的索引,确保返回后从下一条弧继续。
顶点入栈时立即标记,而不是等到弹出时才标记。这能防止重复边、环和自环使同一个尚未标记的顶点多次入栈。第二遍只需判断可达性,所以栈中只存顶点,不需要保存返回索引。
下列输入是一个可按索引访问的邻接序列的序列,邻居标签为整数。非法邻居下标会被拒绝,包括 Python 原本会将其解释为从末尾索引的负下标。函数只读取输入,不修改它。返回值包括每个顶点的 ID 和每个分量的成员列表;成员顺序及无关联分量之间的相对 ID 都不是唯一标准形式。
def strongly_connected_components(graph):
n = len(graph)
transpose = [[] for _ in range(n)]
for vertex, neighbors in enumerate(graph):
for neighbor in neighbors:
if not 0 <= neighbor < n:
raise ValueError("neighbor outside the vertex range")
transpose[neighbor].append(vertex)
seen = [False] * n
finish = []
for root in range(n):
if seen[root]:
continue
seen[root] = True
stack = [(root, 0)]
while stack:
vertex, index = stack[-1]
if index == len(graph[vertex]):
stack.pop()
finish.append(vertex)
continue
neighbor = graph[vertex][index]
stack[-1] = (vertex, index + 1)
if not seen[neighbor]:
seen[neighbor] = True
stack.append((neighbor, 0))
component = [-1] * n
groups = []
for root in reversed(finish):
if component[root] != -1:
continue
identifier = len(groups)
component[root] = identifier
stack = [root]
members = []
while stack:
vertex = stack.pop()
members.append(vertex)
for neighbor in transpose[vertex]:
if component[neighbor] == -1:
component[neighbor] = identifier
stack.append(neighbor)
groups.append(members)
return component, groups
def condensation_edges(graph, component):
return sorted({
(component[u], component[v])
for u, neighbors in enumerate(graph)
for v in neighbors
if component[u] != component[v]
})
调用 condensation_edges 时,应传入对同一个图返回的 ID。DAG 有 len(groups) 个顶点,即使某些顶点没有关联边、因此不会出现在返回的边列表中也一样。集合负责去除重复的跨分量弧;排序便于检查返回的点对列表,但 SCC 的证明并不需要排序。
空图中两轮循环均为空,结果是 ([], [])。自环只会遇到已经标记的顶点;重复弧可能造成重复的边检查,但不会改变可达性。实现不依赖递归深度。
例题 10.2.8
(成员顺序不同于数学上的分量集合)
对于八顶点例子,代码返回的分组是 。其中顺序 来自对转置图的搜索;数学上的分量则是集合 。为了显示而排序成员列表不会改变划分。
如果再添加一条 ,或在 7 处添加自环,SCC 均不改变。对于这次遍历,排序后的缩点图边列表仍为 。即使孤立顶点 0 不出现在任何边对中,它仍然代表 。
复杂度与输出的含义
令 统计邻接表中列出的全部弧,包括重复弧。构造转置图需要 时间和存储。每一遍中,每个顶点最多入栈一次,每条列出的弧最多被检查一次;第一遍的显式栈帧会从上次位置继续,而不是重新扫描邻接表。因此,寻找分量需要 时间,以及包括转置图、栈和输出在内的 个额外存储单元。
可选的排序边辅助函数有单独的开销。若不同的跨分量点对共有 个,则使用哈希集合扫描邻接表并建立集合的期望时间为 ;随后排序需要 次比较,并需要 个额外存储单元。不要把排序后的辅助函数输出描述为无条件线性时间的一部分。这些是通常的图操作和存储单元界,不是对任意大标签的位复杂度界。
反例模式
分量 ID 较小并不能证明可达
在这个例子中,孤立分量 的 ID 为 0,分量 的 ID 为 1。但前者无法到达后者。拓扑顺序只保证已有的跨分量路径沿着 ID 增大的方向前进,并不保证每个 ID 较小的分量都能到达每个 ID 较大的分量。
同样,改变根顶点或邻居的顺序可能改变 ID,却不改变 SCC 划分。比较划分时应比较顶点是否属于同一分量,而不是期待每个分量都有一个通用的数字标签。
缩点图有助于后续处理依赖关系,但对于所有优化问题,SCC 并不会自动变成一个没有内部代价的顶点。如果后续问题涉及分量内部的路径长度、容量或访问约束,就需要另行论证这些内部细节。分量划分证明的是相互可达,并不会抹去原图的所有其他特征。
常见错误
(用缩点图计算分量内部的距离)
把有向环 缩成一个顶点,就丢掉了从 到 的最短路径有两条弧这个信息。缩点图只记录哪些分量能到达哪些分量;分量内部的路径长度、容量和访问限制需要另外论证。
练习与完整解答
快速检查
(1. 为什么孤立顶点没有自环也构成一个 SCC?说明相互可达为何具有传递性,从而两个 SCC 不可能重叠。)
解答 · 1. 零长度路径与路径拼接确立划分
零长度路径使每个顶点都能到达自身,包括孤立顶点。若 且 ,拼接 和 可得 。加上自反性和对称性,这就是一个等价关系,其等价类互不相交。因此若两个极大的相互可达集合有重叠,它们必定是同一个等价类。
快速检查
(2. 在八顶点例子中,{0,1,2}、{3,4} 和 {5,6} 的最大完成序号分别是多少?为什么 {7} 获得第一个分量 ID 不与排序引理矛盾?)
解答 · 2. 最大完成序号约束的是边,而非无关分量
若完成序号从 1 开始,三个最大值分别是 7、4 和 2。缩点图上的边符合 。顶点 7 在序号 8 完成,其单点分量首先被选中。它与其他分量没有连接边,因此引理不约束该分量与那条链的相对顺序。
快速检查
(3. 对单条弧 ,给出发现顺序、完成顺序和正确的第二遍根顶点顺序。分别解释逆发现顺序以及不转置会造成什么错误。)
解答 · 3. 完成顺序和反转边都不可少
发现顺序为 ,完成顺序为 ,在转置图上正确的第二遍根顶点顺序为 。在转置图上使用逆发现顺序会从 1 开始并到达 0,错误地把它们合并。在原图上使用正确根顶点顺序则从 0 到达 1,同样错误合并。只有在转置图上使用正确顺序,才会分别得到两个单点 SCC。
快速检查
(4. 添加重复弧或自环能改变 SCC 划分吗?既然这些弧不改变可达性,为什么实现仍要在入栈时标记?)
解答 · 4. 边的重数不会产生新的可达点对
重复弧只提供一个已有的步骤;从任意游走中删掉自环也不会改变起点和终点。二者都不会新增不同顶点之间的相互可达关系。入栈时标记使后续检查立即知道该顶点已被发现,防止重复弧或环导致重复入栈。实现相同的可达性关系时,仍须控制栈操作。
快速检查
(5. 八顶点缩点图中,虽然从分量 1 有两条原图弧进入顶点 3,为什么只包含 (1,2) 和 (2,3)?它有多少个 DAG 顶点?)
解答 · 5. 去重边时不要丢掉孤立顶点
和 都产生同一个分量点对 ,所以只需保留一个代表。边 产生 ;其他列出的边都在分量内部。DAG 有四个顶点,每个分量对应一个。孤立 ID 0 虽不出现在任何边对中,仍由顶点数保留下来。
快速检查
(6. 如果 component[u] 小于 component[v],u 一定能到达 v 吗?输出顺序实际保证哪个方向的蕴含关系?)
解答 · 6. 拓扑标签约束路径方向,但不保证路径存在
不一定:例子中顶点 7 的分量 ID 小于顶点 0 的分量 ID,但 7 无法到达 0。实际成立的是:如果 能到达 且两者分量不同,那么缩点图中的路径包含一条或多条跨分量边,每条边都使 ID 增大,因此 component[u] < component[v]。如果两顶点在同一分量,则它们相互可达且 ID 相等。