C语言设计一个算法,通过拓扑排序的方法判断一个有向图中是否有环,若无环,则输出该拓扑序列。的代码
时间: 2023-06-03 19:02:27 浏览: 61
以下是 C语言设计的算法,通过拓扑排序的方法判断一个有向图中是否有环,若无环,则输出该拓扑序列的代码:
```
#include<stdio.h>
#define MAXV 1000
int V, E; // V表示有向图中节点的数量,E表示有向边的数量
int G[MAXV][MAXV]; // G表示邻接矩阵,表示有向图中的有向边关系
int indeg[MAXV]; // 表示节点的入度
int topsort[MAXV]; // 用于存储排序结果的数组
int toph = -1; // 用于记录排序结果数组的头指针
// 拓扑排序函数
int topsort(){
int i; // 用于循环计数
int j; //用于循环计数
int k = 0; //用于记录节点的数量
int indeg[MAXV]; //用于记录节点的入度
for (i = 0; i < V; i++){
indeg[i] = 0; //1. 初始化入度
}
for (i = 0; i < V; i++){ //2. 记录每个节点的入度
for (j = 0; j < V; j++){
if (G[i][j] != 0){
indeg[j]++;
}
}
}
//3. 将入度为0的节点依次入队
for (i = 0; i < V; i++){
if (indeg[i] == 0){
tops[++toph] = i;
}
}
while (toph != -1){
int u = tops[toph--];
topsort[k++] = u; // 4. 把u加入拓扑序列中
for (i = 0; i < V; i++){
if (G[u][i] != 0){
indeg[i]--; //5. 更新节点i的入度
if (indeg[i] == 0){
tops[++toph] = i; //6. 若节点i的入度为0,则入队
}
}
}
}
if (k != V){
return 0; //7. 若排序后节点数量小于V,则说明存在环,返回假
}
else{
return 1; //8. 否则返回真
}
}
int main(){
scanf("%d %d", &V, &E); //读入节点数量和边数量
for (int i = 0; i < E; i++){ //读入有向边的信息,并将有向边插入邻接矩阵中
int u, v;
scanf("%d %d", &u, &v);
G[u][v] = 1;
}
if (topsort()){ //如果有拓扑序列
for (int i = 0; i < V; i++){
printf("%d ", topsort[i]);
}
}
else{
printf("存在环");
}
return 0;
}
```
注意:本算法没有考虑图中存在多个拓扑排序的情况。