C语言，用深度优先算法实现拓扑排序

C语言中，使用深度优先搜索（Depth-First Search，DFS）算法实现拓扑排序通常用于处理有向无环图（DAG，Directed Acyclic Graph）。拓扑排序是一种将图中的顶点按照某种线性顺序排列的方式，使得对于每条有向边 (u, v)，节点 u 总是在节点 v 的前面。

以下是使用递归实现的简单示例：

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

// 用于记录邻接表
typedef struct AdjacencyList {
    int vertex;
    struct AdjacencyList* next;
} Node;

void addEdge(Node** list, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = *list;
    *list = newNode;
}

bool isVisited(int node, Node** adjList, int n) {
    for (Node* current = *adjList; current != NULL; current = current->next) {
        if (current->vertex == node && !current->visited)
            return false;
    }
    return true;
}

void DFSUtil(Node** adjList, int node, int visited[], int n) {
    visited[node] = 1;
    printf("%d ", node);

    Node* temp = adjList[node];
    while (temp != NULL) {
        if (!visited[temp->vertex]) {
            DFSUtil(adjList, temp->vertex, visited, n);
        }
        temp = temp->next;
    }
}

void DFS(Node** adjList, int n) {
    int visited[n + 1]; // 初始化所有顶点为未访问
    for (int i = 0; i <= n; i++) {
        if (isVisited(i, adjList, n)) {
            DFSUtil(adjList, i, visited, n);
        }
    }
}

int main() {
    int n, edges;
    printf("Enter number of vertices: ");
    scanf("%d", &n);
    printf("Enter number of edges: ");
    scanf("%d", &edges);

    // 创建邻接列表
    Node** adjList = (Node**)malloc(n * sizeof(Node*));
    for (int i = 0; i < n; i++) {
        adjList[i] = NULL;
    }

    printf("Enter the edges:\n");
    for (int i = 0; i < edges; i++) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(&adjList[src], dest, src);  // 由于拓扑排序需要先入后出，这里交换源和目标
    }

    printf("Topological sorting: ");
    DFS(adjList, n);
    printf("\n");

    return 0;
}

这段代码首先创建了一个邻接列表表示图结构，然后通过DFS遍历每个顶点并标记已访问过的节点。只有当一个节点的所有相邻节点都被访问过，才会将其添加到结果序列中。最后输出拓扑排序的结果。