Kahn算法是DAG拓扑排序的标准解法，包含三种实现：一、基于邻接表与队列的标准BFS实现；二、用priority_queue实现字典序最小拓扑序；三、用静态数组优化的紧凑实现。

如果您需要在C++中对有向无环图（DAG）执行拓扑排序，且希望基于入度统计与广度优先搜索（BFS）机制实现稳定、可验证的线性序列输出，则Kahn算法是直接对应的标准解法。以下是该算法的两种核心实现方案：

一、基于邻接表与队列的Kahn算法标准实现

该方案使用vector>存储邻接表，vector维护各节点入度，queue管理当前入度为0的候选节点。每次从队列弹出节点时，将其加入结果序列，并对其所有邻接点执行入度减1操作；若某邻接点入度降为0，则入队。此过程天然保证了拓扑序的合法性与BFS层级推进特性。

1、定义图的顶点数n，初始化邻接表graph(n)，入度数组indeg(n, 0)；

2、遍历所有有向边u→v，执行graph[u].push_back(v)与indeg[v]++；

立即学习“C++免费学习笔记（深入）”；

3、遍历0至n−1，将所有indeg[i] == 0的i压入queue q；

4、初始化空vector result；当q非空时，执行循环体：弹出队首cur，将cur追加至result；遍历graph[cur]中每个邻接点nei，执行indeg[nei]--，若indeg[nei] == 0则将nei入队；

5、若result.size() != n，则图中存在环，拓扑排序不存在；否则result即为合法拓扑序列。

二、使用priority_queue实现字典序最小拓扑序

当需在多个合法拓扑序中选取字典序最小者时，将标准队列替换为大根堆（实际使用greater配置的priority_queue, greater>），确保每次优先处理编号最小的入度为0节点。该变体不改变算法本质，仅调整节点选取策略，仍严格遵循入度归零即释放、BFS逐层消解的逻辑。

1、声明priority_queue, greater> pq，其余数据结构同方案一；

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

2、初始化阶段，将所有indeg[i] == 0的i插入pq而非普通queue；

3、循环中每次调用pq.top()获取最小可用节点，pop后处理其邻接点，入度归零者仍以相同方式插入pq；

4、最终生成的result序列满足：在所有可能拓扑序中，其字符串表示具有最小字典序；

5、环检测逻辑不变，仍通过result长度是否等于n判定。

三、使用静态数组优化的紧凑实现（适用于顶点编号连续且范围已知）

当图规模较大但顶点编号固定为0~MAXN−1且MAXN可预估时，可避免vector动态扩容开销，改用int graph[MAXN][MAXN_DEG]、int deg[MAXN]、int q[MAXN]及头尾指针实现纯数组模拟队列。该方案减少内存分配次数，提升缓存局部性，在嵌入式或竞赛高频调用场景下具备性能优势。

1、定义全局常量MAXN = 10005，MAXN_DEG = 500；声明int graph[MAXN][MAXN_DEG]，int deg[MAXN]，int q[MAXN]，int head = 0, tail = 0；

2、读入边u→v时，在graph[u][deg[u]++] = v，同时deg[v]++（此处deg复用为出度计数器，另设indeg[v]++记录入度）；

3、遍历0~n−1，若indeg[i] == 0，则q[tail++] = i；

4、当head

5、若处理节点总数不等于n，说明图含环，无法完成拓扑排序。