Kosaraju（科萨拉朱）求强连通分量 （-8-5）

kosaraju 强连通分量

强连通图：任意俩点之间均可达

以下总结均为视频笔记：视频地址

结论：

（1）无向图：

共执行几次dfs遍历完全图，就是几个连通分量

（2）有向图：

1.对原图G1进行dfs，记录顶点

2.每次选择栈顶的顶点（出栈），对反图G2进行dfs，标记能够遍历的顶点，这些顶点构成一个强连通分量

3.如果还有顶点没有标记，继续step2，否则算法结束

原理：

1.反图与原图的强连通分量是相同的

2.若原图能从分量1走到分量2，则反图不能从分量1走到分量2

图：（1）原图 （2）反图

（转载视频图）

原图：

（1)从1为起点，后序遍历结果为：

3 2 6 7 9 8 5 4 1

反图：

（2）强连通分量1：1 3 2

强连通分量2：4 6 7 5

强连通分量3：8 9

代码：（邻接表+dfs）

#include<iostream>#include<string.h>using namespace std;int A1[99][99],A2[99][99];//邻接点int vis1[99],vis2[99];//访问标记 int num,set[99]; //对应连通分量，计数器 int index,stack[99];//栈 （后序） ,下标 void dfs1(int s){//深搜原图 int v; for(int i=1;i<=A1[s][0];i++){//A1[s][0]:s点的邻接点个数 v=A1[s][i];if(!vis1[v]){vis1[v]=1;dfs1(v);}} stack[++index]=s; //后序入栈 printf("%d ",s);//输出后序序列 }void dfs2(int s,int num){//深搜反图 set[s]=num;//set下标存连通分量顶点 int v;for(int i=1;i<=A2[s][0];i++){v=A2[s][i];if(!vis2[v]){vis2[v]=1;dfs2(v,num);}}} int main(){memset(vis1,0,sizeof(vis1));memset(vis2,0,sizeof(vis2)); int E[15][3]={{1,2},{2,3},{3,1},{1,4},{4,5},{5,6},{5,7},{7,6},{6,4},{5,8},{8,9},{9,8}};//存图的边int m=12,n=9;//9个顶点 12条边 int a,b; for(int i=0;i<m;i++){//***妙啊！！！ a=E[i][0],b=E[i][1];A1[a][++A1[a][0]]=b;//存原图 A1[a][0]相当于下标,同时记录此点有几个邻接点 A2[b][++A2[b][0]]=a;//存反图 } index=0; //下标初始化0 num=0;//连通分量个数 int tmp;for(int i=1;i<=n;i++){if(!vis1[i]){vis1[i]=1;//标记dfs1(i);//深搜原图 }}while(index){tmp=stack[index--];//出栈if(!vis2[tmp]){vis2[tmp]=1;//标记 dfs2(tmp,++num);//深搜反图 } }for(int i=1;i<=num;i++){printf("\n强连通分量：%d: ",i);for(int j=1;j<=n;j++){if(set[j]==i){printf("%d ",j);}}}return 0;}

如果觉得《Kosaraju（科萨拉朱）求强连通分量 （-8-5）》对你有帮助，请点赞、收藏，并留下你的观点哦！