Kahn算法是求解有向无环图拓扑排序的标准BFS方法：基于入度统计，每次取入度为0的节点加入序列并更新邻接点入度，最终若序列长度等于节点数则成功，否则图中存在环。
如果您需要在C++中实现有向无环图（DAG）的拓扑排序，且要求基于入度统计与广度优先搜索（BFS）机制，则Kahn算法是直接对应的标准解法。以下是该算法的完整核心实现逻辑与源码级说明：
一、算法原理与数据结构准备
Kahn算法依赖于节点入度的动态维护与零入度节点的逐层剥离。其本质是模拟BFS过程：每次选取当前入度为0的节点输出，并将其所有邻接节点入度减1；若某邻接节点入度降为0，则加入待处理队列。该过程持续至队列为空，最终输出序列即为合法拓扑序（若图含环，则输出节点数少于总节点数）。
需预先构建邻接表表示图结构，并用数组或vector存储各节点当前入度值；使用queue实现BFS调度；另需vector记录拓扑序结果。
二、C++核心源码实现（标准模板）
以下代码严格遵循C++11及以上标准，不依赖第三方库，仅使用
1、定义图节点数n，声明邻接表graph为vector
2、声明inDegree为vector
3、遍历所有有向边(u → v)，执行graph[u].push_back(v)与inDegree[v]++；
4、创建queue
5、创建vector
6、当q非空时，执行：int u = q.front(); q.pop(); topo.push_back(u)；对每个v ∈ graph[u]，执行inDegree[v]--；若inDegree[v] == 0，则q.push(v)；
7、若topo.size() != n，则图中存在环，拓扑排序不存在；否则topo即为有效拓扑序列。
三、关键边界与健壮性处理
实际工程中需防范索引越界与输入非法。入度数组下标必须严格对应0~n−1节点编号；若输入边含负数或≥n的顶点编号，应在读入阶段进行范围校验并抛出异常或跳过非法边；邻接表应预留足够容量以避免频繁重分配；对于空图（n=0），应直接返回空vector且不执行BFS循环。
1、在初始化inDegree前，先检查n是否大于0；
2、对每条输入边，判断u和v是否满足0 ≤ u
3、若不满足，输出错误提示并终止边解析流程；
4、queue声明后立即启用empty()验证初始状态；
5、topo构造完成后，用size()与n比对，而非依赖布尔标志变量。
四、时间与空间复杂度分析
算法遍历每条边恰好一次，每个节点入队出队各一次，故时间复杂度为O(V + E)，其中V为节点数，E为边数。空间上需存储邻接表（O(E)）、入度数组（O(V)）、队列与拓扑序列容器（O(V)），因此总空间复杂度为O(V + E)。
1、邻接表graph占用内存与边数线性相关；
2、inDegree与topo均占用O(n)连续空间；
3、queue在最坏情况下存入全部节点，峰值空间为O(n)；
4、所有容器均采用move语义或reserve预分配可进一步降低常数因子，但不改变渐进复杂度阶数。
五、典型测试用例驱动验证
构造最小非平凡DAG：3个节点，边集为{0→1, 0→2}。预期拓扑序为[0,1,2]或[0,2,1]。运行代码后检查topo[0]是否为0，且topo[1]与topo[2]是否为1和2的某种排列；再构造含环图如{0→1, 1→2, 2→0}，验证topo.size()是否等于0（n=3时结果为false）。
1、初始化n=3，graph.resize(3)，inDegree.assign(3,0)；
2、插入边0→1：graph[0].push_back(1), inDegree[1]++；
3、插入边0→2：graph[0].push_back(2), inDegree[2]++；
4、此时inDegree = [0,1,1]，仅节点0入队；
5、出队0后，更新inDegree[1]与inDegree[2]为0，二者先后入队；
6、最终topo = {0,1,2}或{0,2,1}，取决于邻接表遍历顺序，均属合法拓扑排序结果。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
