浅析强连通分量(Tarjan及Kosaraju算法)

强连通分量的专题早在一个月前就AK了,虽然这是个很基础的算法,在图论中的地位不容小觑,和最短路一样十分重要;


强连通分量和强连通图的概念想必是不用多说了

在有向图G中,如果两点互相可达,则称这两个点强连通,如果G中任意两点互相可达,则称G是强连通图。
非强连通有向图的极大强连通子图,称为强连通分量

Kosaraju算法

为什么先讲这个呢,因为这个算法从理解上来说要好懂一些;

首先我们来看一张图

这张图里有两个强连通分量,分别是(A1,A2,A3)和(B1,B2,B3)
容易想到,如果我们从b开始DFS,那么经过两次DFS可以遍历完全图,并且每次遍历的都是不同的连通分量;但是如果从a开始就不能得到正确的答案,因为只需要一次DFS就能遍历完全图,显然是错误的;
为什么呢,因为如果先访问那些指向了其他分量的分量,DFS一定能进入到其他连通分量中,这是我们不想得到的。
显然,为了找出全部的强连通分量,我们只要保证DFS访问顶点的顺序为B强连通分量中任意一个顶点在A强连通分量全部顶点之前即可。
那么也就是说我们需要找到一个正确的DFS顺序,保证一次调用DFS肯定是在同一个连通分量里面遍历,而不会跑到其他连通分量中。
那么现在的问题转化成了如何确定正确的顶点顺序;

Kosaraju算法的做法是:先将原图取反,然后从任意节点开始DFS逆后序遍历,得到的顶点顺序就是答案;那么什么是逆后序呢?

逆后序即DFS递归调用返回之前,将该顶点压入栈中得到的序列,通俗的讲就是拓扑序。

那么为什么这样的顶点序就是正确的呢?
由于我们先对原图取了反,那么对于上面那幅图来说DFS只有两种可能,就是从A中某个点开始或者B、中某个点开始;

如果从A中开始DFS,那么需要两次DFS,第一次A1,A2,A3入栈,第二次B1,B2,B3入栈,保证了B中有点在A之前;
如果从B中开始DFS,需要一次DFS即可遍历全图,假设从B2开始遍历,那么除了B2之外的其他点先入栈,最后才是B2点,这样也保证了B中有点在A之前;

显然当连通分量个数大于2时结论也成立;

现在有了正确的DFS顶点顺序,再进行一次DFS就能找到所有强连通分量了;


Kosaraju模版

//Kosaraju
const int maxn =1e5, maxm=2e5;
struct node{
    int to,next;
}g[maxm],g2[maxm]; //逆图,原图
int dfn[maxn],head1[maxn],head2[maxn],belong[maxn],num[maxn];
//dfn时间戳
//belg记录每个点属于哪个连通分量
//num记录强连通分量点的个数
bool vis[maxn];
int cnt,cnt1,scc,tot1,tot2;
void init(){
    tot1=tot2=0;
    memset(head1,-1,sizeof(head1));
    memset(head2,-1,sizeof(head2));
    memset(num,0,sizeof(num));
}
void addedge(int u,int v){
	g2[tot2]={v,head2[u]}; head2[u]=tot2++;
	g[tot1]={u,head1[v]}; head1[v]=tot1++;
}
void dfs1(int u){//求逆后序
    vis[u]=1;
    for(int k=head2[u];~k;k=g2[k].next)
        if(!vis[g2[k].to]) dfs1(g2[k].to);
    dfn[++cnt1]=u;
}
void dfs2(int u){
    vis[u]=1; cnt++;
    belong[u]=scc;
    for(int k=head1[u];~k;k=g[k].next)
        if(!vis[g[k].to]) dfs2(g[k].to);
}
void Kosaraju(int n){
    memset(dfn,0,sizeof(dfn));
    memset(vis,0,sizeof(vis));
    cnt1=scc=0;
    for(int i=1;i<=n;i++)
        if(!vis[i]) dfs1(i);
    memset(vis,0,sizeof(vis));
    for(int i=cnt1;i>0;i--)
        if(!vis[dfn[i]]){
            cnt=0;
            ++scc;
            dfs2(dfn[i]);
            num[scc] = cnt;
        }
}

 


