c语言拓扑排序代码实现

在C语言中实现拓扑排序通常涉及到图论的知识，拓扑排序是对有向无环图(DAG)中顶点进行排序的一种方法，它的结果保证了所有依赖关系正确的顺序。下面是一个简单的使用邻接表表示有向图并进行拓扑排序的示例：

#include <stdio.h>
#include <stdlib.h>

// 定义节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 添加边到图
void add_edge(Node** graph, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = dest;
    newNode->next = (*graph)[src];
    (*graph)[src] = newNode;
}

// 检查是否为根节点
int is_root(Node** graph, int node) {
    return !(*graph[node]);
}

// 找出邻居
int get_neighbors(Node** graph, int node) {
    Node* temp = *graph[node];
    int count = 0;
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count;
}

// 边数小于等于节点数的递归实现
void topological_sortUtil(Node** graph, int v, int visited[], stack_t* s, int n) {
    if (visited[v] == true)
        return;

    visited[v] = true;

    printf("%d ", v);

    for (int i = 0; i < n; i++) {
        if ((*graph)[v] != NULL && visited[i] == false && is_root(graph, i)) {
            topological_sortUtil(graph, i, visited, s, n);
        }
    }

    // push the current vertex to stack before visiting its neighbors
    push(s, v);
}

// 主函数
void topological_sort(Node** graph, int nodes) {
    stack_t* s = create_stack();
    int visited[nodes];

    // 初始化已访问数组
    for (int i = 0; i < nodes; i++)
        visited[i] = false;

    for (int i = 0; i < nodes; i++) {
        if (is_root(graph, i))
            topological_sortUtil(graph, i, visited, s, nodes);
    }

    // 如果存在环，则无法进行拓扑排序，所以此处会出错
    if (!isEmpty(s)) {
        printf("Graph has a cycle\n");
        destroy_stack(s);
        return;
    }

    printf("\nTopological Sort of given graph:\n");
    print_postorder(s);
    destroy_stack(s);
}

// 测试代码
int main() {
    int vertices[] = {5, 4, 3, 2, 1};
    Node** graph = (Node**)malloc(sizeof(Node*) * 6); // 创建一个大小为6的动态邻接表

    // 添加边
    add_edge(&graph[0], 1, 2);
    add_edge(&graph[0], 2, 3);
    add_edge(&graph[0], 3, 4);
    add_edge(&graph[1], 4, 5);

    int n = sizeof(vertices) / sizeof(vertices[0]);
    topological_sort(graph, n);

    return 0;
}

在这个例子中，我们首先创建了一个邻接表来存储图，然后通过递归的topological_sortUtil函数进行拓扑排序。如果检测到环，则说明图不是有向无环图，无法进行拓扑排序。