c语言的设计一个算法,通过拓扑排序的方法判断一个有向图中是否有环,若无环,则输出该拓扑序列代码
时间: 2023-06-02 19:05:34 浏览: 104
有向图的拓扑排序判断是否存在环
5星 · 资源好评率100%
非常感谢您的提问!关于您的问题,我可以给出以下实现代码:
```c
#include <stdio.h>
#define MAX_N 100 //最大节点数
int indegree[MAX_N]; //每个节点的入度
int G[MAX_N][MAX_N]; //有向图的邻接矩阵
int topo[MAX_N]; //存放拓扑序列
int topoSort(int n) //n为节点个数,返回是否有环
{
int i, j, k = 0;
int q[MAX_N], front = 0, rear = -1; //队列
for(i = 0; i < n; i++)
if(indegree[i] == 0) q[++rear] = i; //将入度为0的节点加入队列
while(front <= rear) //队列非空时循环
{
int u = q[front++]; //取出队首节点
topo[k++] = u; //将该节点加入拓扑序列
for(j = 0; j < n; j++) //遍历该节点的所有出边
if(G[u][j]) //如果存在一条出边
if(--indegree[j] == 0) q[++rear] = j; //将该出边对应节点的入度减一
//如果该节点的入度变为0,将其加入队列
}
return k == n; //如果拓扑序列中包含所有节点,说明没有环
}
int main()
{
int n, m, i, u, v; //n为节点数,m为有向边数
scanf("%d%d", &n, &m);
for(i = 0; i < m; i++)
{
scanf("%d%d", &u, &v);
G[u][v] = 1; //有向图中u到v存在一条边
indegree[v]++; //节点v的入度加1
}
if(topoSort(n)) //如果不存在环
{
printf("拓扑序列为:\n");
for(i = 0; i < n; i++)
printf("%d ", topo[i]);
printf("\n");
}
else
{
printf("有向图中存在环!\n");
}
return 0;
}
```
此算法利用了拓扑排序的思想,如果有向图中存在环,那么必然至少有一个节点的入度不为零,无法入队,因此无法输出拓扑序列。如果有向图中不存在环,那么每个节点的入度都可以为零,将它们全部入队,按照入队时的顺序输出,即可得到一个拓扑序列。
阅读全文