图论-强连通分量-Tarjan算法

有关概念:

  如果图中两个结点可以相互通达,则称两个结点强连通。

  如果有向图G的每两个结点都强连通,称G是一个强连通图。

  有向图的极大强连通子图(没有被其他强连通子图包含),称为强连通分量。(这个定义在百科上和别的大神的博客中不太一样,暂且采用百科上的定义)

  Tarjan算法的功能就是求有向图中的强连通分量

思路:

  定义DFNi存放访问到i结点的次序(时间戳),Lowi存放i结点及向i下方深搜到的结点中能追溯到的访问次序最小的结点的访问次序(即这些结点回溯上去能找到的最小的DFN值),找到未被访问过的结点时进栈,当找到一个强连通分量的根结点时(判断条件DFNi==Lowi),将该结点到栈顶之间的元素退栈,作为一个强连通分量

  从结点1开始,枚举每一个未被访问的结点,以该节点为点u,进栈,赋DFNu=Lowu=time++,枚举每一个以u为起点的边,找到指向的终点v,进行判断:

  (1)v未被访问过,则以v为起点继续深搜,并做Lowu=min(Lowu,Lowv);

  (2)v仍在栈内,则做Lowu=min(Lowu,DFNv);(如果v的访问次序更小,更新Lowu,在回溯时更新u的父结点的Low值)

  枚举完毕后,判断该结点是否为某一强连通分量的根节点,是则进行退栈操作

样例推导:

图论-强连通分量-Tarjan算法

从1开始深搜,1、2、4依次进栈

DFN={1,2,0,3,0,0}

搜索到4时有指向1的一条边,Low4=DFN1=1

图论-强连通分量-Tarjan算法

6进栈

DFN={1,2,0,3,0,4}

判定 DFN6==Low6,6为第一个强连通分量的根节点,从6向栈顶(其实就一个元素)退栈,得第一个强连通分量为{6}

图论-强连通分量-Tarjan算法

回溯到1,并更新Low值

DFN={1,2,0,3,0,4}

Low={1,1,0,1,0,4}

继续深搜到3,又有一条边指向4,Low3=DFN4=3

图论-强连通分量-Tarjan算法

5进栈,有一条边指向6,但6被访问过且不在栈内,pass

此时5满足条件出栈,第二个强连通分量为{5}

回溯到1,更新Low值

DFN={1,2,5,3,6,4}

Low={1,1,3,1,6,4}

最后1满足条件,从1到栈顶出栈,第三个强连通分量为{1,2,3,4}

图论-强连通分量-Tarjan算法

复杂度:

  每一个点和边均只被访问过一次,时间复杂度为O(n+m)

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN
#define MAXM
int n,m,time,cnt,heads[MAXN],DFN[MAXN],Low[MAXN],stack[MAXN],top,belong[MAXN];//time为访问次序,belong存该结点属于第几个强连通分量
bool vis[MAXN];//该结点是否在栈内
struct node
{
int v,next;
}edge[MAXM];
void add(int x,int y)
{
edge[++cnt].next=heads[x];
heads[x]=cnt;
edge[cnt].v=y;
}
void tarjan(int u)
{
DFN[u]=Low[u]=++time;
vis[u]=true;
stack[++top]=u;//进栈
for(int i=heads[u];i!=;i=edge[i].next)
{
int v=edge[i].v;
if(!DFN[v])//是否被访问过,DFN初值都为0,只有访问过才会被赋值
{
tarjan(v);
Low[u]=min(Low[u],Low[v]);
}
else if(vis[v])Low[u]=min(Low[u],DFN[v]);
}
if(DFN[u]==Low[u])//该结点为根结点,出栈
{
int i;
cnt++;
do
{
i=stack[top--];
vis[i]=false;
belong[i]=cnt;
print();//输出之类的操作
}while(u!=i);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);//默认输入有向边
}
cnt=;//cnt为强连通分量数量
for(int i=;i<=n;i++)
if(!DFN[i])tarjan(i);
return ;
}

*参考:http://baike.baidu.com/link?url=3xvU8jjqA2McnNL07G_5XHs8so96ZLAwjmc5oMPY1K67EkixIzyHdrn6QhqCsM9da0SVN_9vvca4iEcXJMyRVK

上一篇:\(\S1\) 描述性统计


下一篇:图之强连通、强连通图、强连通分量 Tarjan算法