目录
提示:由于拓扑排序的检测方式不涉及到边权或点权,所以拓扑序列中的正环和负环都能够被检测出来。检测
可达负环
可以用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 版权协议,转载请附上原文出处链接和本声明。