C语言实现Kahn算法：拓扑排序原理与实战解析

这周在帮一个朋友调一个课程选课系统的排课模块时，又碰上了拓扑排序。说实话，这个算法在学校里学的时候觉得挺简单，无非就是“不断找入度为0的节点”，可真到了项目里自己动手实现，才发现细节远比课本上写的要多。

尤其是用C语言从头写一遍Kahn算法的时候，图的存储结构怎么选、队列怎么维护、入度数组怎么更新、环检测怎么做，每一步都藏着坑。所以我想趁这次实战，把Kahn算法从头到尾拆一遍，包括算法原理、完整C语言实现、常见误区，以及和另一种DFS拓扑排序方案的选型对比。如果你是刚学图论的学生，或者工作中要处理依赖关系（比如任务调度、编译顺序、包管理器）的开发者，这篇文章应该能帮你省不少事。

1. 从实际场景认识拓扑排序

1.1 拓扑排序到底在解决什么问题

先抛一个最经典的例子：大学选课。假设你要修完《数据结构》才能学《算法设计》，而《算法设计》又是《机器学习》的先修课，这时候你手头有十几门课，怎么排出一个合理的学习顺序？

这类问题的本质是：在一组存在先后依赖关系的任务中，找出一个可行的执行顺序。用图论的术语讲，每门课是一个节点，先修关系是一条有向边，整个依赖关系就构成了一张有向图。拓扑排序要做的，就是把这张图的所有节点排成一列，使得对于每一条有向边 A→B，节点 A 都排在节点 B 前面。

听起来很抽象？其实你每天都在用它。写代码时编译器需要先编译被依赖的模块；安装软件时依赖包要优先安装；数据库里先有父表数据才能插入子表记录；甚至你做饭时“先烧水再煮面”这个朴素的先后顺序，本质上也是一次手工拓扑排序。

1.2 什么样的图才能做拓扑排序

这是第一个必须搞清楚的前提：不是所有图都能拓扑排序。只有有向无环图，也就是通常说的 DAG（Directed Acyclic Graph），才存在拓扑排序结果。

道理很简单：如果图中存在环，比如 A→B→C→A，那么这三个任务互为前置条件，A 做完才能做 B，B 做完才能做 C，C 做完才能做 A，等于永远等不到开始的那一天。在工程里，这就意味着你的依赖关系定义错了，必须回去检查配置。

这里顺带提一句，拓扑排序的结果不唯一。同一张 DAG 往往有多个合法的拓扑序列，具体输出哪一个，取决于你处理“入度为 0 的节点”时的顺序。这一点在面试里也是高频考点，后面我会专门展开。

1.3 为什么单独讲 Kahn 算法

图论里实现拓扑排序有两条经典路线：Kahn 算法（基于入度）和基于 DFS 的逆后序法。我自己在项目里绝大多数时间都在用 Kahn 算法，原因有三个：

第一，Kahn 算法的思路和依赖问题的直觉完全一致——“先做没有前置条件的任务，做完一批后释放新的没有前置条件的任务”这个逻辑，几乎不需要看图论知识就能理解，和产品经理对话时也能讲得清楚。

第二，Kahn 算法天然支持在线处理。每弹出一个节点，你知道它已经可以执行了，可以直接丢给下游任务调度器，不用等全部拓扑序列生成完毕。这对做任务流水线来说非常友好。

第三，Kahn 算法做环检测非常直观。只要最后统计一下输出的节点数是否等于总节点数，就知道图里有没有环，代码写起来几乎不增加额外负担。

2. Kahn 算法核心原理

2.1 入度驱动的核心思想

要理解 Kahn 算法，首先要理解“入度”这个概念。一个节点的入度，就是有多少条有向边指向它。白话讲就是：“它依赖多少个前置任务”。

在 DAG 里，一定至少存在一个入度为 0 的节点（否则就无法定义起点）。Kahn 算法的核心思路就是用 BFS 式的扩散逻辑，不断把“当前已经没有前置依赖”的节点拿出来，放到拓扑序列里，同时“解除”它对后续节点的依赖关系——具体做法就是把所有从它出发的边都删掉，相当于让后继节点的入度减 1。

