Kosaraju算法求强连通分量_基于转置图的强连通分支 kosaraju-程序员宅基地

技术标签: dfs  算法  图论  数据结构  

Kosaraju算法

该算法旨在得到深度优先后续排列后的递归探索中,每次调用DFS的所有顶点都属于同一强联通分量。所以可以这么理解:当递归进入一个强联通分量时,把他锁死在这个强联通分量中(即不能从该强联通分量中的任意顶点达到外部顶点)

下面来说说该算法的思路,我认为这是一个十分巧妙的算法,有兴趣的同学可以去看算法导论这本书,我觉得关于这个算法的解释讲的特别好。

该算法的核心思想就是两次DFS遍历,可以先遍历原图再遍历转置图(即所有边都反向的图),也可以先遍历转置图再遍历原图。

下面我们按先遍历原图再遍历转置图来说一说该算法的大致实现流程:

  1. 深度优先遍历原图G(V,E),并记录每个结点遍历结束的时间(将该点的所有子孙结点都遍历完从该点退出的时间即为该点遍历的结束时间,由此可知该结点的结束时间比他的所有子孙节点的结束时间都要晚)
  2. 将该图逆转得到转置图(需要明白的是转置图的强连通分量和原图的强连通分量完全相同,即逆转图不会改变图的强连通分量)
  3. 在转置图上每次取出结束时间最晚且未遍历过的点进行深度优先遍历,并将遍历过的结点标记(下次遍历不再遍历这些被标记过的点),每一次深度优先遍历得到的点即为一个强连通分量。

那么为什么按上述方法的到的为强连通分量呢?且听我慢慢道来:

要理解kosaraju算法,首先得理解拓扑排序,即访问每个强连通分量都得有一个先后顺序,使得每次访问一个强连通分量时,都不能从该强连通分量到达其他强连通分量(即该强连通分量中若有边指向其他强连通分量,则他所指向的强连通分量一定已经被访问过了)

那么如何使得每次访问一个强连通分量时,都不能从该强连通分量中的任意顶点达到外部顶点呢?按上述所说的每次取出遍历结束时间最大的点,在转置图中进行深度优先遍历即可完美解决该问题。

我们实际上是在以拓扑排序的次序来访问分量图中的结点。(分量图:即将每个强连通分量都浓缩成一个结点得到的一个有向无环图,该图中的每一个结点对应原图G的一个强连通分量)

 

(结点的发现时间:即第一次访问到该结点的时间;结点的完成时间:即DFS从该结点退出时的时间,同遍历结束时间的意思相同)

