Section-4 Connectivity 第4节 连通 - Kosaraju Kosaraju算法

Kosaraju算法

问题：

用Kosaraju算法求有向图(G)的强连通分支。

解法：

Kosaraju算法分为3个步骤：

((1))求出图(G)的逆图(G’)；

((2))求出逆图(G’)的拓扑排序(T)；

((3))按照逆图(G’)拓扑排序(T)的顺序，对原图(G)中每个节点进行DFS，得到的森林即为所求的强连通分支。注意每个节点只能属于一个强连通分支，因此当一个节点被DFS遍历到后，需要将其染红；

求出有向图(G)的逆图(G’)：

用矩阵可以表示为：

[
G =
\begin{bmatrix}
0 & 1 & 1 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 & 0 \
0 & 0 & 0 & 1 & 1 & 0 \
1 & 0 & 0 & 0 & 0 & 1 \
0 & 0 & 0 & 0 & 0 & 1 \
0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}
G’ =
\begin{bmatrix}
0 & 0 & 0 & 1 & 0 & 0 \
1 & 0 & 0 & 0 & 0 & 0 \
1 & 0 & 0 & 0 & 0 & 0 \
0 & 1 & 1 & 0 & 0 & 0 \
0 & 0 & 1 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 1 & 0
\end{bmatrix}
]

对逆图(G’)进行拓扑排序，得到顺序(T = [5, 4, 0, 1, 2, 3])。

按照顺序(T)对原图(G)进行DFS搜索，得到下面的森林，即为有向图(G)的(3)个强连通分支。这(3)个强连通分支中，任意节点(V_i)都存在一条路径可以到达其他任意节点(V_j)。

[
\begin{bmatrix}
tree_1 = [ 5 ] \
tree_2 = [ 4 ] \
tree_3 = [ 0, 1, 3, 2 ]
\end{bmatrix}
]