你可以把它想象成一层层剥洋葱：先剥掉最外层不需要依赖任何人的节点，剥完之后，原本被它们挡住的内层节点就暴露出来，继续剥。直到所有节点都被剥完，或者发现剥不动了（剩下的节点入度都大于 0，说明有环）。

2.2 算法完整流程拆解

Kahn 算法的标准流程可以拆成四个步骤：

第一步，初始化入度数组。遍历所有边，统计每个节点的入度。这里有图的表示方式决定，用邻接表的话就在建表边时同步统计入度。

第二步，将所有入度为 0 的节点入队。这里用的是队列还是栈，或者优先队列，会影响最终输出的拓扑序，但不影响算法的正确性。想在依赖同级时按字典序输出，就用优先队列；无特殊要求用普通队列就行。

第三步，循环取出队首节点。每取出一个节点，先把它加入拓扑序列，然后遍历这个节点的所有邻接节点，把它们的入度减 1。如果某个邻接节点的入度减到 0，说明它的所有前置任务都已完成，可以入队了。

第四步，判环。循环结束后，如果拓扑序列里的节点数等于图的总节点数，说明排序成功；如果少于总节点数，说明有环存在，剩下的那些节点是环上或者被环依赖的节点。

2.3 正确性证明与复杂度分析

为什么这个流程是正确的？关键点在于一个朴素但严谨的观察：在 DAG 中，当算法取出一个节点 u 时，所有指向 u 的节点 v 都已经被加入拓扑序列了。为什么？因为只有当 v 被取出时，u 的入度才会减 1；u 能入队，说明它的入度已经被减到 0——也就是说它的所有“入边来源”都已经先于它出队了。

把这个逻辑推广到所有节点，最终得到的序列里，任何一条边 A→B，A 都必然在 B 之前。所以只要队列不空且节点总数相等，这个序列就是一个合法的拓扑排序。

复杂度方面，设图有 V 个节点、E 条边。初始化入度数组需要扫描全部边，O(E)。每个节点最多入队、出队一次，O(V)。每处理一个节点时，需要遍历它的所有出边，所有节点的出边总和正好是所有边数，O(E)。所以总时间复杂度是O(V + E)，这是一个彻底遍历图的最优复杂度，没有多余开销。空间上需要入度数组、队列和邻接表，合计 O(V + E)。

2.4 环检测与边界情况

刚刚提到，如果最后输出的节点数小于 V，则说明有环。这里有一个容易被忽略的细节：被“卡住”的节点数量并不等于环上的节点数量。因为环上的节点入度永远不可能减到 0，而所有被环上的节点依赖、或者被环间接依赖的节点，也会因为没有前置被释放而停留在原地。所以不能通过剩余节点栈去反推环的具体组成，只能确定“有环”。

如果你想进一步定位环在哪里，需要借助 DFS 的白灰黑染色法，或者说在 Kahn 算法结束后，对剩余节点再做一次环追踪。这是个扩展话题，但面试时如果被问到“Kahn 算法怎么找环”，能答到这里就已经领先很多人了。

3. C 语言实现与逐行解读

3.1 数据结构选型

既然热词里专门提到“拓扑排序 c语言”，我就直接上 C 语言完整实现，顺便讲讲为什么要这样设计数据结构。

C 语言实现图的结构，最朴素的两个选择是邻接矩阵和邻接表。邻接矩阵的好处是查询任意两点之间是否有边是 O(1)，但在 V 较大时空间开销是 O(V²)，对稀疏图极不友好。Kahn 算法的主要操作是“遍历某个节点的所有邻接节点”，邻接表在这件事上的效率要高得多，所以工程上几乎都用邻接表。

我这里的邻接表用“数组 + 头插法”实现，每个节点维护一个边节点链表。为什么用头插法而不是尾插法？因为头插法时间复杂度 O(1)，尾插法如果每次都要遍历到尾部就退化了。不过要注意，头插法会让邻接表的遍历顺序恰好和输入顺序相反，对拓扑排序的输出顺序会有影响，但不影响正确性。想要稳定地按输入顺序遍历，就额外维护一个 tail 指针。

3.2 邻接表与入度数组实现

