c语言递归实现拓扑排序的代码

在C语言中，递归可以用来实现拓扑排序（Topological Sort），它主要用于有向无环图（DAG，Directed Acyclic Graph）。下面是一个简单的示例，展示了如何使用广度优先搜索（BFS）结合递归来实现拓扑排序：

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

// 定义邻接表结构
typedef struct {
    int num;
    struct Node *adj[100];
} graph;

// 辅助函数，用于检查是否所有的节点都有前驱
int hasAllPredecessors(graph *g) {
    int visited[100] = {0}; // 记录已访问节点
    for (int i = 0; i < g->num; i++) {
        if (!visited[i] && !hasNoIncomingEdges(g, i)) {
            return 0; // 如果找到一个直接有入边的节点，说明图中存在环，无法拓扑排序
        }
    }
    return 1; // 所有节点都没有直接入边，表示不存在环，可以继续拓扑排序
}

// 检查某个节点是否有出边
int hasNoIncomingEdges(graph *g, int node) {
    for (int i = 0; i < g->adj[node]->num; i++) {
        if (g->adj[node]->adj[i]) return 0; // 发现出边则返回false
    }
    return 1;
}

// 主函数
void topologicalSort(graph *g) {
    if (!hasAllPredecessors(g)) {
        printf("拓扑排序失败，图中存在环\n");
        return;
    }

    int stack[100], top = -1;
    int visited[100];

    // 使用栈辅助BFS
    for (int i = 0; i < g->num; i++) {
        if (!visited[i] && hasNoIncomingEdges(g, i)) {
            stack[++top] = i;
        }
    }

    while (top >= 0) {
        int vertex = stack[top--]; // 弹出最后一个入队的节点
        printf("%d ", vertex); // 输出节点

        // 标记已经访问过，并将它的所有邻居加入队列
        visited[vertex] = 1;
        for (int i = 0; i < g->adj[vertex]->num; i++) {
            int neighbor = g->adj[vertex]->adj[i];
            if (!visited[neighbor]) {
                stack[++top] = neighbor;
            }
        }
    }
}

int main() {
    // 初始化并构建图的邻接表...
    graph myGraph;
    // ...这里填写实际的邻接表构建代码
    topologicalSort(&myGraph);
    return 0;
}

这个代码首先检查图是否存在环，然后使用BFS对图进行遍历，按照拓扑顺序输出节点。注意，这个例子假设你已经有了一个实现了邻接表结构的`graph`结构体，并且需要自己填充构建邻接表的部分。