图论 求有向图的所有强连通分量 kosaraju算法

本文主要是介绍图论 求有向图的所有强连通分量 kosaraju算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题

如何找到有向图（a）中的所有强连通分量，如图（b)

 

 二、kosaraju算法

Kosaraju的算法（又称为–Sharir Kosaraju算法）是一个线性时间(linear time)算法找到的有向图的强连通分量。

 

1. 原理

它利用了一个事实，逆图（与各边方向相同的图形反转, transpose graph）有相同的强连通分量的原始图。

 

2. 逆图

将各边的方向反转

 

3. 算法图示

上图是对图G,进行一遍DFS（深度优先搜索）的结果，

• 1、2、4、6
• 1、3、5

 

每个节点有两个时间戳，即节点的

• 发现时间u.d（左边，即搜索发现的时间）
• 完成时间u.f（右边，即搜索返回的时间）

 

我们将完成时间较大的，按大小（从小到大）加入堆栈

1)每次从栈顶取出元素

2)检查是否被访问过

3)若没被访问过，以该点为起点，对逆图进行深度优先遍历

4)否则返回第一步，直到栈空为止

 

[ATTENTION] : 对逆图搜索时，从一个节点开始能搜索到的最大区块就是该点所在的强连通分量。

• 从节点1出发，能走到  2 ，3，4 ， 所以{1 , 2 , 3 , 4 }是一个强连通分量
• 从节点5出发，无路可走，所以{ 5 }是一个强连通分量
• 从节点6出发，无路可走，所以{ 6 }是一个强连通分量

自此Kosaraju Algorithm完毕，这个算法只需要两遍DFS即可，是一个比较易懂的求强连通分量的算法。

 

4. 算法复杂度

邻接表：O(V+E)

邻接矩阵：O(V^2)

 该算法在实际操作中要比Tarjan算法要慢

 

5. 算法模板&注释代码

#include "cstdio"
#include "iostream"
#include "algorithm"using namespace std ;const int maxN = 10010 , maxM = 50010;struct Kosaraju { int to , next ; } ;Kosaraju E[ 2 ][ maxM ] ;
bool vis[ maxN ];
int head[ 2 ][ maxN ] , cnt[ 2 ] , ord[maxN] , size[maxN] ,color[ maxN ];int tot , dfs_num  , col_num , N , M  ;void Add_Edge( int x , int y , int _ ){//建图E[ _ ][ ++cnt[ _ ] ].to = y ;E[ _ ][ cnt[ _ ] ].next = head[ _ ][ x ] ;head[ _ ][ x ] = cnt[ _ ] ;
}void DFS_1 ( int x , int _ ){dfs_num ++ ;//发现时间vis[ x ] = true ;for ( int i = head[ _ ][ x ] ; i ; i = E[ _ ][ i ].next ) {int temp = E[ _ ][ i ].to;if(vis[ temp ] == false) DFS_1 ( temp , _ ) ;}ord[(N<<1) + 1 - (++dfs_num) ] = x ;//完成时间加入栈
}void DFS_2 ( int x , int _ ){size[ tot ]++ ;// 强连通分量的大小vis[ x ] = false ;color[ x ] = col_num ;//染色for ( int i=head[ _ ][ x ] ; i ; i = E[ _ ][ i ].next ) {int temp = E[ _ ][ i ].to;if(vis[temp] == true) DFS_2(temp , _);}
}int main ( ){scanf("%d %d" , &N , &M );for ( int i=1 ; i<=M ; ++i ){int _x , _y ;scanf("%d %d" , &_x , &_y ) ;Add_Edge( _x , _y , 0 ) ;//原图的邻接表Add_Edge( _y , _x , 1 ) ;//逆图的邻接表}for ( int i=1 ; i<=N ; ++i )if ( vis[ i ]==false )DFS_1 ( i , 0 ) ;//原图的DFSfor ( int i = 1 ; i<=( N << 1) ; ++i ) {if( ord[ i ]!=0 && vis[ ord[ i ] ] ){tot ++ ; //强连通分量的个数col_num ++ ;//染色的颜色DFS_2 ( ord[ i ] , 1 ) ;}}for ( int i=1 ; i<=tot ; ++i )printf ("%d ",size[ i ]);putchar ('\n');for ( int i=1 ; i<=N ; ++i )printf ("%d ",color[ i ]);return 0;
}

 

https://www.cnblogs.com/shadowland/p/5876307.html

 

 

 

 

 

这篇关于图论 求有向图的所有强连通分量 kosaraju算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---