处理SCC(强连通分量问题)的Tarjan算法

在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected),如果有向图G的每两个顶点都强连通,称G是一个强连通图.

如图所示,蓝色框圈起来的是一个强连通分量

通俗的说法是:从图G内任意一个点出发,存在通向图G内任意一点的的一条路径.

非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components,SCC).

求图强连通分量的意义是:由于强连通分量内部的节点性质相同,可以将一个强连通分量内的节点缩成一个点,即消除了环,这样,原图就变成了一个有向无环图(directed acyclic graph,DAG).显然对于一个无向图,求强连通分量没有什么意义,联通即为强连通.

求强连通分量比较高效的算法是SCC Tarjan算法,BYV牛有一个很好的说明,推荐大家看一看:有向图强连通分量的Tarjan算法« Beyond the Void,我在这里就不照搬了.

Tarjan 算法基本基于DFS,时间复杂度就是遍历图一遍,为\(\Theta (N)\),Tarjan 貌似很喜欢深搜的样子,LCA被深搜活生生的弄成了\(\Theta (N)\),SCC 看来一样,Tarjan 一出现,时间复杂度果然降了一个数量级.

先看BYV牛的CODE,写的真不错,虽然第一遍我没看懂,不过相信加了注释后会好理解多,如果有错误,别打我.

SCC Tarjan算法的基本框架:

  • 遍历一个点,指定一个唯一时间戳DFN[i];指定该点向前追溯可追溯到的最老时间戳LOW[i].
  • 枚举当前点所有边,若DFN[j]=0表明未被搜索过,递归搜索之.
  • 若DFN[j]不为0,则j被搜索过,这时判断j是否在栈中,且j的时间戳DFN[j]小于当前时间戳DFN[i],可判定成环.将LOW[i]设定为DFN[j]
  • 若这个点LOW[i]和DFN[i]相等,说明这个节点是所有强连通分量的元素中在栈中最早的节点.
  • 弹栈,将这个强连通分量全部弹出,缩成点.

这里解释下比较晦涩的两个词:

LOW[i],这个向前追溯可追溯到的最老时间戳 的意思是根据有向图的方向遍历,在有环的情况下,向前追溯可以达到较早的点.在每次递归调用Tarjan(j)后我们可以高速较快的更新LOW[i]

至于所有强连通分量的元素中在栈中最早的节点.是这样的,所有自成强连通分量的节点或子图,在本次弹栈前都已经弹出去了,这时栈里所元素的LOW都大于等于DFN[该强连通分量的最早遍历节点],栈顶元素一定比下面元素的时间戳要大

在遍历完所有相关边之后再验证(DFN[i]==LOW[i]),可以避免有漏判情况,这时,当前节点的子节点已经将LOW更新的很优了,不存在一个强连通分量被包含在一个强连通分量里的情况.

学习SCC Tarjan算法有两道测验题:

POJ 2186 Popular Cows

POJ 1236 Network of Schools
参见Comzyh这两道强连通分量的题解

原创文章,转载请注明(最好把图片带走): 转载自Comzyh的博客

本文链接地址: 处理SCC(强连通分量问题)的Tarjan算法

6 Responses

发表评论