Strongly Connected Components – Kosaraju’s algorithm

之前一直做的都是无向图,最近开始处理有向图,发现复杂度比无向图高不止一个数量级啊。

BTW: 除了SCC,还有一个概念是weakly connected component,相当于将有向图当成无向图,然后算connected component。

———————-

SCC常用的三个算法:Kosaraju, Tarjan, Gabow。全都是线性算法。Kosaraju性能稍微差一些,需要DFS算2次且需要对原图做reverse,其他两个都只需要1次DFS计算。但是Kosaraju最好理解,没什么太难的地方。(我一开始看的是Gabow,对着原始论文看了一晚上,20+行的伪代码愣是没看懂)

算法:

  • Let G be a directed graph and S be an empty stack.
  • While S does not contain all vertices:
    • Choose an arbitrary vertex v not in S. Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.
  • Reverse the directions of all arcs to obtain the transpose graph.
  • While S is nonempty:
    • Pop the top vertex v from S. Perform a depth-first search starting at v in the transpose graph. The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search (BFS) can be used instead of depth-first search.

简单解释一下,算法大概分为3个步骤
1. 第一次对图进行DFS遍历,获得所有节点的“reverse postordering”;
2. 将原图做逆向,即边 a -> b 改成 b -> a;
3. 按照节点的“reverse postordering”,对逆向图做DFS;

算法的依据就在于一个图的SCC,在逆图中也是SCC。所以,对逆图的DFS遍历,其实是对之前找到的连通子图再做一次过滤。后一个DFS理论上也能改成BFS。

算法最难理解的地方,在于为什么第二次DFS必须按照节点的“reverse postordering”来进行?我找了很多资料,最后在算法导论22.5中找到了最清楚的解释。

先解释一下如何获得节点的“reverse postordering”:
void dfs1 ( int v )
{
vis[v]=true;
for (int i=0 ; i<adj[v].size() ; i++ )
if ( !vis[adj[v][i]] )
dfs1(u);

ord.push_back(v); //reverse postordering
}
只有当节点的所有邻居都被DFS遍历完,然后将节点压栈,得到的才是reverse postordering,也是graph的topological ordering。

image

对于一个biGraph,一定存在一个SCC,它和其它的SCC之间只有out-edge而没有in-edge。如上图中的SCC-abe。对图做DFS,节点的“reverse postordering”的第一个节点一定会落到这样的SCC中。例如上图(a),从节点c开始做DFS,最后完成的节点是b,位于SCC-abe中。

当对逆图进行DFS遍历时,因为SCC-abe在原图中没有in-edge,所有它在逆图中没有out-edge。因此,如果从b节点开始遍历,能够保证不会遍历到其他的SCC中去。所以“reverse postordering”的作用,在于找到逆图中没有out-edge的SCC中的节点。(简单的解释,更详细的还是得看算法导论)

网上能搜到不少算法的代码,我就不贴了。不过要注意,有些是错的。(甚至有些书里面都是错的,看着郁闷)

— END. —

Advertisements
相册 | 此条目发表在Graph Process分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s