拓扑排序结果为线性序列，使用kahn算法：先构建邻接表并同步更新入度数组，再将入度为0的顶点入队，bfs遍历中逐个剥离并更新邻接点入度，最终判断是否包含全部顶点。

要用C++实现图的拓扑排序，且必须基于Kahn算法——即通过统计每个顶点入度、反复剥离入度为0的节点并更新邻接点入度来完成线性排序，整个过程需严格依赖BFS遍历逻辑，不能使用DFS或递归回溯。

构建有向图并初始化入度数组

定义图的顶点数V和边列表edges，用vector> adj表示邻接表；同时声明vector indegree(V, 0)，为每个顶点预分配入度计数器。

遍历edges中每条边u→v，执行adj[u].push_back(v) → indegree[v]++；这一步不可颠倒，【若先建邻接表再统计算入度，可能漏计自环或重复边】。

用队列启动BFS剥离过程

方法一：标准queue q；遍历所有顶点i（0 ≤ i

方法二：改用deque或priority_queue可控制输出顺序，但Kahn原始算法仅要求任意入度为0节点优先，此处用普通queue最稳妥。

注意：初始时队列为空不报错，但意味着图含环，后续步骤将自然暴露该问题。

执行拓扑剥离与入度更新

第一步：当q非空时，取队首节点u → 将u加入结果vector topo中 → 弹出q.front()。

C++14

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

下载

第二步：遍历adj[u]中每个邻接点v → 执行indegree[v]-- → 若indegree[v] == 0，则q.push(v)。

第三步：重复上述两步直至队列为空。

这一步是BFS骨架所在：每个节点仅被访问一次，每次只处理其直接后继的入度变化，时间复杂度严格为O(V + E)。若某次循环后q为空但topo.size()

验证结果有效性并返回

比较topo.size()与V是否相等。

相等则返回topo；不相等则返回空vector()，表示不存在合法拓扑序。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！