这里的d(C)<d(C')指的是在第一次DFS中强连通分量C中的结点要比C'中的结点先访问(不一定C中的所有结点都比C'要先访问,但是C中一定至少存在一个结点的访问时间要比C'中的所有结点都要早);同理d(C)>d(C')表示C’中的结点要比C中的结点先访问。

根据上述定理可知,将原图逆转后的到的分量图中的边都是由 f 较小的强连通分量指向 f 较大的强连通分量。

这里的E^T是指的转置图的边。

所以当我们每次取出完成时间最晚的那个顶点进行深度优先遍历时,从该顶点所表示的强连通分量的所有出边(即指出该强连通分量的边)所指向的强连通分量一定已经访问(因为他们的 f 要大于该强连通分量的 f ,这即是拓扑排序的一个应用),所以不可能有一条边可以跳出该强连通分量,故DFS被锁死在该强连通分量中,所以该次DFS所访问的点即为该强连通分量中的所有点。

下面是代码:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_SIZE 100
typedef int Elemtype;
typedef struct{
	int vexsnum;
	int arcsnum;
	Elemtype vexs[MAX_SIZE];//结点表 
	int arcs[MAX_SIZE][MAX_SIZE];//临接矩阵 
}Mgraph;//图结构 

void DFS(Mgraph G,int i,int key);//从结点i开始进行深搜
int DFStraving(Mgraph G,int key);//当key为1时,在深搜的同时打印结点 
void creat_graph(Mgraph* G);//创建有向图 
int get_location(Mgraph G,Elemtype v);//找到元素v在结点表中的位置 
void recreat(Mgraph* G);//逆转原图 

bool visited[MAX_SIZE]={false};
int finish[MAX_SIZE]={0};//记录结点访问完成的时间 
int time=0;

int main()
{
	Mgraph G;
	creat_graph(&G);
	int cnt;
	DFStraving(G,0);
	recreat(&G);
	cnt=DFStraving(G,1);
	printf("强连通分量的个数:%d\n",cnt);
	return 0;
} 
 
void DFS(Mgraph G,int i,int key)
{
	visited[i]=true;
	int j;
	if(key==1)
		printf("%d ",G.vexs[i]);
	for(j=0;j<G.vexsnum;j++)
		if(G.arcs[i][j]&&!visited[j])
			DFS(G,j,key);
	if(key==0)
		finish[i]=++time; 
}

int DFStraving(Mgraph G,int key)//第一次调用时key为0,为的是得到finish数组,第二次调用时key为1 
{
	int i,cnt=0;
	if(key==0)
	{
		for(i=0;i<G.vexsnum;i++)
			if(!visited[i])
				DFS(G,i,key);
	}
	else if(key==1)
	{
		printf("强连通分量:\n");
		memset(visited,0,MAX_SIZE*sizeof(bool)); 
		while(1)
		{
			int max=-1;
			for(i=0;i<G.vexsnum;i++)//找出完成时间最大的点 
			{
				if(visited[i]==false&&max==-1)
					max=i;
				if(visited[i]==false&&max!=-1&&finish[max]<finish[i])
					max=i;
			}
			if(max==-1)//所有点都已经被访问 
				break;
			DFS(G,max,key);
			cnt++;
			printf("\n");
		}
	}
	return cnt;
}

void creat_graph(Mgraph* G)
{
	printf("请输入有向图的结点数和边数:");
	scanf("%d%d",&(G->vexsnum),&(G->arcsnum));
	int i;
	memset(G->arcs,0,(MAX_SIZE)*(G->vexsnum)*sizeof(int));//初始化邻接矩阵
	printf("请输入各结点的值:");
	for(i=0;i<G->vexsnum;i++)
		scanf("%d",&(G->vexs[i])); 
	printf("请输入有向边所依附的两结点的值(从结点1指向结点2):");
	Elemtype m,n;
	int x,y;
	for(i=0;i<G->arcsnum;i++)
	{
		scanf("%d%d",&m,&n);
		x=get_location(*G,m);
		y=get_location(*G,n);
		G->arcs[x][y]=1;
	}
	printf("有向图创建完成!\n");
}

int get_location(Mgraph G,Elemtype v)
{
	int i;
	for(i=0;i<G.vexsnum&&G.vexs[i]!=v;i++);
	return i;
}

void recreat(Mgraph* G)
{
	int i,j,e;
	for(i=0;i<G->vexsnum;i++)
		for(j=i;j<G->vexsnum;j++)//这里很细节,不能从j=0开始,否则会有重复,做使边做两次交换,相当于没有对图做逆转 
		{
			if(G->arcs[i][j]!=G->arcs[j][i])
			{
				e=G->arcs[i][j];
				G->arcs[i][j]=G->arcs[j][i];
				G->arcs[j][i]=e;
			}
		}
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_54123999/article/details/116640653

智能推荐

Python字符串的相关操作和方法_2.在python中,设有 s = 'abc',则s.zfill(7)、s.center(7, ' -程序员宅基地

文章浏览阅读464次。Python字符串的相关操作和方法1.什么是字符串(str)容器型数据类型:将’‘或者""或者’’‘或者""""""作为容器标志,引号中的每个符号就是字符串的元素。作为容器标志,引号中每个符号就是字符串的元素。(’’’’’'和"""""""在表示字符串内容的时候换行可以不适用转义字符,而是直接按回车)字符串不可变:不支持增删改,字符串有序(支持下标操作)字符串对元素的要求:引号中单独的每个符号都是字符串的元素(又叫字符),字符可以任何符号。字符串分为两类:普通字符(表示符号本身字符),转义字符(_2.在python中,设有 s = 'abc',则s.zfill(7)、s.center(7, ' ')、s.ljust(7)、s.rj

C++报错:error: return type specification for constructor invalid-程序员宅基地

文章浏览阅读6.1k次,点赞8次,收藏6次。类的构造函数不需要返回类型,即将void orbclass();前面的void去掉即可。_return type specification for

librosa的安装_conda安装liborsa指定源-程序员宅基地

文章浏览阅读4.8k次。在很多设计到语音识别合成等方面的项目里经常用到python的一个包librosa但是这个包直接用pip安装容易出现GCC的CXXABI一些各种各样的问题推荐使用conda安装但是conda的源在国外下面这个是conda换源的命令其中 https://example.com 可以随意更换底部的源conda config --add channels https://e_conda安装liborsa指定源

神器!这个Python神器竟能把图片视频无损清晰放大N倍!-程序员宅基地

文章浏览阅读1k次。文 |闲欢来源:Python 技术「ID: pythonall」最近在浏览 GitHub 的时候,偶然发现了一个非常牛逼的开源库,利用机器学习算法竟然把图片无损放大 N 倍,简直逆天!这个库叫做 video2x,目前有 4300+ 颗星星,是基于 waifu2x,Anime4K,SRMD 和 RealSR 开发的工具,不仅支持视频无损放大,还可以支持图片和 GIF 动画..._video2x源码怎么用

POJ1733 Parity game(并查集模型+带权并查集+离散化)_partiy game poj1733-程序员宅基地

文章浏览阅读357次。题意:有一个长度已知的01串,给出[l,r]这个区间中的1是奇数个还是偶数个,给出一系列语句问前几个是正确的思路:一类经典的并查集题目,经典模型就是将[l,r]这个区间化为(l-1,r],那么1的个数就可以表示为sum[r]-sum[l-1],也就确定了奇偶性,我们可以用r[]数组表示这个端点到它的根节点的1的奇偶(这个区间就是(i,root(i)](0代表偶,1代表奇_partiy game poj1733

华为畅享9 plus鸿蒙,华为畅享9 Plus 与OPPO A3之间的较量 实力差距一目了然-程序员宅基地

文章浏览阅读611次。在游戏性能方面怎样呢?笔者通过热门游戏王者荣耀对两款产品的帧数浮动和温度进行了分别测试。华为畅享9 Plus使用下来的帧率变化为55-60帧,游戏时表现的机身温度是33.5℃。OPPO A3使用下来帧率变化为55-58帧,游戏时的温度表现是34.2℃。两者虽然都没有在游戏过程中出现太频繁的卡顿,但整个体验而言,华为畅享9 Plus的流畅性好更好些,画面的连续性输出效果不错,而且温度控制的也在可接受..._华为畅享9plus和oppoa3哪个好

随便推点

harmonyos2.0手机上手,上手体验如何?华为鸿蒙OS 2.0测试版推送-程序员宅基地

文章浏览阅读210次。原标题:上手体验如何?华为鸿蒙OS 2.0测试版推送前不久,华为开启了新一轮的鸿蒙手机系统测试招募,花粉俱乐部里有不少网友都获得了测试机会。在公测招募的帖子上方,有提到华为将于2021年04月27日的22:00-24:00,对当前支持OTA升级的手机推送华为HarmonyOS 2.0开发者Beta版。目前,已经有不少用户收到了华为HarmonyOS的推送,开发者版本的公测正式开启。而且根据各个机型..._手机harmonyos怎么玩

HTML表格标签和列表标签20200424_静态网页表格有几个标签-程序员宅基地

文章浏览阅读139次。表格标签基本语法 <table> <tr> <td>单元格1</td> <td>单元格2</td> </tr> <tr> <td>单元格3</td>..._静态网页表格有几个标签

变量向导添加控件变量Control类别和Value类别差别_control和value类型区别-程序员宅基地

文章浏览阅读526次。Control类别:控件的实例 Value类别:与控件绑定的值每个控件最多只能有一个Value型和一个Control型的成员变量,前者代表着控件的值,而后者代表着控件本身如果只想设置或获取控件内部存储的值,选择添加一个Value型的变量;如果想在运行时对控件的各种属性进行控制,那么选择添加一个Control型的变量。常见的Value型变量有int、UINT、long、DWORD、float、double、BYTE、short、BOOL、CString、CTime、COleDateTime和C.._control和value类型区别

RSA 原理与 python 实现_rsa 的python代码-程序员宅基地

文章浏览阅读1.5k次,点赞5次,收藏4次。原理摘自:http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html如果看不懂或者对此没有需求的同学可以直接翻到底查看 python 实现一、基础数论1、互质关系如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,15和32没有公因子,所以它们是互质关系。这说明,不是质数也可以构成..._rsa 的python代码

Android Jetpack ViewModel 的使用_viewmodel 延迟初始化-程序员宅基地

文章浏览阅读156次。官网镇楼 ViewModel 概览 | Android 开发者 | Android Developershttps://developer.android.google.cn/topic/libraries/architecture/viewmodel?hl=zh_cn#kotlinViewModel 类旨在以注重生命周期的方式存储和管理界面相关的数据。ViewModel 类让数据可在发生屏幕旋转等配置更改后继续留存。ViewModel 是用于管理数据的,界面上的数据,都应该放到 ViewM_viewmodel 延迟初始化

C++ error-程序员宅基地

文章浏览阅读1k次。文章目录变量重命名变量重命名countalgorithm库和std命名空间indexcstring/string.h库和std命名空间_c++ error

推荐文章

热门文章

相关标签