Strongly Connected Components – Tarjan’s algorithm

wiki上说,Tarjan算法是Kosaraju算法的一个“improved version”,我个人不太赞成这个说法。两个算法确实在某些设计上有类似,但本质是不太一样的。

Kosaraju算法的核心出发点是一个图的SCC在它的逆图中也是SCC。所以算法中需要对原图求逆。

Tarjan算法,我个人的理解,它抓住的是SCC的环的本质。一个SCC,是由一个或者几个环构成的:

image

一个环如果用DFS进行遍历的话,得到的是一条“直线”的路径。例如上图,如果从b点开始进行DFS遍历的话,会得到 b > c > d > e > a。如果每遍历到一个点,就给它一个timestamp,能够得到 b(1) > c(2) > d(3) > e(4) > a(5),因为是环,a会存在一个路径指向b。Tarjan算法会将b的timestamp“传播”给a,然后在DFS回退的过程中,b的timestamp又会依次的传递给e, d, c,最后,环中每个节点的timestamp都变成了最早被遍历到的节点b的timestamp。于是,相同timestamp的节点就属于同一个SCC了,如下图:

如果说Tarjan和Kosaraju有什么相同的地方,就是它们都是在DFS遍历的后序阶段做文章。Kosaraju的第一次DFS得到的是节点的后序排列,而Tarjan则是在后序阶段计算节点的Low值。

总的来说,Tarjan是个很好理解的算法。甚至我认为它的思路比Kosaraju还更清晰一些。

伪码:

image

Reference

1. http://en.algoritmy.net/article/44220/Tarjans-algorithm

2. http://www.byvoid.com/blog/scc-tarjan/

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