强连通分量(Korasaju & Tarjan)学习笔记

强连通分量(Korasaju & Tarjan)学习笔记,第1张

连通分量(Korasaju & Tarjan)学习笔记

好久以前学过的东西...现在已经全忘了

很多图论问题需要用到强连通分量,还是很有必要重新学一遍的


强连通分量(Strongly Connected Component / SCC)

指在一个有向图中,存在的一个顶点集合S,对于所有顶点vi∈S,都保证能够互相到达

环就是最简单的强连通分量之一

但是强连通不等价于简单的环,还有可能是环套环、环套环套环...没有高效的算法很难解决这类问题


Korasaju

Korasaju是一个比较直观的解决SCC问题的算法,只需要用到两遍dfs

算法流程如下

(1)假设给定了一个如下的有向图

(2)对于原图进行一遍dfs,并且记录每一个顶点回溯时(★1)的序号(类似于树的后序遍历)

(3)建立一个反向图(将原图所有的边反向)

(4)按顶点dfs回溯序号从大到小(★2)进行rdfs(反向dfs),所有能访问到的顶点同属一个强联通分量

貌似看起来很简单.jpg

【以下是正确性的证明,加深印象用,可以选择跳过】

但是这个算法中有两个第一眼看过去并不容易理解的蛇皮 *** 作

  • (★1):为什么要记录dfs的后序而不是前序?
  • (★2):反向建图后,为什么要按dfs后序从大到小的顺序进行rdfs?

而这正是Korasaju算法的关键

强连通分量的性质是,在同一个分量中的任意两个顶点可以互相到达

对于一个顶点V为起点进行dfs和rdfs,那么V所属的强连通分量S在dfs和rdfs都能被访问到

问题在于,在两次搜索中,有可能有一些本身不在S中的顶点也被访问到了,再通过判断去除这些顶点会使算法的效率降低

那么我们可以考虑以V为起点进行dfs和rdfs一共会出现多少种情形

  1. 某一顶点在dfs和rdfs中都被访问到(那么这个顶点就属于V所在的强连通分量S中)
  2. 某一顶点在dfs中被访问到,在rdfs中没有访问到
  3. 某一顶点在rdfs中被访问到,在dfs中没有访问到

第2、3种情形中的顶点一定不属于强连通分量S,但是如何排除?我们可以考虑通过在rdfs中统计V所在的强连通分量S中的顶点

这样一来,第2种情形

某一顶点在dfs中被访问到,在rdfs中没有访问到

无需特殊处理

但是第3种情形

某一顶点在rdfs中被访问到,在dfs中没有访问到

暂时还是没有办法解决

我们可以考虑一下这种典型情形

以1为起点进行dfs,那么不会访问到3 但是以1位起点进行rdfs就会访问到3

但是记录dfs的后序恰好能够解决这样的问题

对于单点进行dfs的过程其实形成了一棵搜索树,由先访问到的顶点(层数较小)指向后访问到的顶点(层数较大)

dfs后序具有这样的性质:对于某搜索树中的一点P,P的dfs后序一定比P的子树中所有顶点的dfs后序大

而对于整个图的dfs就形成了一个搜索树构成的森林,整张图dfs后序最大顶点的总是某一棵树的根R

现在考虑R在反向图中出边的情况(入边即是原图中R的出边,已经在dfs中使用过了)

  1. 如果R有出边(R,V),且V在以R为起点dfs的搜索树中 那么V在R所属的强连通分量中
  2. 如果R有出边(R,V'),且V'不在在以R为起点dfs的搜索树中 那么在原图中,存在边(V',R),则R必然在V'所在的搜索树中,与R为某搜索树的根矛盾

所以对R进行rdfs,访问到的顶点全部在R所在的强连通分量中

这时,将这些点从以R为根的搜索树中删去,则搜索树被拆分成森林 根据dfs后序的性质,剩下来所有rdfs未访问的顶点中dfs后序最大的仍是某棵树的根R'

这样一来,Korasaju的正确性得以证明(好绕啊...)

一句话总结算法:建正向、反向图,dfs记录后序,从大到小rdfs

 #include <cstdio>
 #include <cstring>
 #include <vector>
 using namespace std;

 ;

 int n,m;
 vector<int> v[MAX],rv[MAX];

 bool vis[MAX];
 vector<int> ord;

 inline void dfs(int x)
 {
     vis[x]=true;
     ;i<v[x].size();i++)
     {
         int next=v[x][i];
         if(!vis[next])
             dfs(next);
     }
     ord.push_back(x);
 }

 ;
 vector<int> scc[MAX];

 inline void rdfs(int x)
 {
     scc[sz].push_back(x);
     vis[x]=true;
     ;i<rv[x].size();i++)
     {
         int next=rv[x][i];
         if(!vis[next])
             rdfs(next);
     }
 }

 int main()
 {
 //    freopen("input.txt","r",stdin);
     scanf("%d%d",&n,&m);
     ;i<=m;i++)
     {
         int x,y;
         scanf("%d%d",&x,&y);
         v[x].push_back(y);
         rv[y].push_back(x);
     }

     ;i<=n;i++)
         if(!vis[i])
             dfs(i);

     memset(vis,false,sizeof(vis));
     ;i>=;i--)
     {
         int cur=ord[i];
         if(!vis[cur])
         {
             sz++;
             rdfs(cur);
         }
     }

     ;i<=sz;i++)
     {
         printf("SCC #%d:",i);
         ;j<scc[i].size();j++)
             printf(" %d",scc[i][j]);
         printf("\n");
     }
     ;
 }

