处理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,写的真不错,虽然第一遍我没看懂,不过相信加了注释后会好理解多,如果有错误,别打我.

void tarjan(int i)//Tarjan 
{
	int j;
	DFN[i]=LOW[i]=++Dindex;//Index 时间戳 
	instack[i]=true;//标记入栈 
	Stap[++Stop]=i;//入栈 
	for (edge *e=V[i];e;e=e->next)//枚举所有相连边 
	{
		j=e->t;//临时变量 
		if (!DFN[j])//j没有被搜索过 
		{
			tarjan(j);//递归搜索j 
			if (LOW[j]<LOW[i])//回溯中发现j找到了更老的时间戳 
				LOW[i]=LOW[j];//更新能达到老时间戳 
		}
		else if (instack[j] && DFN[j]<LOW[i])//如果已经印有时间戳 且 时间戳比较小,则有环 
			LOW[i]=DFN[j];//当前记录可追溯时间戳更新 
	}
	if (DFN[i]==LOW[i])//可追溯最老是自己,表明自己是当前强连通分量的栈底 
	{
		Bcnt++;//强连通分量数增加 
		do
		{
			j=Stap[Stop--];//出栈顶元素 
			instack[j]=false;//标记出栈 
			Belong[j]=Bcnt;//记录j所在的强连通分量编号 
		}
		while (j!=i);//如果是当前元素,弹栈完成 
	}
}
void solve()
{
	int i;
	Stop=Bcnt=Dindex=0;
	memset(DFN,0,sizeof(DFN));//标记为为搜索过 
	for (i=1;i<=N;i++)
		if (!DFN[i])
			tarjan(i);
}

void tarjan(int i)//Tarjan

{

int j;

DFN[i]=LOW[i]=++Dindex;//Index 时间戳

instack[i]=true;//标记入栈

Stap[++Stop]=i;//入栈

for (edge *e=V[i];e;e=e->next)//枚举所有相连边

{

j=e->t;//临时变量

if (!DFN[j])//j没有被搜索过

{

tarjan(j);//递归搜索j

if (LOW[j]<LOW[i])//回溯中发现j找到了更老的时间戳

LOW[i]=LOW[j];//更新能达到老时间戳

}

else if (instack[j] && DFN[j]<LOW[i])//如果已经印有时间戳且时间戳比较小,则有环

LOW[i]=DFN[j];//当前记录可追溯时间戳更新

}

if (DFN[i]==LOW[i])//可追溯最老是自己,表明自己是当前强连通分量的栈底

{

Bcnt++;//强连通分量数增加

{

j=Stap[Stop--];//出栈顶元素

instack[j]=false;//标记出栈

Belong[j]=Bcnt;//记录j所在的强连通分量编号

}

while (j!=i);//如果是当前元素,弹栈完成

}

void solve()

{

int i;

Stop=Bcnt=Dindex=0;

memset(DFN,0,sizeof(DFN));//标记为为搜索过

for (i=1;i<=N;i++)

if (!DFN[i])

tarjan(i);

}

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算法

7 replies on “处理SCC(强连通分量问题)的Tarjan算法”

CodeWays说道：

2011年04月9日 5:10 下午

相关博文的链接都失效了奥~

回复
1. comzyh说道：
  
  2011年04月9日 9:52 下午
  
  竟然还有人留言哈，激动…
  问题已修复，谢谢指正
  
  回复
hotmocha说道：

2012年12月23日 7:22 下午

你的blog很不错，以后有空会过来看看哈哈，请问动画是用什么软件制作的还是？？？？

回复
1. comzyh说道：
  
  2013年03月25日 4:32 下午
  
  渣渣的Flash~~
  
  回复
Pingback： POJ 2186 & 1236 强连通分量 Tarjan算法 | Comzyh的博客
Anatasmloz说道：

2016年10月24日 7:03 下午

谢谢

回复
wuming说道：

2019年11月14日 4:58 下午

受教了，前辈

回复

发表评论取消回复

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。

共享此文章：

赞过：

相关

7 replies on “处理SCC(强连通分量问题)的Tarjan算法”

发表评论取消回复