一. 基本原理
图1
如图，图中包含了3个强连通分量（简称SCC，下同），从左到右分别设为, 则可以抽象为下面的图2，一个圈代表一个SCC
图2
注意到，如果把一个SCC当作一个结点，则这个图为有向无环图，即仅存在从到
的有向边，不存在从
到
的边，否则
同属一个强连通分量
所以我们只需要用DFS遍历，并使得图遍历的顺序为 , 就可以分别遍历
的所有结点
回到图1，设访问每个强联通分量时第一个访问的结点为这个强连通分量的leader，我们只要找到一个方法使得DFS访问的结点顺序为即可
则问题转变为如何找到一个访问leader的顺序，使得被指向的SCC先访问
按照DFS访问图1的时候有以下性质
- 一个SCC的leader总是最先访问，并且最后访问结束（遍历完所有后继结点）
- 如果有
则
的leader总是先访问结束
如果建立一个栈finishstack，如果结点访问结束，将其push入栈中，则在finishstack 中pop出来的结点顺序我们就称为后逆序，这个后逆序满足先访问结束的SCC的leader 顺序先于后访问结束的SCC的leader。
如果用leader结点代替相应的SCC，那么后逆序就是用DFS访问leader的顺序
并且，有一个引理
- 对图G求逆得到的
和原图的SCC相同
所以只要利用DFS访问,得到后逆序，然后再利用DFS按照后逆序访问图G，就可以使得G中被指向的SCC先访问，最终DFS访问得到的一个连通分量就是一个SCC
二. 方法概述
- 对原图取反，从任意一个顶点开始对反向图
- 按照
中顶点出栈顺序，对原图
进行DFS遍历，一次DFS遍历中访问的所有顶点都属于同一强连通分量。
三. 例子
找出图G中的强连通分量
G
第一步：求出
GT.png
第二步：求出后逆序
由A开始并按照字母序进行DFS遍历，并求出
访问顺序为 A G B C H D I F E
得到的为 C B D H F I G A E
第三步： 按照后逆序访问原图G
出栈顺序（后逆序）为 E A G I F H D B C
所以按照这个顺序对G进行DFS遍历， 访问的得到的结果是（一行为一次DFS遍历得到的连通图）
访问 E：{E}
访问 A：{A B G F I}
访问 H：{H}
访问 D：{D}
访问 C：{C}
所以得到五个连通图：{E}, {A B G F I}, {H}, {D}, {C}
四. 伪代码
- 获得finishstack后的原图遍历
图3.png
网友评论