输入:



输出:

SCC #:
SCC #:
SCC #:
SCC #: 

Tarjan

Tarjan大爷就知道玩dfs,什么算法都是dfs搞出来的orz

这个算法网上讲的也比较全了

我觉得写得比较好的一篇

感觉也就记一记实现方法吧...正确性挺对的但总感觉缺少一点细节

算法流程:

(1)对于每个顶点V维护两个值

  • dfn[V]:顶点V的dfs前序
  • low[V]:顶点V能到达的节点Pi中,dfn[Pi]的最小值【可能的Pi为当前搜索树中的所有顶点】

(2)访问当前顶点V,idx++(用于统计已经搜索到的顶点数量),dfn[V]=idx,先给low[V]初值idx,将V压入栈

(3)访问与V有边(V,Ui)且没有被访问过的顶点Ui;借助与V有边(V,Ui')且已在栈中的顶点Ui'更新low[V]的值,low[V]=min{ low[V] , dfn[Ui'] }(这里其实dfn[Ui']==low[Ui'])

(4)借助所有Ui,更新low[V]的值,low[V]=min { low[V] , low[Ui] }

(5)判断:如果low[V]==dfn[V],则栈中的所有顶点同属一个强连通分量,则全部d出栈;否则当无事发生(笑)

【简单分析一下正确性,可跳过】

整个图是由很多坨(有多个顶点的)强连通分量和伸出/伸入的“触须”构成的

  • 如果是单纯的一坨强连通分量,那么显然子树中的任意点都可以通过一些边回到层数更小的点,从而避免被单独d出当做强连通分量
  • 如果这一坨强连通分量有伸出的“触须”,那么“触须”上的所有点均无法访问到层数更小的点,会被依次d出
  • 如果有伸入这一坨强连通分量的“触须”,那么强连通分量中的所有点均无法访问到“触须”上的点,会在强连通分量d出后被依次d出
 #include <cstdio>
 #include <cstring>
 #include <cmath>
 #include <vector>
 using namespace std;

 ;

 int n,m;
 vector<int> v[MAX];

 int index;
 int dfn[MAX],low[MAX];
 bool in[MAX];
 vector<int> stack;

 int sz;
 vector<int> scc[MAX];

 void Tarjan(int x)
 {
     dfn[x]=low[x]=++index;
     in[x]=true;
     stack.push_back(x);

     ;i<v[x].size();i++)
     {
         int next=v[x][i];

         if(!dfn[next])
         {
             Tarjan(next);
             low[x]=min(low[x],low[next]);
         }
         else
             if(in[next])
                 low[x]=min(low[x],dfn[next]);
     }

     if(low[x]==dfn[x])
     {
         sz++;
         int y;
         do
         {
             y=stack.back();
             stack.pop_back();
             in[y]=false;
             scc[sz].push_back(y);
         }
         while(y!=x);
     }
 }

 int main()
 {
 //    freopen("input.txt","r",stdin);
     scanf("%d%d",&n,&m);
     ;i<=m;i++)
     {
         int x,y;
         scanf("%d%d",&x,&y);
         v[x].push_back(y);
     }

     ;i<=n;i++)
         if(!dfn[i])
             Tarjan(i);

     ;i<=sz;i++)
     {
         printf("SCC #%d:",i);
         ;j<scc[i].size();j++)
             printf(" %d",scc[i][j]);
         printf("\n");
     }
     ;
 }

SCC往往是其他图论算法的一个子任务,就不单独找题练了(模板题NOIP2015 D1T2)

(完)

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/585462.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-12
下一篇 2022-04-12

发表评论

登录后才能评论

评论列表(0条)

保存