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

非递归的拓扑排序通常是通过使用邻接表（Adjacency List）数据结构来存储有向图，并借助BFS（广度优先搜索）算法来实现的。这里是一个简单的C语言实现示例：

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Graph {
    Node** adj;
    int vertices;
} Graph;

void addEdge(Graph* graph, int src, int dest) {
    graph->adj[src] = (Node*)malloc(sizeof(Node));
    graph->adj[src]->data = dest;
    graph->adj[src]->next = NULL;
}

// 使用邻接列表表示是否有边从src到dest
int isSafe(Graph* graph, int u) {
    for (int i = 0; i < graph->vertices; ++i) {
        if (graph->adj[i] != NULL && graph->adj[i]->data == u)
            return false;
    }
    return true;
}

// 执行BFS并返回拓扑排序结果
void topologicalSortUtil(Graph* graph, int u, int visited[], Stack* stack) {
    visited[u] = 1;
    printf("%d ", u);

    for (Node* node = graph->adj[u]; node != NULL; node = node->next) {
        int v = node->data;
        if (!visited[v])
            topologicalSortUtil(graph, v, visited, stack);
    }

    stackPush(stack, u); // 将节点压入栈
}

// 主函数，驱动非递归拓扑排序过程
void topologicalSort(Graph* graph) {
    int visited[graph->vertices];
    Stack* stack = createStack();

    for (int i = 0; i < graph->vertices; ++i) {
        if (isSafe(graph, i)) {
            topologicalSortUtil(graph, i, visited, stack);
        }
    }

    while (!isEmpty(stack)) {
        printf("%d ", pop(stack));
    }
}

int main() {
    Graph g;
    // 初始化图和添加边...
    int numVertices = 5;
    g.vertices = numVertices;
    g.adj = (Node**)malloc(numVertices * sizeof(Node*));

    // 假设我们有一个完整的邻接表在这里...
    // ...addEdge(g, u, v)...

    topologicalSort(&g);
    return 0;
}