请用c语言编程实现拓扑排序算法
时间: 2023-09-28 12:11:03 浏览: 66
好的,以下是拓扑排序算法的 C 语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 1000
int in_degree[MAX_NODES]; // 每个节点的入度
int graph[MAX_NODES][MAX_NODES]; // 邻接表表示的有向图
int queue[MAX_NODES]; // 拓扑排序队列
int topological_sort(int n) {
int front = 0, rear = -1;
int count = 0; // 已经处理的节点数
// 计算每个节点的入度
for (int i = 0; i < n; i++) {
in_degree[i] = 0;
for (int j = 0; j < n; j++) {
if (graph[j][i]) {
in_degree[i]++;
}
}
}
// 将入度为 0 的节点入队
for (int i = 0; i < n; i++) {
if (in_degree[i] == 0) {
queue[++rear] = i;
}
}
while (front <= rear) {
int node = queue[front++]; // 出队
count++;
// 将所有邻接节点的入度减 1
for (int i = 0; i < n; i++) {
if (graph[node][i]) {
in_degree[i]--;
if (in_degree[i] == 0) { // 入度为 0,入队
queue[++rear] = i;
}
}
}
}
if (count != n) { // 存在环
return -1;
} else { // 拓扑排序成功
return 0;
}
}
int main() {
int n, m; // 节点数和边数
scanf("%d %d", &n, &m);
// 初始化邻接表
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = 0;
}
}
// 读入每条边
for (int i = 0; i < m; i++) {
int u, v; // 边的起点和终点
scanf("%d %d", &u, &v);
graph[u][v] = 1;
}
// 进行拓扑排序
int ret = topological_sort(n);
if (ret == -1) {
printf("存在环\n");
} else {
printf("拓扑排序结果为:");
for (int i = 0; i < n; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
return 0;
}
```
该算法的时间复杂度为 O(|V| + |E|),其中 |V| 和 |E| 分别是图中的节点数和边数。
阅读全文