拓扑排序c 算法实现
时间: 2024-06-24 21:01:11 浏览: 33
拓扑排序是一种用来解决有向无环图(DAG)的线性排序算法,它将图中的节点按照依赖关系进行排序,使得对于任何一条有向边 (u, v),都有 u 排在 v 的前面。这个算法在很多地方都有应用,例如软件编译的依赖关系处理。
C 语言实现拓扑排序的方法比较简单,具体步骤如下:
1. 定义邻接表结构体来存储图信息,包括节点个数、入度信息、边信息等;
2. 构建邻接表,即通过输入的节点和边信息建立起有向图;
3. 统计每个节点的入度信息,记录下入度为 0 的节点;
4. 从入度为 0 的节点开始遍历图,每次将入度为 0 的节点加入结果数组,并将与该节点相邻的节点的入度减一;
5. 重复执行步骤 4 直到所有节点都已加入结果数组中或者发现环路。
下面是一个简单的 C 语言实现代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
typedef struct EdgeNode {
int to;
struct EdgeNode *next;
} EdgeNode;
typedef struct Node {
int in_degree;
EdgeNode *head;
} Node;
Node graph[MAXN];
int sorted_nodes[MAXN];
int node_count;
void add_edge(int from, int to) {
EdgeNode *node = malloc(sizeof(EdgeNode));
node->to = to;
node->next = graph[from].head;
graph[from].head = node;
}
void build_graph(int n, int m) {
for (int i = 1; i <= n; i++) {
graph[i].head = NULL;
graph[i].in_degree = 0;
}
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d%d", &a, &b);
add_edge(a, b);
graph[b].in_degree++;
}
}
void top_sort() {
int queue[MAXN], head = 0, tail = -1;
for (int i = 1; i <= node_count; i++) {
if (graph[i].in_degree == 0) {
queue[++tail] = i;
}
}
while (head <= tail) {
int node = queue[head++];
sorted_nodes[node_count++] = node;
for (EdgeNode *p = graph[node].head; p; p = p->next) {
int to = p->to;
graph[to].in_degree--;
if (graph[to].in_degree == 0) {
queue[++tail] = to;
}
}
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
build_graph(n, m);
top_sort();
if (node_count < n) {
printf("Graph contains cycle\n");
} else {
printf("Sorted nodes: ");
for (int i = 0; i < n; i++) {
printf("%d ", sorted_nodes[i]);
}
printf("\n");
}
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)