用C语言编程实现图的拓扑排序

在C语言中实现图的拓扑排序，通常会采用深度优先搜索（DFS）或广度优先搜索（BFS）算法。这里我会简述使用DFS的方法，因为DFS更适合于有向无环图（DAG），这是拓扑排序的前提条件。

首先，我们需要创建一个邻接表来存储图的结构，每个节点包含指向其出边相邻节点的指针。然后按照以下步骤：

1. 初始化：标记所有节点为未访问（通常用一个布尔数组表示）。
2. 遍历图：从任意一个入度为0的节点开始（即无前驱节点），将其加入结果序列，并将对应的节点标记为已访问。
3. 对剩余节点进行递归处理：对于当前节点的所有邻居，如果它们还没有被访问过，继续进行下一层的遍历。
4. 重复步骤2和3，直到所有的节点都被访问过或者无法找到新的入度为0的节点。

如果在整个过程中所有节点都能被正确处理并加入序列，那么得到的就是图的一个合法拓扑排序；如果在某个时刻找不到入度为0的节点，说明图存在环，这意味着该图不是强连通图，无法进行拓扑排序。

#include <stdbool.h>
#include <stdio.h>

// 图节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 拓扑排序函数
void topologicalSort(Node** head, int n) {
    bool visited[n];
    int indegree[n]; // 记录每个节点的入度
    for (int i = 0; i < n; i++) {
        visited[i] = indegree[i] = 0;
    }

    // 初始化邻接表
    // ...

    // 遍历图，计算入度
    for (int u = 0; u < n; u++) {
        if (head[u]) {
            for (Node* v = head[u]; v != NULL; v = v->next) {
                indegree[v->data]++;
            }
        }
    }

    // 深度优先搜索
    stack<int> s;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            s.push(i);
        }
    }

    while (!s.empty()) {
        int u = s.top();
        printf("%d ", u); // 输出节点数据
        s.pop();

        Node* temp = head[u];
        while (temp != NULL) {
            int v = temp->data;
            indegree[v]--;
            if (indegree[v] == 0)
                s.push(v);
            temp = temp->next;
        }
    }
}

// 主函数演示
int main() {
    // 创建图节点和邻接表
    Node** graph = createAdjacencyList(); // 假设这个函数已经定义

    int nodes = sizeof(graph) / sizeof(graph[0]);
    topologicalSort(graph, nodes);

    return 0;
}