动机
在有向图中,从一个顶点能到达另一个顶点,并不意味着反方向也能到达。强连通分量把彼此可达的顶点归为一组,将这些组收缩之后便得到一个无环结构。两遍扫描算法利用深度优先搜索的完成时间来选取分量的处理顺序,使得在转置图中,每个分量与剩余的搜索相互隔离。
证明依赖的是整个分量及其最大完成时间,而不是“一个分量的每个顶点都晚于另一个分量的每个顶点完成”。清楚地区分这一点,可以避免顺序论证中一个常见的错误。
定义
定义 3.5.1
(强连通分量与缩点图)
设 为有限有向图。若顶点 之间各自都能沿有向路径到达对方,则称 强连通;长度为零的路径也允许。强连通分量(SCC)是这一关系的一个等价类。缩点图(condensation graph)为每个 SCC 设一个顶点;当 且原图中存在一条从 中某顶点指向 中某顶点的边时,缩点图中有边 。
定义 3.5.2
(转置图与分量的完成时间)
转置图 将每条边反向。对 执行一次完整的深度优先搜索(DFS):只要还有未访问的顶点,就从任一未访问顶点重新开始,直到所有顶点都被访问,并记录每个顶点的完成时间。对 SCC ,令 为 中各顶点完成时间的最大值。
两遍扫描过程按完成时间从大到小处理各顶点;每当遇到一个尚未分配的顶点,就在 中从它出发做一次 DFS,并忽略已分配的顶点。该次搜索所找到的顶点构成一个输出组。
定理
定理 3.5.3
(缩点图与完成时间)
缩点图是无环的。若缩点图中有边 ,则对 的完整 DFS 满足 。
定理 3.5.4
(两遍扫描 SCC 算法)
两遍扫描过程输出的各组恰好就是 的各个 SCC。使用邻接表时,两遍搜索以及转置图的构造所需的时间和空间均为 。
证明思路或证明
第一个证明涵盖第一个定理的两项结论。
证明
(缩点图无环,以及沿边的完成时间)
互相可达关系按定义满足自反性和对称性,并借助路径的拼接满足传递性,因此其等价类构成顶点集的一个划分。若不同分量在缩点图中构成一个有向环,则沿该环的路径再加上各分量内部的路径,会使环上所有顶点彼此可达,它们便属于同一个分量,这与分量互不相同矛盾。因此缩点图是一个有向无环图(DAG)。
对于边 ,比较 中顶点最先被发现的情形。设最先被发现的顶点 在 中。此刻 中其余顶点都仍未被发现。在 内有一条路径从 通向该边的起点,该边进入 ,再沿 内的路径可到达 的每个顶点;这些顶点全都仍未被发现。因此 DFS 在从 返回之前会探索它们全部, 在 的每个顶点之后完成,故 。反之,设最先被发现的顶点 在 中。此时不存在从 到 的路径:这样的路径与 合在一起会使两个分量合并。从 出发的 DFS 会到达 的每个顶点,并在发现任何 的顶点之前使它们全部完成。 的每个顶点都在 的每个顶点之后被发现,因而也在其后完成,于是同样有 。
第二个证明涵盖两遍扫描算法,是对第二遍各次搜索的归纳。
证明
(第二遍的每次搜索恰好输出一个分量)
不变量:在每次第二遍搜索开始前,已分配的顶点构成若干完整 SCC 的并集,并且每个已输出的组都是一个 SCC。开始时没有任何已分配顶点。
设 为完成时间最大的未分配顶点, 为它所属的 SCC。 的所有顶点都未分配,而完成时间互不相同,所以 大于其余每个剩余分量 的 。若某个剩余分量 在缩点图中有边 ,由第一个定理会得 ,这不可能。所以 是剩余分量中的源点。于是在 中,每条离开 的边都终止于 内或某个已分配顶点。由于搜索忽略已分配顶点,它不会离开 。反过来, 内任意两个顶点在 中借助留在 内的路径彼此可达(把 内的路径反向,仍是 内的路径),而 全部未分配,所以从 出发的搜索能到达 的每个顶点。输出的组恰好是 ,不变量得以保持。每个顶点最终都会被分配,所以各组恰好就是各 SCC。
使用邻接表时,构造转置图以及每次完整的 DFS 对每个顶点和每条边只扫描常数次。把完成顺序反转可借助栈或列表完成,所以总时间和额外空间均为 。
证明透视
第二遍可能从哪里逃出
第二个证明只使用第一个定理一次:用来排除某个剩余分量有边指向所选分量 。这也说明了为什么只比较最大值就足够:完成时间最大的顶点 本身就是它所属分量的最大值,不需要任何关于其他个别顶点的结论。
不显而易见的一步是把边反向。在 中, 完全可以有边通向其他剩余分量,搜索会沿这些边走出去;完成时间定理只保证没有剩余分量有边指向 。把所有边反向,恰好把这个保证变成“没有边离开 ”。有两个假设承担了重量。搜索必须跳过已分配顶点,因为由较早分配的分量指向 的原有边,在 中会变成离开 的边。起点必须取自第一遍的完成顺序,因为只有这个顺序才由定理与缩点图的边联系起来。论证以归纳法完结:取走一个完整分量之后,剩余的分量仍按 排序,所以下一步仍可作同样的选择。
例题详解
例题 3.5.5
(链状排列的三个分量及其完成时间)
设边为 、、、、 和 ,并按字母顺序扫描邻接表。第一遍 DFS 从 开始:先发现 ,再发现 和 (边 与 都指向已被发现的顶点),最后发现 。 的发现时间依次为 。然后 在时间 完成, 在 , 在 , 在 , 在 。于是 、、:沿链 ,最大值递减,与定理的预测一致。
转置图的边为 、、、、 和 。完成时间递减的顺序是 。从 出发的搜索只到达 :得到组 ,随后跳过 。从 出发的搜索看到指向 的边,但 已分配而被忽略,并到达 :得到组 ,随后跳过 。从 出发的搜索忽略指向已分配顶点 的边:得到组 。这三个组就是各个 SCC。
例题 3.5.6
(一条单向边)
对于两个顶点 且没有返回路径的情形,SCC 为 和 。仅有从 到 的可达性并不能使它们成为同一个分量。缩点图只有一条边 。
例题 3.5.7
(一个环就是一个分量)
在有向环 中,每个顶点都能到达另外两个顶点。这三个顶点同属一个 SCC,尽管任意两个顶点之间并没有双向的直接边。
常见错误
反例模式
一条边并不意味着互相可达
图 中存在从 到 的路径,但没有返回的路径。把有向可达性当作无向关系,会把两个不同的分量错误地合并。
常见错误
(拿个别顶点的完成时间代替最大值作比较)
当缩点图中有边 时,定理比较的是最大完成时间 与 。它并没有声称 中的每个顶点都晚于 中的每个顶点完成。在下面的例子中,、 且有边 ,完成顺序可以是 :虽然 , 中的 却早于 中的 完成。
常见错误
(第二遍漏掉已分配顶点的记录)
第二遍搜索必须忽略先前搜索已经分配的顶点,并且必须按第一遍所得的完成时间递减顺序选取起点。若在第二遍中重新计算完成顺序,或让搜索重新进入已分配的顶点,就无法保证每次搜索只停留在一个分量之内。
为什么完成时间的最大值就足够
深度优先搜索在第一次访问某个顶点时赋予其发现时间,在检查完它所有的出边并从递归后代返回之后赋予其完成时间。在通常的顺序实现中,完成时间互不相同。一棵 DFS 树可以包含来自多个 SCC 的顶点;定理并不要求每个分量在整个 DFS 森林中构成一个连续的子树。
考虑从分量 指向另一个不同分量 的一条边。若这两个分量中最先被发现的是 的某个顶点,则此刻除该起始顶点之外, 和 的所有顶点都尚未被发现。 内的路径、通向 的边以及 内的路径表明:最先被发现的那个 顶点可以经由这两个分量中尚未访问的顶点到达 的每个顶点。DFS 在从该 顶点返回之前,会使所有这些后代顶点完成。因此它的完成时间大于 中每个顶点的完成时间,从而推出最大值之间的不等式。
若最先被发现的是 的某个顶点,则边 的存在排除了从 回到 的任何路径。从该 顶点出发的 DFS 会到达 的全部顶点,但在完成之前无法发现 的任何顶点。因此每个 的顶点都在第一个 顶点被发现之前完成。这两种情形在不预先假设 DFS 先访问哪个分量的前提下,建立了同一个比较结论。
例题 3.5.8
(完成顺序不一定把同一分量的顶点排在一起)
设 ,两个方向的边都有;设 ,并添加边 。从 开始 DFS,并先探索 再探索 。完成顺序可以是 。在此顺序中,分量 与 交错出现,但 是 的完成时间,它大于 。定理涉及的是最大值,而不是由各个时间构成的连续区段。
为什么第二遍能提取出整个分量
将所有边反向会使每条路径反向,所以在 中彼此可达的顶点在 中仍然彼此可达。SCC 的划分保持不变,而缩点图的每条边都改变方向。在每次第二遍搜索开始时,假定先前输出的各组都是完整的分量;这就是归纳假设。
完成时间最大的未分配顶点所属分量的最大值,在剩余分量中最大。若原缩点图中另有一个剩余分量有边指向它,则由完成时间定理,该前驱分量会有更大的最大值,这是不可能的。因此所选分量是剩余分量中的源点。在转置图中,它没有指向其他剩余分量的边。拒绝进入已分配顶点的搜索无法离开所选分量,而转置图中的互相可达性又保证搜索能到达该分量的每个顶点。于是得到的组恰好是一个 SCC,归纳假设得以保持。
在转置图中,从某个未分配分量指向已分配分量的边不会使上述推理失效,因为搜索明确地忽略已分配的顶点。若实现中开始新的 DFS 时不记录先前的分配情况,就可能反复遍历已经输出的顶点,也就不能直接体现所述的证明。所用的顺序是由第一次图搜索得到的完成时间递减顺序,而不是在第二遍中重新计算的完成顺序。
反例模式
在第二遍搜索原图
假设第二遍不在 而在 本身按完成时间递减顺序搜索。取只有一条边 的图 。每次完整的 DFS 都使 先于 完成(从 开始,先完成 再完成 ;从 开始,先完成 ,其后才发现 )。递减顺序因此以 开始,而在 中从 出发的搜索会到达 ,输出变成单一组 。可是没有从 回到 的路径,所以 SCC 是 和 。在只有边 的 中,从 出发只找到 ,下一次搜索找到 。补救的办法是使用转置图:顺序中的第一个顶点属于源点分量,只有把边反向之后,它才没有指向其他剩余分量的边。
一个可实现的执行过程
第一遍 DFS 可以在每个顶点完成时把它追加到一个列表中。倒着读这个列表就得到完成时间递减的顺序,不需要数值形式的时间戳。构造 的方法是:对每条原有边 添加边 。将所有顶点初始化为未分配。扫描反转后的完成列表;若某顶点已分配,则跳过。否则在 中运行一次图搜索,用当前的分量编号标记搜索发现的每个顶点,并在搜索结束时输出该组。
第二遍可以使用 DFS 或其他穷尽式图搜索:证明所需要的是它恰好访问转置图中从起点可达的未分配顶点。第一遍则必须使用 DFS 的完成时间。邻接表使每条有向边在每次遍历中都能以常数时间取得。转置图的构造、两次图搜索以及最后的扫描合计检查 个条目。稠密的邻接矩阵有不同的扫描代价,所以图的表示方式是所述复杂度的一部分。
输出的各组可用来构造缩点图:扫描原图的各条边,只要两个端点的编号不同就添加一条边。同样两个分量之间的平行边可以保留,也可以去重,视所需的表示而定;两种选择的可达性结构相同。SCC 算法并不会自动输出某种特定的拓扑排序,除非事先规定了它的约定和顺序。
检验一个给定的划分
要验证一个声称的分量,可以选一个代表顶点,只使用该组内的顶点,检验从它到组内每个顶点的可达性,以及从组内每个顶点回到它的可达性。将边反向后,第二组检验就变成从该代表顶点出发的另一次搜索。如果每个组在内部都是强连通的,并且把各组收缩之后得到的图是无环的,那么这些组就是 SCC:更大的互相可达类会在不同的收缩组之间产生环。
这一证明将内部连通性与极大性分离开来。仅仅证明每个给定的组是强连通的并不充分:把一个有向环拆成若干单点组满足这一局部条件,却不满足极大性。反过来,若某个组本身含有彼此不可达的顶点,那么仅有各任意组构成的无环图也不充分。两部分缺一不可。
没有边的图中,每个顶点(包括孤立顶点)各自构成一个 SCC。空图没有分量。自环不会使其顶点与其他分量合并。这些情形都可由同样的定义推出,两遍扫描过程不需要为此设置特殊例外。
总结
互相可达性把有向图划分为各个 SCC,其缩点图是 DAG。沿缩点图的边,DFS 完成时间的最大值递减。在转置图中按完成顺序递减处理各顶点,每次可提取出一个剩余的源点分量。
练习
快速检查
(顶点为 、只有一条边 的图,其 SCC 是什么?)
想一想 能否到达 。
解答 · 答案
它们是 和 ,因为 不能到达 。
快速检查
(为什么缩点图不能包含有向环?)
把沿环的路径与各分量内部的路径拼接起来。
解答 · 答案
一个环会使环上任意两个分量之间在两个方向上都有路径,于是环上所有顶点彼此可达,这些分量就不会互不相同。
快速检查
(若缩点图中有边 ,哪个分量的最大完成时间较大?)
回想完成时间定理。
解答 · 答案
是边的起点分量 :。
快速检查
(为什么转置会保持 SCC 的划分?)
把每条边反向后,一条路径会变成什么?
解答 · 答案
把每条边反向会使每条路径反向。互相可达性在转置图中成立,当且仅当它在原图中成立。
练习 3.5.9
(对顶点为 、边为 、、、、、 的图执行两遍扫描算法,邻接表按递增顺序扫描,并列出输出的各组。)
核心
提示(1)
只需记录顶点完成的先后顺序,不必计算数值形式的时间。
解答(4)
- 1
从顶点 1 开始第一遍 DFS
搜索依次发现 ;边 指向已被发现的顶点,于是继续到 和 ,边 同样被跳过。顶点完成的顺序是 。
- 2
构造转置图并反转完成顺序
转置图的边为 、、、、、。完成时间递减的顺序是 。
- 3
在转置图中搜索并跳过已分配顶点
关键一步
从 出发,搜索到达 再到达 ,得到组 ;随后跳过 和 。从 出发,指向 的边因 已分配而被忽略,搜索到达 :得到组 。
依据: 在转置图中从完成时间最大的顶点出发的搜索无法离开它所属的分量。
- 4
写出各组并检验
输出为 和 。它们就是各个 SCC: 与 都是环,两者之间只有边 。这与定理一致:顶点 最后完成(时间 ),而 中的最大值较小(时间 )。