Kosaraju算法

SCC

SCC = strong connected component. 即强连通分量。

In the mathematical theory of directed graphs, a graph is said to be strongly connected or diconnected if every vertex is reachable from every other vertex the strongly connected components or diconnected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. (wikipedia)

强连通分量是指有向图的一个子图，在该子图中所有的结点到其他结点都是可达的。

在这里插入图片描述

Kosaraju算法

Kosaraju‘s algorithm (also known as the Kosaraju–Sharir algorithm)

Is a linear time algorithm to find the strongly connected components of a directed graph.

It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.

Main procedure:

Traverse edges in the backward direction to get the transpose graph.

DFS the transpose graph you get, store the visit sequence in a stack

DFS the original graph using the stack.

1. 对原图所有边的方向取反得到原图的逆图。
2. 对逆图进行深度优先遍历，访问结点的顺序存入一个栈中(即逆后序)。
3. 按出栈的顺序对原图进行深度优先遍历。

O(V+E) if you are using the adjacent list.

Pseudo-code

1. For each vertex u of the graph, mark u as unvisited. Let L be empty.
2. For each vertex u of the graph do Visit(u), where Visit(u) is the recursive subroutine: If u is unvisited then: 1. Mark u as visited. 2. For each out-neighbour v of u, do Visit(v).
   1. Prepend u to L. Otherwise do nothing.
3. For each element u of L in order, do Assign(u,u) where Assign(u,root) is the recursive subroutine: If u has not been assigned to a component then:
   1. Assign u as belonging to the component whose root is root.
   2. For each in-neighbour v of u, do Assign(v,root). Otherwise do nothing.

参考文献

https://www.cnblogs.com/nullzx/p/6437926.html 这篇文章里有实例分析。