用c语言写拓扑排序
时间: 2023-07-27 08:18:44 浏览: 48
以下是使用C语言实现拓扑排序的示例代码:
```c
#include <stdio.h>
#define MAX 100
int adj[MAX][MAX];
int visited[MAX];
int n, m;
void dfs(int v, int* topo_order, int* index) {
visited[v] = 1;
int i;
for (i = 0; i < n; i++) {
if (adj[v][i] && !visited[i])
dfs(i, topo_order, index);
}
topo_order[--(*index)] = v;
}
void topological_sort(int* topo_order) {
int i, index = n;
for (i = 0; i < n; i++) {
visited[i] = 0;
}
for (i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, topo_order, &index);
}
}
}
int main() {
scanf("%d%d", &n, &m);
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
adj[i][j] = 0;
}
}
for (i = 0; i < m; i++) {
int x, y;
scanf("%d%d", &x, &y);
adj[x][y] = 1;
}
int topo_order[MAX];
topological_sort(topo_order);
for (i = 0; i < n; i++) {
printf("%d ", topo_order[i]);
}
printf("\n");
return 0;
}
```
该代码使用邻接矩阵来表示有向图,并使用深度优先搜索来进行拓扑排序。函数`dfs`用于遍历图中的节点,并将拓扑排序的结果存储在数组`topo_order`中。函数`topological_sort`用于对所有未访问的节点进行深度优先搜索,从而得到整个图的拓扑排序结果。
在`main`函数中,首先读入有向图的节点数`n`和边数`m`,然后读入每条边的起点和终点,并将其存储在邻接矩阵中。最后调用`topological_sort`函数进行拓扑排序,并输出结果。