用数组表示法对有向图做拓朴排序并输出所有的拓扑有序序列C语言
时间: 2023-12-10 14:40:54 浏览: 40
以下是用数组表示法对有向图做拓扑排序并输出所有的拓扑有序序列的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXV 1000
int G[MAXV][MAXV]; //邻接矩阵表示图
int inDegree[MAXV]; //每个节点的入度
int n; //节点数
void topologicalSort() {
int queue[MAXV], front = -1, rear = -1; //队列
int i, j, k;
for (i = 0; i < n; ++i) { //初始化队列
if (inDegree[i] == 0) {
queue[++rear] = i;
}
}
while (front != rear) { //队列非空
i = queue[++front]; //出队
printf("%d ", i); //输出
for (j = 0; j < n; ++j) { //遍历所有节点
if (G[i][j] != 0) { //i->j存在一条有向边
if (--inDegree[j] == 0) { //入度为0,入队
queue[++rear] = j;
}
}
}
}
}
int main() {
int m; //边数
scanf("%d%d", &n, &m);
int i, j, k;
for (k = 0; k < m; ++k) {
scanf("%d%d", &i, &j);
G[i][j] = 1; //i->j存在一条有向边
inDegree[j]++; //j的入度加1
}
topologicalSort();
return 0;
}
```
其中,G数组表示邻接矩阵,inDegree数组表示每个节点的入度。topologicalSort函数是拓扑排序的实现,它使用队列来遍历所有节点,输出拓扑有序序列。程序读入节点数n、边数m和每条边的起点i和终点j,然后构建邻接矩阵和计算每个节点的入度。最后调用topologicalSort函数进行拓扑排序。