用拓扑排序检测有向图中是否有环

  • Post author:
  • Post category:其他



目录


算法主要步骤


代码


测试数据


提示:由于拓扑排序的检测方式不涉及到边权或点权,所以拓扑序列中的正环和负环都能够被检测出来。检测

可达负环

可以用Bellman-Ford或者SPFA。

算法主要步骤

1. 记录每个结点的入度,设置一个队列,专门存放入度为0的结点,设置一个整型计数变量inqNum,记录加入过队列的结点的个数。

2. 首先将所有的入度为0的点放入队列中,进入while循环,条件是队列不为空,对于队列中的每一个点,都对齐后继结点的入度进行减一操作,如果在那之后该后继节点的入度变为0,则将其加入队列。

3. 注意inqNum的维护,不是在将一个结点放入队列时增加,而是在它弹出后、处理了它的所有后继节点后增加,这样只要写一处代码。出了while循环后对inqNum进行判断,如果恰好等于节点个数说明图中没有环,否则说明有环(环上的结点由于永远不会入度为0所以入不了队列)

代码

#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

const int maxn = 1010;

int vNum;
vector<int> G[maxn];
int inDegree[maxn] = {0};//记录每个点的入度 
int inqNum = 0;

bool topoSort(){
	queue<int> Q;
	for(int i=0;i<vNum;i++){
		if(inDegree[i]==0){
			Q.push(i);
		}
	}
	while(!Q.empty()){
		int u = Q.front();
		Q.pop();
		for(int i=0;i<G[u].size();i++){
			int v = G[u][i];
			inDegree[v] --;
			if(inDegree[v]==0){
				Q.push(v);		
			}
		}
		inqNum ++;
	}
	
	if(inqNum==vNum)return true;
	else return false; 
}


int main(){
	int eNum;
	scanf("%d %d",&vNum,&eNum);
	
	int v1,v2;
	while(eNum--){
		scanf("%d %d",&v1,&v2);
		inDegree[v2] ++;//v2不会是起点了 
		G[v1].push_back(v2);
	}
	
	if(topoSort())printf("该拓扑结构不含有环");
	else printf("该拓扑结构含有环"); 
	

	return 0;
}

测试数据

第一行是点的个数(从0开始编号)、边的个数

后面是拓扑序列

#Case 1 无环

8 15
0 1
1 2
3 4
3 7
4 5
7 5
5 6
0 4
3 1
1 4
1 5
2 4
7 2
2 5
2 6

# Case 2 有环

4 5
0 1
1 2
3 0
3 2
2 0



版权声明:本文为weixin_44997802原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。