使用C语言实现拓扑排序

拓扑排序是一种对有向无环图（DAG）进行排序的算法，它可以将图中的节点按照依赖关系进行排序，使得所有的依赖关系都得到满足。

在C语言中，可以使用邻接表来表示有向图，并通过深度优先搜索（DFS）来实现拓扑排序。下面是一个使用C语言实现拓扑排序的示例代码：

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

#define MAX_VERTEX 100

// 邻接表节点
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 图结构
typedef struct Graph {
    int numVertices;
    Node* adjLists[MAX_VERTEX];
} Graph;

// 创建节点
Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

// 拓扑排序辅助函数
void topologicalSortUtil(Graph* graph, int v, int visited[], int stack[]) {
    visited[v] = 1;

    Node* temp = graph->adjLists[v];
    while (temp != NULL) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex]) {
            topologicalSortUtil(graph, adjVertex, visited, stack);
        }
        temp = temp->next;
    }

    stack[--stack[0]] = v;
}

// 拓扑排序
void topologicalSort(Graph* graph) {
    int visited[MAX_VERTEX] = {0};
    int stack[MAX_VERTEX + 1] = {0};

    for (int i = 0; i < graph->numVertices; i++) {
        if (!visited[i]) {
            topologicalSortUtil(graph, i, visited, stack);
        }
    }

    printf("拓扑排序结果：");
    for (int i = 0; i < graph->numVertices; i++) {
        printf("%d ", stack[i]);
    }
}

int main() {
    int vertices, edges;
    printf("请输入图的顶点数和边数：");
    scanf("%d %d", &vertices, &edges);

    Graph* graph = createGraph(vertices);

    printf("请输入边的起始点和终点：\n");
    for (int i = 0; i < edges; i++) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    topologicalSort(graph);

    return 0;
}

以上代码实现了一个简单的拓扑排序算法。用户需要输入图的顶点数和边数，然后输入每条边的起始点和终点。程序会输出拓扑排序的结果。