c语言使用dfs实现拓扑排序代码

在C语言中，使用深度优先搜索（DFS）算法实现拓扑排序通常用于有向无环图（DAG）。这里是一个简单的例子，展示如何通过递归的方式实现：

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

// 声明邻接表结构
typedef struct {
    int* adj; // 存储邻居节点索引
    int size; // 邻居数量
} Graph;

// 用于记录节点是否已经访问过
int visited[100]; // 假设你有最多100个节点

void dfs(int node, Graph* graph) {
    visited[node] = 1;
    printf("%d ", node); // 打印节点值

    // 遍历当前节点的所有未访问邻居
    for (int i = 0; i < graph->size[node]; i++) {
        if (!visited[graph->adj[node][i]]) {
            dfs(graph->adj[node][i], graph); // 递归访问邻居
        }
    }
}

// 拓扑排序函数
void topologicalSort(Graph* graph) {
    int n = sizeof(visited)/sizeof(visited[0]);
    // 对所有节点初始化访问状态
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }

    // 从没有前驱节点的节点开始（即入度为0的节点）
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0 && getDegree(i, graph) == 0) {
            dfs(i, graph);
        }
    }
}

// 获取给定节点的入度
int getDegree(int node, Graph* graph) {
    return graph->size[node];
}

int main() {
    // 初始化并构建你的邻接列表...
    Graph g = { ... };
    topologicalSort(&g);
    return 0;
}

这个代码首先创建了一个邻接表表示图，然后在`topologicalSort`函数中，使用DFS遍历并打印出每个节点（按照拓扑排序顺序），同时维护了`visited`数组来跟踪节点是否已被访问。

请注意，这个代码简化了许多细节，例如假设输入图已经预处理成邻接列表形式。在实际应用中，你需要根据你的数据结构适当地调整代码。