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

拓扑排序的应用场景

• 项目管理中的任务调度（如Makefile编译依赖）
• 课程先修关系（如“数据结构”需在“算法设计”之前学习）
• 软件包安装依赖解析
• 指令流水线优化

实现拓扑排序的两种方法

常见的实现方式有两种：基于深度优先搜索（DFS）和基于入度（Kahn算法）。本文将重点讲解更直观、更适合初学者的 Kahn 算法。

Kahn 算法原理

1. 计算图中每个顶点的入度（即有多少条边指向它）。
2. 将所有入度为 0 的顶点加入队列。
3. 从队列中取出一个顶点，将其加入拓扑序列，并移除它发出的所有边（即减少其邻居的入度）。
4. 若某个邻居的入度变为 0，则将其加入队列。
5. 重复上述过程，直到队列为空。
6. 如果最终拓扑序列中的顶点数等于图的总顶点数，则排序成功；否则说明图中存在环，无法进行拓扑排序。

C语言实现拓扑排序

下面是一个完整的 C 语言实现，使用邻接表表示图，并通过队列实现 Kahn 算法：

#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 = malloc(sizeof(Node));    newNode->vertex = v;    newNode->next = NULL;    return newNode;}// 初始化图Graph* createGraph(int vertices) {    Graph* graph = malloc(sizeof(Graph));    graph->numVertices = vertices;    graph->adjLists = malloc(vertices * sizeof(Node*));    graph->inDegree = 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 = malloc(graph->numVertices * sizeof(int));    int front = 0, rear = 0;    int* topoOrder = malloc(graph->numVertices * sizeof(int));    int index = 0;    // 将所有入度为0的顶点入队    for (int i = 0; i < graph->numVertices; i++) {        if (graph->inDegree[i] == 0) {            queue[rear++] = i;        }    }    while (front < rear) {        int current = queue[front++];        topoOrder[index++] = current;        Node* temp = graph->adjLists[current];        while (temp) {            int neighbor = temp->vertex;            graph->inDegree[neighbor]--;            if (graph->inDegree[neighbor] == 0) {                queue[rear++] = neighbor;            }            temp = temp->next;        }    }    if (index != graph->numVertices) {        printf("图中存在环，无法进行拓扑排序！\n");    } else {        printf("拓扑排序结果: ");        for (int i = 0; i < index; i++) {            printf("%d ", topoOrder[i]);        }        printf("\n");    }    free(queue);    free(topoOrder);}// 主函数测试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);    topologicalSort(graph);    return 0;}

代码说明

- 我们用邻接表存储图结构，同时维护一个 inDegree 数组记录每个顶点的入度。

- 在 topologicalSort 函数中，使用一个简单数组模拟队列（也可用链式队列）。

- 如果最终输出的顶点数量不等于总顶点数，说明图中存在环，此时有向无环图拓扑排序无法完成。

总结

通过本教程，你已经掌握了 C语言图论算法 中的拓扑排序实现方法。它不仅能帮助你解决实际工程中的依赖问题，也是面试中常见的算法题型。建议你动手敲一遍代码，加深理解。

记住：拓扑排序只适用于有向无环图（DAG），如果图中存在环，则不存在合法的拓扑序列。

希望这篇教程对你有所帮助！如果你喜欢，请分享给更多正在学习 C语言拓扑排序 的朋友。