求解图的强连通分量的方法（一）：Kosaraju算法

一. 基本原理

图1

如图，图中包含了3个强连通分量（简称SCC，下同），从左到右分别设为 $S_1, S_2, S_3$ , 则可以抽象为下面的图2，一个圈代表一个SCC

图2

注意到，如果把一个SCC当作一个结点，则这个图为有向无环图，即仅存在从 $S_1$ 到 $S_3$ 的有向边，不存在从 $S_3$ 到 $S_1$ 的边，否则 $S_1和S_3$ 同属一个强连通分量

所以我们只需要用DFS遍历，并使得图遍历的顺序为 $S_2 \rightarrow S_3 \rightarrow S_1$ , 就可以分别遍历 $S_1,S_2,S_3$ 的所有结点

回到图1，设访问每个强联通分量时第一个访问的结点为这个强连通分量的leader，我们只要找到一个方法使得DFS访问的结点顺序为 $leader(S_1) \to leader(S_2) \to leader(S_3)$ 即可

则问题转变为如何找到一个访问leader的顺序，使得被指向的SCC先访问
按照DFS访问图1的时候有以下性质

如果建立一个栈finishstack，如果结点访问结束，将其push入栈中，则在finishstack 中pop出来的结点顺序我们就称为后逆序，这个后逆序满足先访问结束的SCC的leader 顺序先于后访问结束的SCC的leader。

如果用leader结点代替相应的SCC，那么后逆序就是用DFS访问leader的顺序

并且，有一个引理

所以只要利用DFS访问 $G^T$ ,得到后逆序，然后再利用DFS按照后逆序访问图G，就可以使得G中被指向的SCC先访问，最终DFS访问得到的一个连通分量就是一个SCC

找出图G中的强连通分量

第一步：求出 $G^T$

GT.png

第二步：求出后逆序
由A开始并按照字母序进行DFS遍历，并求出 $finish\_stack$
访问顺序为 A G B C H D I F E
得到的 $finish \_ stack$ 为 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}

图3.png