C++实现图的拓扑排序(Kahn算法) _ 入度统计法与BFS核心算法实现【源码】

拓扑排序失败，这事儿在算法实现里挺常见的。表面上看，代码逻辑似乎都对，但一运行，要么卡住不动，要么输出的序列长度不对，就是排不出一个完整的顺序。问题的根源，十有八九是图中存在环路依赖，导致算法找不到那个“零依赖”的起始节点，整个流程就卡壳了。

具体是哪些环节容易出岔子呢？咱们来逐一排查。

为什么拓扑排序失败？先检查入度数组是否初始化为0

如果你的拓扑排序卡在空队列或者提前退出了，第一个要怀疑的就是 inDegree 数组有没有被正确清零。在C++里，用 vector inDegree(n, 0) 来初始化是相对安全的做法。但如果你用的是裸数组，比如 int inDegree[1000]，却忘了用 memset 或者 std::fill 来初始化，那么数组里残留的随机值就会被误当成某些节点的入度。结果就是，这些节点可能永远达不到入度为0的条件，进不了队列，整个排序流程自然就中断了。

一个典型的错误现象是：最终得到的 result.size() 不等于节点总数 n，但程序又不报错。调试的时候仔细看，可能会发现某个节点的 inDegree[v] 显示为一个非常大的随机数。

• 优先使用 vector 容器，它能帮你省去手动清零的麻烦，也避免了遗漏的风险。
• 如果非要用数组不可，记得在声明后立刻用 std::fill 或 memset 进行初始化。
• 在处理每条边 u → v 时，确保只执行一次 inDegree[v]++，避免重复累加导致入度计算错误。

如何正确构建邻接表并遍历出边？注意 vector> 的索引方向

Kahn算法的核心逻辑是“从当前节点出发，能到达哪些节点”。因此，邻接表的构建方向至关重要：graph[u] 里存储的，必须是所有从节点 u 出发能直接到达的节点 v。如果方向搞反了，后续的BFS流程就无法正确更新下游节点的入度。

一个典型的错误是把边 u → v 存成了 graph[v].push_back(u)。这样一来，当BFS从队列中弹出节点 u 时，它试图去遍历 graph[u] 寻找出边，却发现里面是空的（或者根本不是它的后继节点），导致后续所有依赖它的节点入度都无法递减，全部被卡住。

• 在读入边的时候，明确地写成 graph[u].push_back(v)，并在心里默念“u指向v”。
• 一个简单的验证方法：打印出 graph[0] 的内容，确认里面的元素确实都是从节点0出发能到达的终点。
• 特别注意：如果输入包含无向图的边，需要额外处理。拓扑排序只适用于有向无环图（DAG），无向边本身就构成了环，算法应该拒绝处理这种情况。

BFS过程中何时更新入度？必须在弹出节点后立即处理其所有邻接点

这里的逻辑顺序是关键。核心不是“遇到一个入度为0的节点就把它加入队列”，而是“每处理完一个节点，就把它所有后继节点的入度减1；减完之后，如果某个后继节点的入度变成了0，才把它加入队列”。如果这个顺序颠倒了（比如先入队再减），或者漏减了某个后继，整个拓扑序的生成就会被破坏。

从性能角度看，每次入度减1的操作是O(1)的，所以总的时间复杂度依然是O(V + E)。但如果你用了 map 或 set 来存储邻接关系，而没有预分配好空间，常数项可能会变大。在小规模数据上可能看不出来，但数据量一大，就有超时的风险。

• 标准的处理流程应该是：int u = q.front(); q.pop(); → 遍历 for (int v : graph[u]) → inDegree[v]--; → 检查 if (inDegree[v] == 0) 则 q.push(v)。
• 不要在循环内部去修改 graph[u] 这类容器（比如删除边），这既没必要，也容易引入错误。
• 使用普通的 queue 就足够了，除非题目明确要求输出字典序最小的拓扑序，才需要考虑使用 priority_queue。

怎么判断图含环？仅靠队列空还不够

这是Kahn算法一个非常优雅的特性：它天然具备环检测的能力。如果BFS结束后，队列空了，但得到的 result 序列长度小于节点总数 n，那就说明图中存在环。因为环内的所有节点，它们的入度永远无法被减到0，所以永远没有机会进入队列。

这里有个容易混淆的点：如果图是不连通的，但每个连通分量本身都是DAG（有向无环图），那么算法仍然可以完成排序。只有当图中存在至少一个有向环时，result 的长度才会“缩水”。另外，不要把孤立的节点（入度为0且出度也为0）误判为环的一部分——它们在算法一开始就会被加入队列。

• 所以，在算法最后，必须加上检查：if (result.size() != n) { // 检测到环，进行相应处理 }。
• 不要试图用异常或者特殊的返回码来隐藏环的信息。在业务逻辑里，必须显式地处理存在环的这种情况。
• 调试时，可以额外统计“入队次数”和“出队次数”，理论上二者应该相等。如果不相等，那说明队列的弹出和压入逻辑可能有问题。

最后提一句，拓扑排序的结果本身通常不唯一。但是，基于入度统计和BFS的Kahn算法，只要输入和邻接表遍历顺序固定，每次运行得到的结果是稳定的。当然，如果你用了 unordered_set 这类无序容器来存储邻接关系，那输出的顺序就不可控了，这点需要注意。