请用c语言编程实现拓扑排序算法
时间: 2023-09-28 07:11:03 浏览: 76
好的,以下是用C语言编写的拓扑排序算法示例:
```c
#include <stdio.h>
#define MAXN 10000
int n, m, cnt;
int head[MAXN], indeg[MAXN], to[MAXN], nxt[MAXN];
void addEdge(int u, int v) {
to[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
indeg[v]++;
}
void topoSort() {
int q[MAXN], front = 0, rear = -1;
for (int i = 1; i <= n; i++)
if (indeg[i] == 0)
q[++rear] = i;
while (front <= rear) {
int u = q[front++];
printf("%d ", u);
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (--indeg[v] == 0)
q[++rear] = v;
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
}
topoSort();
return 0;
}
```
在该程序中,我们使用邻接表来存储图,使用indeg数组来存储每个节点的入度。在拓扑排序算法中,我们首先将所有入度为0的节点加入队列中,然后不断地从队列中取出元素,并将其邻接节点的入度减1。当邻接节点的入度为0时,将其加入队列中。最终,当队列为空时,所有节点就已经按照拓扑序排列好了。
阅读全文