先定义图的结构体和边节点：

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_NODES 100 // 边节点：存储目标顶点编号 + 指向下一条边的指针 typedef struct EdgeNode { int adjvex; struct EdgeNode *next; } EdgeNode; // 顶点节点：存储顶点数据 + 指向第一条边 typedef struct VertexNode { int data; int indegree; // 入度 EdgeNode *firstedge; // 邻接表头 } VertexNode; // 图结构：顶点数组 + 顶点数 + 边数 typedef struct { VertexNode adjlist[MAX_NODES]; int numNodes; int numEdges; } Graph;

这里我把入度直接存在顶点节点里，而不是单独定义一个 indegree 数组。这样在建图过程中，只要加一条边，就能立刻更新目标节点的入度，逻辑更集中，写起来也更不容易漏。后续 Kahn 算法里直接访问graph.adjlist[i].indegree即可。

接着是建图函数。假设输入数据是若干条from to形式的边，表示 from 必须排在 to 前面。

void createGraph(Graph *g) { printf("请输入顶点数和边数："); scanf("%d %d", &g->numNodes, &g->numEdges); for (int i = 0; i < g->numNodes; i++) { g->adjlist[i].data = i; g->adjlist[i].indegree = 0; g->adjlist[i].firstedge = NULL; } printf("请输入每条边（格式：起始顶点的编号 终止顶点的编号）：\n"); for (int i = 0; i < g->numEdges; i++) { int from, to; scanf("%d %d", &from, &to); // 头插法创建边节点 EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode)); e->adjvex = to; e->next = g->adjlist[from].firstedge; g->adjlist[from].firstedge = e; // 更新目标节点入度 g->adjlist[to].indegree++; } }

这段代码里有一个特别容易被新手忽略的坑：初始化顶点数组时必须把 firstedge 统一置空。如果忘记初始化就分配内存，后面遍历邻接表时会踩到野指针，程序直接崩溃，而且这种崩溃还很难排查，因为它是偶发的、取决于内存里的残值。

3.3 Kahn 算法核心函数

下面是 Kahn 算法的完整实现。这里我使用自己维护的循环队列，而不是用 STL 的队列——毕竟我们是 C 语言，所有东西都得自己写。

#define QUEUE_SIZE 100 typedef struct { int data[QUEUE_SIZE]; int front; int rear; } Queue; void initQueue(Queue *q) { q->front = 0; q->rear = 0; } int isEmpty(Queue *q) { return q->front == q->rear; } int isFull(Queue *q) { return (q->rear + 1) % QUEUE_SIZE == q->front; } void enQueue(Queue *q, int x) { if (isFull(q)) { printf("队列已满，无法入队 %d\n", x); return; } q->data[q->rear] = x; q->rear = (q->rear + 1) % QUEUE_SIZE; } int deQueue(Queue *q) { if (isEmpty(q)) return -1; int x = q->data[q->front]; q->front = (q->front + 1) % QUEUE_SIZE; return x; } // Kahn算法求拓扑排序 int topologicalSort(Graph *g, int *result) { Queue q; initQueue(&q); // 初始化入度为0的节点入队 for (int i = 0; i < g->numNodes; i++) { if (g->adjlist[i].indegree == 0) { enQueue(&q, i); } } int count = 0; while (!isEmpty(&q)) { int node = deQueue(&q); result[count++] = node; // 遍历该节点的所有邻接点 EdgeNode *p = g->adjlist[node].firstedge; while (p != NULL) { int adj = p->adjvex; // 入度减1，减到0就入队 g->adjlist[adj].indegree--; if (g->adjlist[adj].indegree == 0) { enQueue(&q, adj); } p = p->next; } } return count; // 返回成功输出的节点数量 }

主函数测试代码：

int main() { Graph g; createGraph(&g); int result[MAX_NODES]; int count = topologicalSort(&g, result); if (count < g.numNodes) { printf("图中存在环，无法完成拓扑排序。\n"); printf("成功输出的节点数：%d / %d\n", count, g.numNodes); } else { printf("拓扑排序结果："); for (int i = 0; i < count; i++) { printf("%d ", result[i]); } printf("\n"); } // 释放邻接表内存（这里省略，实际项目必须做） return 0; }

3.4 队列容量与边界条件

上面的队列实现有个细节值得说道。循环队列里我预留了QUEUE_SIZE个元素的数组，但实际最多只能放QUEUE_SIZE - 1个元素。为什么要浪费一格？因为front == rear这个条件被用来表示队列为空，如果你真把最后一个格子占满，会分不清是空还是满。

在实际使用时，队列的最大长度就是图中的节点总数 V。因为每个节点只会入队一次，队列里同时存在的入度为 0 节点数量不会超过总节点数。所以只要QUEUE_SIZE大于V + 1，理论上就不会出现队列溢出的问题。我在测试时就把QUEUE_SIZE 定义为 100，对应 MAX_NODES 也是 100，运行是安全的。

如果你处理的是节点数超过 100 的图，可以把MAX_NODES和QUEUE_SIZE改大，或者直接用malloc按需分配。我这里的固定数组是为了让代码在任何编译器上都能直接跑起来，演示性质更强。

3.5 一个完整的测试案例

咱们用课程先修关系来测试。设节点编号：0=C语言，1=数据结构，2=算法设计，3=操作系统，4=编译原理，5=机器学习。先修关系设：0→1，1→2，1→3，2→4，2→5，3→4。

运行结果（可能因队列顺序而异，但必然是合法拓扑序）：

请输入顶点数和边数：6 6 请输入每条边（格式：起始顶点的编号 终止顶点的编号）： 0 1 1 2 1 3 2 4 2 5 3 4 拓扑排序结果：0 1 3 2 5 4

这个结果是合法的：0 在 1 前，1 在 2/3 前，2 在 4/5 前，3 在 4 前。另一种合法结果可能是0 1 2 3 5 4，也没有问题。

再说一个环测试的案例。把边改一下：0→1，1→2，2→0，这样三个节点构成环。

请输入顶点数和边数：3 3 请输入每条边（格式：起始顶点的编号 终止顶点的编号）： 0 1 1 2 2 0 图中存在环，无法完成拓扑排序。

输出数量是 0，因为没有任何一个节点入度为 0。道理和前面说的一样。

4. 和 DFS 法的对比：选型要看清场景

4.1 DFS 拓扑排序的思路：后序逆序

除了 Kahn 算法，另一种常见实现是用 DFS + 栈。简单说就是：对图做深度优先遍历，当一个节点的所有后继节点都访问完之后，才把这个节点压入栈。最后从栈顶开始依次弹出，得到的序列就是拓扑序。

为什么后序遍历再逆序是对的？因为 DFS 递归返回的顺序保证了“后继先入栈”，那么栈顶就是没有后继依赖的叶子节点，最后出栈的是最前面的依赖源头。反过来理解就是：一个节点入栈时，它的所有后继都已经在栈里了，所以栈从顶到底自然满足拓扑序。

但 DFS 版本在实际工程里有个致命缺陷——递归深度。如果图是一条链，比如 1→2→3→...→100000，DFS 的递归深度就到 10 万层，C 语言默认栈空间往往会栈溢出。除非手动改写成显式栈迭代，否则不如 Kahn 算法稳。而且用 DFS 判断环需要增加节点染色状态（白/灰/黑），实现复杂度也不低。

4.2 两个算法的核心差异对照

用一张表来看两个算法的差异更清楚。

从表里可以看出来，Kahn 在绝大多数场景下都是更省心的选择，尤其在大数据处理时，没有递归爆栈的风险。不过 DFS 法在一些场合依然有不可替代的价值——比如在内存极紧张、又不需要立刻输出结果时，DFS 不需要显式维护一个和队列差不多的数组，空间上可能略微有优势（前提是递归栈不被算进去）。

4.3 工程实战中我选择 Kahn 的三个理由

第一，Kahn 算法可以做到“边处理边输出”。我做任务调度时，希望每个任务一准备好就立刻执行，而不是等全图算完再统一执行。Kahn 出队一个节点就是“这个任务可以开跑”的信号。DFS 法必须完整遍历结束才能从栈顶开始输出，天然是离线的。

第二，Kahn 算法与实时并行调度天然契合。出队一个节点后，其所有后继的入度减 1，凡是减到 0 的，说明它的所有前置任务都完成了，可以直接进入“就绪状态”。这其实就是操作系统的进程调度模型，产品和技术都能理解。

第三，Kahn 算法的环检测代码成本几乎为零。就是在最后多比一下 count 和 numNodes 的大小。DFS 法要做环检测需要维护三色标记，每次递归都要判断颜色状态，代码逻辑容易写错，尤其在有多个连通分量时，漏掉某个未访问起点是常有的 bug。

5. 真实场景：任务调度与依赖解析

5.1 编译系统的依赖关系处理

写过大型 C/C++ 项目的人都知道 Makefile。Makefile 里的规则本质上就是一张 DAG，每个目标文件依赖于源文件，可执行文件又依赖所有目标文件。当你执行make的时候，Make 工具内部做的事情之一就是拓扑排序——按照依赖关系决定最早应该执行哪些编译指令。

如果你在 Makefile 里写出了循环依赖——比如a: b和b: a——GNU Make 会直接报错说“circular dependency dropped”。这其实就是一次拓扑排序的环检测。理解了 Kahn 算法，你就能明白为什么 Make 是在“找不到可以执行的目标”的时候才报告循环依赖的，也能理解怎么通过拆分构建阶段来打破循环。

我在实际项目里也遇到过类似的问题。公司的组件库有几十个内部 npm 包互相依赖，发布顺序必须满足“先发底层的、再发上层的”。用脚本做一次拓扑排序，把输出顺序直接作为发布流水线的执行顺序，从此再也不用靠人肉记忆谁依赖谁了。

5.2 把算法写进课程选课系统

回到开头提到的选课系统。用户在系统里勾选本学期要上的课，系统根据先修关系帮用户检查“选课顺序是否合理”。这里我用 Kahn 算法的思路生成建议修读顺序：

• 把用户选的课作为节点，先修关系作为有向边。
• 用 Kahn 算法输出一个可行的修读序列，比如“先修 C 语言，再修数据结构，再修算法设计”。
• 如果检测出环，说明用户选择的课程集合里存在互为先修的情况，系统给出提示，让用户调整选课。

那这个系统在实现上需要注意什么？接口返回的拓扑序列可能有多个合法解，用户可能会问“为什么推荐先修 A 而不是 B”。这时候我通常会先按课程的编号或优先级做排序，再用优先队列替代普通队列，保证输出是字典序最小的那个拓扑序列，这样用户体验上不容易困惑。

具体做法是把普通 Queue 换成最小堆。在 C 语言里可以用一个简单数组维护最小堆，也可以用已有的优先队列库。每次从堆顶取出的节点都是当前编号最小的入度为 0 节点，最终输出的拓扑序就是所有合法序列中的字典序最小序列。这个细节在面试里也特别常见，问“如果要输出字典序最小的拓扑序怎么办”，答案就是这个。

5.3 包管理器里的循环依赖检测

包管理工具（如 npm、Maven 等）最怕的就是出现循环依赖。用 Kahn 算法做依赖解析时，如果最终输出的依赖数量少于已声明的依赖数量，那么就可以定位到哪些包存在循环依赖。把这些包名输出给用户，要求他们拆分模块或调整依赖关系。

有意思的是，Kahn 算法在“安装依赖”这个场景里还有一种基础变体：不是一次性求出全局拓扑序，而是从某个包出发做受限拓扑遍历，只解析“当前包所涉及的依赖链”。这就把全图的拓扑排序变成了子图的依赖树分析。但核心原理完全一致。

6. 常见问题与排错技巧

6.1 问题：结果数量少于节点数，一定是环吗

答案是：一定是存在环，但具体是哪几个节点构成环，需要进一步分析。

我在项目里遇到过一个特别迷惑的场景：图的节点数有 50 个，最后 Kahn 输出了 48 个，还有 2 个节点卡住。我一开始以为是这两个节点形成了小环，认真检查后发现并不是。实际情况是这 2 个节点不在环上，但有一连串依赖关系最终还是依赖到环里的某个节点，导致它们的入度永远无法清零。

所以排查时千万别只盯着“剩下那 2 个节点”，而是要沿着它们的依赖链往上找，直到路径出现循环。这种情况在数据依赖配置里特别常见，比如 A 依赖 B，B 依赖 C，C 又依赖 A，同时 D 依赖 B——那么 D 也是无法输出的。

6.2 问题：多个节点入度为 0，先处理哪个？

前面提到，拓扑排序结果不唯一。假设当前队列里有 3 个入度为 0 的节点，你随便取 1 个出来都是合法的。但如果面试题里明确要求“输出字典序最小的拓扑序”，那就必须用优先队列，不能用普通 FIFO 队列。

这里有一个常见误区：有人觉得“只要入度为 0 就入队，先入队的先出队，这样顺序是稳定的”，但稳定的只是相对输入顺序，不是字典序。如果需要字典序最小，记住把队列换成最小堆（优先队列），每次弹出顶点编号最小的节点。

6.3 问题：为什么我用栈替代队列，结果也正确？

理论上栈也可以。Kahn 算法中，队列只是“保存当前可用节点”的容器，不要求 FIFO 特性。你用栈、用数组、随便拿个 list 都能保证正确性，前提是你能从里面取出一个元素来处理。

那为什么教程和实现都用队列？因为 Kahn 算法是从 BFS 思路延伸出来的，BFS 天然配队列，代码上更自然。而如果你用栈，算法就变成了 DFS 和 Kahn 的一个杂交体，出队的节点顺序会偏向“后进先用”，结果仍然是合法拓扑序，但和 BFS 版的线性度略有差异，可能让调试时比较困惑。我建议初学者老老实实用普通队列，不要花里胡哨。

6.4 三个独家排错技巧

先分享一个百试百灵的自测方法。当你实现完 Kahn 算法，建议先拿一个小 DAG 跑一遍，然后把每一步队列里的节点和入度数组打印出来，人工推演一遍，确认无误后再跑大数据。我用过的日志格式大概长这样：

初始化，入度为0的节点入队：[0, 2] 取出节点 0，邻接节点 1 入度由 2 减到 1，不入队 取出节点 2，邻接节点 3 入度由 1 减到 0，入队 取出节点 3，邻接节点 1 入度由 1 减到 0，入队 取出节点 1，全部处理完毕

配合一份这样的日志，哪怕算法出了 bug，你也能一眼看出是入度更新出了问题，还是队列逻辑有问题。我自己每次实现新算法时都会打这种日志做单步验证，调试效率提高很多。

第二个技巧是先画图再写代码。很多人在写邻接表时会把边的方向搞反，导致拓扑排序结果全反。建议先在纸上画出图，标注每个节点的入度，然后对照代码一步步模拟。节点少于 8 个时，这种手工模拟就足以发现大多数问题。

第三个技巧是完整实现内存释放。C 语言项目里，很多人写完核心逻辑就不管内存了，但如果你的拓扑排序被反复调用，内存泄漏会越来越严重。释放顺序是：从每个顶点的 firstedge 开始，遍历链表逐个 free 边节点，最后重置顶点数组。如果我的代码示例里有省略释放，是因为把它单独写出来会让演示代码太长，实际工程里这是一定要做的。

我在实际项目里还踩过一个坑：一开始用全局二维数组保存邻接矩阵，V 到了 1 万以后，内存直接爆掉。改用邻接表之后，1 万节点、3 万边的稀疏图，内存从 400MB 降到不到 5MB，速度反而更快。所以选邻接表不是一个“高档选项”，而是大图的唯一选项，这也是我建议你优先掌握邻接表的原因。

写在最后的实践笔记

每次重写一遍 Kahn 算法，我都会有一些新的收获。这次最大的感受是：越基础的算法，它的边界条件越值得抠细节。比如“入度为 0 的节点用队列还是栈”这种问题，课本上不会细讲，但落到工程里你真的会遇到多解的问题；比如“环检测剩下多少个节点”这个数字，坑过不少人——它不等于环长度。如果你在实现过程中也卡住了，建议把我代码里的打印日志加回去，手动推演一遍，绝大多数问题都会水落石出。

最后再分享一个可以继续扩展的方向：Kahn 算法本身是无权图的拓扑排序，但如果你的任务带有优先级权重，比如每个任务有预估工期，想让整体完成时间最短，那就要引入关键路径算法（CPM），它是在拓扑序基础上再做一次动态规划。路线是先跑 Kahn 拿到拓扑序，然后按拓扑序逐节点计算最早开始时间和最晚结束时间——这篇文章的代码，正好可以当那条路线的地基。