深入理解C语言拓扑排序（从零开始掌握有向无环图的拓扑排序算法）

拓扑排序的核心思想

拓扑排序常用两种方法实现：

• Kahn算法（基于入度）
• DFS深度优先搜索（基于递归后序遍历）

本文将使用更直观的 Kahn 算法 来实现 C语言拓扑排序。其基本步骤如下：

1. 计算每个节点的入度（即有多少条边指向它）
2. 将所有入度为0的节点加入队列
3. 从队列中取出一个节点，加入结果序列
4. 删除该节点的所有出边，并更新相邻节点的入度
5. 若某个相邻节点入度变为0，则将其加入队列
6. 重复步骤3~5，直到队列为空

C语言实现拓扑排序

下面我们用C语言完整实现这个算法。为了简化，我们使用邻接表存储图，并用数组模拟队列。

#include <stdio.h>#include <stdlib.h>#define MAX_VERTICES 100typedef struct Node {    int vertex;    struct Node* next;} Node;typedef struct Graph {    int numVertices;    Node** adjLists;    int* inDegree;} Graph;Node* createNode(int v) {    Node* newNode = (struct 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;    graph->adjLists = (Node**) malloc(vertices * sizeof(Node*));    graph->inDegree = (int*) calloc(vertices, sizeof(int));    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;    graph->inDegree[dest]++;}void topologicalSort(Graph* graph) {    int queue[MAX_VERTICES];    int front = 0, rear = 0;    int result[MAX_VERTICES];    int index = 0;    // 将所有入度为0的节点入队    for (int i = 0; i < graph->numVertices; i++) {        if (graph->inDegree[i] == 0) {            queue[rear++] = i;        }    }    // Kahn 算法主循环    while (front != rear) {        int current = queue[front++];        result[index++] = current;        Node* temp = graph->adjLists[current];        while (temp) {            int adjVertex = temp->vertex;            graph->inDegree[adjVertex]--;            if (graph->inDegree[adjVertex] == 0) {                queue[rear++] = adjVertex;            }            temp = temp->next;        }    }    // 检查是否所有节点都被处理（判断是否有环）    if (index != graph->numVertices) {        printf("图中存在环，无法进行拓扑排序！\n");    } else {        printf("拓扑排序结果: ");        for (int i = 0; i < index; i++) {            printf("%d ", result[i]);        }        printf("\n");    }}int main() {    Graph* graph = createGraph(6);    // 添加边：表示依赖关系    addEdge(graph, 5, 2);    addEdge(graph, 5, 0);    addEdge(graph, 4, 0);    addEdge(graph, 4, 1);    addEdge(graph, 2, 3);    addEdge(graph, 3, 1);    printf("执行C语言拓扑排序...\n");    topologicalSort(graph);    return 0;}

代码说明

上述代码实现了完整的 C语言拓扑排序 功能：

• createGraph：初始化图结构，包括邻接表和入度数组
• addEdge：添加有向边，并更新目标节点的入度
• topologicalSort：核心算法，使用队列处理入度为0的节点
• 程序最后会检查是否所有节点都被处理，若否，则说明图中存在环

运行此程序，输出可能是：拓扑排序结果: 4 5 2 0 3 1（顺序可能因实现细节略有不同，但都满足依赖关系）。

应用场景与总结

拓扑排序是图论算法中的基础内容，在编译器构建、项目管理、课程规划等领域都有广泛应用。通过本教程，你已经掌握了如何用C语言实现拓扑排序，并理解了其背后的逻辑。

记住关键点：

• 只适用于有向无环图（DAG）
• Kahn算法基于入度，易于理解和实现
• 务必检查是否存在环，避免错误结果

希望这篇关于C语言图论算法的教程对你有所帮助！动手试试修改图的结构，观察不同的拓扑排序结果吧。