Tarjan算法

Tarjan算法是用来求强连通的一种算法。在学习算法之前,我们需要了解强连通的概念。

强联通

​ 在一张有向图中,对于任意两个点v1,v2,存在从v1->v2 和v2->v1 的路径,则称这张图为强连通图。

强联通子图

​ 在一张有向图中,存在一张子图是强连通图,则称这个子图为强连通子图,其极大强连通子图称之为强连通分量

Tarjan的作用就是求强连通分量。

在遍历之前,我们需要建立一个栈来统计当前未被处理的节点。

对于下图:

我们从节点1开始dfs遍历,其中DFN表示遍历的编号,LOW表示连通块中最小的遍历的编号:

(此时栈中元素为:1 2 3 6)

遍历到节点6后,开始回溯,此时判断DFN是否等于LOW,如果相等,那么这是强连通分量上的一个点:

(此时栈中元素为:1 2 3)

回溯到节点3时,没有其他路可走,那么就判断DFN是否等于LOW,同时更新LOW[ 3 ]的值:

(此时栈中元素为:1 2)

接下来从节点2向下遍历:

(此时栈中元素为:1 2 5)

由于5 -> 1 中节点1已经访问过了,那么此时我们更新LOW[ 5 ] = LOW[ 1 ] = 1,然后回溯更新LOW[2]=LOW[ 1 ]:

(此时栈中元素为:1 2 5)

回溯到节点1,向下搜节点4,节点5被访问过,回溯LOW[ 4 ]=LOW[ 5 ] = 1 :

(此时栈中元素:1 2 5 4)

继续回溯到节点1,此时节点1相邻边已被访问完毕,判断DFN是否等于LOW,相等就开始标记强连通分量。将栈中元素LOW相等的全部连通。

完毕。

模板为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int n,m,tt,cnt,sig;
int vis[maxn],low[maxn],dfn[maxn];
int color[maxn];//color[]为染色,即强连通中的元素染成同一种颜色。
stack<int>st;
vector<int>vec[maxn];
void init(){
memset(vis,0,sizeof(vis));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(color,0,sizeof(color));
for(int i=1;i<=n;i++) vec[i].clear();
while(!st.empty()) st.pop();
}
void tarjan(int x){
vis[x]=1;
dfn[x]=low[x]=cnt++;
st.push(x);
for(int i=0;i<vec[x].size();i++){
int y=vec[x][i];
if(vis[y]==0) tarjan(y);//未被访问过,向下遍历
if(vis[y]==1) low[x]=min(low[x],low[y]);//更新LOW下标
}
if(low[x]==dfn[x]){
sig++;//染色序号
int flag=0;
while(!flag){//将栈中x及其以后的节点全部标记为同一种颜色(sig)
int t=st.top(); st.pop();
if(t==x) flag=1;
color[t]=sig;
vis[t]=-1;
}
}
}
void solve(){
tt=-1;cnt=1;sig=0;
for(int i=1;i<=n;i++){
if(vis[i]==0) tarjan(i);
}
/*
此处添加其他操作
*/
}
感谢您的支持
-------------本文结束感谢您的阅读-------------