在介绍算法之前，首先引入时间戳和追溯点的概念。
时间戳: dfn[u]表示 u结点深度优先遍历的序号。
追溯点: low[u]表示 u结点或u的子孙能通过非父子边追溯到的dfn最小的结点序号。即回到最早的过去
例如，在深度优先搜索中，每个点的时间戳和追溯点求解过程如下。
初始时，dfn[u]=low[u], 如果该结点的邻接点未被访问，则一直深度优先遍历，1- -2-3-5-6- -4， 此时4的邻接点1已被访问，且1不是4的父节点，4的父节点是6 (深度优先搜索树上的父结点)。
那么4号结点能回到最早的过去是1号结点( dfn=1 )，因此low[4]=min(low[4],dfn[1])=1。返回时，更新路径上所有祖先结点的low值，因为子孙能回到的追溯点，其祖先也能回到
如图所示。
1.无向图的桥判定法则:·
无向边(x.y)是桥，当且仅当搜索树上存在x的一个子节点y满足:
low[y] > dfm[x]
就是说，孩子的low值比自己的dfn.值大，则该结点到这个孩子的边为桥。下图中，边(5,7)，5的子节点7,满足low[7]>dfmn[5]，因此该边为桥。
实验代码
#include<iostream> #include<cstring> using namespace std; const int maxn = 1000+5; int n,m; int head[maxn],cnt; struct Edge{ int to,next; }e[maxn<<1]; int low[maxn],dfn[maxn],num; void add(int u,int v){ e[++cnt].next = head[u]; e[cnt].to = v; head[u] = cnt; } void tarjan(int u,int fa)//u当前节点 fa:u的父节点 { dfn[u]=low[u]=++num;//结点的dfn和low 进行初始化 for(int i=head[u];i;i=e[i].next) { int v=e[i].to;//v:u的临界点 也是子节点 if(v==fa)//如果v是u的父节点,则直接结束. 因为判断桥时,要的是当前节点和其子节点.. continue; if(!dfn[v])//v未访问过 { tarjan(v,u); //进行深度优先遍历 low[u]=min(low[u],low[v]);//更新父节点的low值,孩子能到达的,父亲一定也能到达. if(low[v]>dfn[u])//如果孩子结点的Low值 > 父节点的dfn则说明u是桥. cout<<u<<"---"<<v<<"是桥"<<endl; } else//v已被访问, 且u-->v 所以 更新u的low值. low[u]=min(low[u],dfn[v]); } } void init(){ memset(head,0,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); cnt = num = 0; } int main(){ while(cin>>n>>m){ init(); int u,v; while(m--){ cin>>u>>v; add(u,v); add(v,u); } for(int i = 1; i <=n; i++){ if(!dfn[i]){// 防止不是连通图的情况. tarjan(i,0); } } } }
2.无向图的割点割点判定法则
若x不是根结点，则x是割点，当且仅当搜索树上存在x的一.个子节点y，满足:
low[y]≥dfn[x]
若x是根结点，则x是割点，当且仅当搜索树上存在至少两个子节点，满足上述条件。就是说，如果不是根，孩子的low值大于等于自己的dfn值，该结点就是割点;如果是根，至少需要两个孩子满足条件。
①.当x不是根节点时:
下图中，5的子节点7，满足low[7]>dfn[5]，因此5是割点。
②.当x是根节点时,两个节点不存在割点.只有三个及其以上(也就是根节点至少有两个子节点)时,才可能有割点.第二幅图中,根节点的两个子节点满足,则1是割点.
最后来解释下为啥判断条件里面有个 = ?
很简单,从下图看,2,3是割点,而dfn[ 3 ] = low[ 3 ] ,所以得加上等号…哈哈
实验代码
#include<iostream> #include<cstring> using namespace std; const int maxn=1000+5; int n,m; int head[maxn],cnt,root; struct Edge { int to,next; }e[maxn<<1]; int low[maxn],dfn[maxn],num; void add(int u,int v) { e[++cnt].next=head[u]; e[cnt].to=v; head[u]=cnt; } void tarjan(int u,int fa) { dfn[u]=low[u]=++num; int count=0;//用于计数 ,因为跟节点必须有两个节点而且子节点的low>= 根节点才说明根节点是割点. for(int i=head[u];i;i=e[i].next)//访问当前节点u的临界点. { int v=e[i].to; if(v==fa) continue; if(!dfn[v]) { tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]) { count++; if(u!=root||count>1)//如果不是跟则,割点已找到.如果是根,则应该判断count是否>=2.. cout<<u<<"是割点"<<endl; } } else low[u]=min(low[u],dfn[v]); } } void init() { memset(head,0,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); cnt=num=0; } int main() { while(cin>>n>>m) { init(); int u,v; while(m--) { cin>>u>>v; add(u,v); add(v,u); } for(int i=1;i<=n;i++) if(!dfn[i])//从哪个节点开始,那个节点就是根. { root=i; tarjan(i,0); } } return 0; }
3.有向图的强连通分量
算法步骤:
1)深度优先遍历结点， 第一次访问结点x时，将x入栈，且dfn[x]=low[x]=++num;
2)遍历 x的所有邻接点y,
若y没被访问，则递归访问y,返回时更新low[x]=min(low[x]low[y]);
若y已被访问且在栈中，则令low[x]=min(low[x],low[y]);
x 回溯之前，判断如果low[x]=dfn[x], 则从找中不断弹出结点，直到x出栈停止。
弹出的结点就是一一个连通分量。
为啥连通判断条件时low[x]=dfn[x]呢?
因为对于一个连通分量来说,里面所有的low值都是相同的,都等于这个连通分量最开始搜索的那个点的low和dfn.在这个连通分量中只有该点满足low=dfn其他的都是dfn>low.回溯到这里则可以从stack中弹出刚才遍历的那些点了.
实验代码
#include<iostream> #include<cstring> #include<stack> using namespace std; const int maxn=1000+5; int n,m; int head[maxn],cnt; stack<int>s;//开一个栈 bool ins[maxn]; struct Edge { int to,next; }e[maxn<<1]; int low[maxn],dfn[maxn],num; void add(int u,int v) { e[++cnt].next=head[u]; e[cnt].to=v; head[u]=cnt; } void tarjan(int u) { low[u]=dfn[u]=++num; ins[u]=true; s.push(u); for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(!dfn[v])//如果没有被访问过,则进行深搜访问. { tarjan(v); low[u]=min(low[u],low[v]);//维护父节点. } else if(ins[v])//如果访问过而且在栈中. 因为v先访问过了,所以dfn会比较小(因为在入栈时,low和dfn相同,所以min里面dfn[v]和low[v]都行...). low[u]=min(low[u],low[v]); }//u的所有邻接点已访问完毕. if(low[u]==dfn[u])//连通分量之间交接的点的low和dfn相同. { int v; cout<<"连通分量："; do { v=s.top(); s.pop(); cout<<v<<" "; ins[v]=false;//当前节点已出栈,标记发生改变 }while(v!=u);//一直弹出直到u cout<<endl; } } void init() { memset(head,0,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(ins,0,sizeof(ins)); cnt=num=0; } int main() { while(cin>>n>>m) { init(); int u,v; while(m--) { cin>>u>>v; add(u,v); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); } return 0; } /* 5 8 1 3 1 2 3 5 3 4 3 2 4 5 4 1 5 1 */ /* 7 9 1 2 2 3 3 1 2 4 4 7 7 4 4 5 5 6 */
运行结果:
注意:有向图的强连通分量和无向图的连通分量是完全不同的概念,Tarjan算法也大不一样.对于无向图,连通分量的标号可以用low直接表示,但对于有向图则完全不可以.在无向图中连通分量的个数就是low的最大值,而在强连通分量中不是.