Tarjan算法

总的来说, Tarjan算法是基于一个观察,即:同处于一个SCC中的结点必然构成DFS树的一棵子树。 我们要找SCC,就得找到它在DFS树上的根

Tarjan算法有两个重要的数组:DFN[]和LOW[],理解了这两个数组,Tarjan也就理解的差不多了;

DFN[]:每个点搜索的次序编号(时间戳),简单来说就是第几个被搜索到的。显然每个点的时间戳都不一样,并且一旦某个点被DFS到后,这个时间戳就不再改变;

LOW[]:该点所在子树中,仍在栈中的最小时间戳;也即这个点所能到达的最小的时间戳;

初始时DFN[] = LOW[]= ++index

我们在DFS时,对于每个点,寻找与其相连的点,判断这些点是否已经被搜索过,若没有,则进行搜索。若该点已经入栈,说明形成了环,则维护low[u]=min(low[u],low[v])

当dfn[u]=low[u]时,以u为根的搜索子树上所有节点是一个强连通分量;此时u也被称为关键点;
显然,关键点能够遍历其属强连通分量的起始点,而且这样的起始点一定只有一个,所以只要发现了一个这样的关键起始点,那么就一定发现了一个强连通分量。而且这个节点没有(属于其他强连通分量的点)能够有一条有向路径连到这个节点来:如果这样的点存在,那么这些点应该属于同一个强连通分量。


Tarjan模版

int n,m;
int sz, dfn[maxn],low[maxn],vis[maxn],belong[maxn];
int scc;//强连通分量个数
stack<int> sta;
void init(){
    rep(i,0,n) vis[i]=0,head[i]=-1,dfn[i]=0;
    while(!sta.empty()) sta.pop();
    scc = cnt = sz = 0;
}
void tarjan(int u){
    dfn[u]=low[u]=++sz; vis[u]=1; sta.push(u);
    for(int i = head[u]; ~i; i = g[i].next) {
        int v = g[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(vis[v] && low[u] > dfn[v]) low[u]=dfn[v];
    }
    if(low[u]==dfn[u]) {
        scc++;
        while(1){
            int id = sta.top(); sta.pop();
            vis[id] = 0;
            belong[id]=scc;
            if(id == u) break;
        }
    }
}

 


好啦,强连通分量介绍完了,那么为什么说它重要呢?由于在许多图论题中,只要涉及到DFS基本都要处理环的部分,有时这是一个很复杂的工作,但是如果我们采用强连通分量缩点,就可以把原图变成一个DAG,即有向无环图,这样在解决某些问题时就方便了很多。

比如对于这道题:

给定一个有向图,每个点i有点权w(i),请对于每个点i,找到i能到达的点中点权的最大值(包括i点)。

对于无环图显然一次记忆化搜索就可以得到答案 ans[u]=max(w[u],ans[v]),但是题目中没有说无环,那么我们就可以先缩点建立新图,对于缩完的每个新点,他们的权值显然是这个连通分量中所有点权中最大的那个;


缩点代码

void work(){ //缩点
    rep(i,1,n) if(!dfn[i]) tarjan(i);
    int de[maxn]={0,};//入度
    rep(i,1,n)
    for(int j=head[i];j!=-1;j=g[j].next){
        int v=g[j].to;
        if(belong[i]!=belong[v]) addedge(belong[i],belong[v]),de[belong[v]]++;
    }
    rep(i,1,scc) if(!de[i]) {//...}
}

 

这只是最基础的一个例子,还有类似于求最小花费,最短路径,树形DP等等题目是需要缩点来做的,总的来说,强连通分量更像是一个基础工具,学会了这个对于很多图论题都很有帮助的。

EOF

发表评论,支持MarkDown语法