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

拓扑排序结果长度不足，或者程序提前终止了？这背后大概率是Kahn算法的一些细节没做到位：入度数组没初始化、邻接表方向反了、入度更新遗漏了，或者初始队列里漏掉了本应为0的节点。说到底，就是要严格初始化indegree(n,0)，按u→v建图，并且全范围扫描节点入队。

进行图的拓扑排序时，如果输出的序列长度小于节点总数，或者程序半途就退出了，别急着怀疑算法本身——十有八九是Kahn算法在入度统计或BFS执行阶段出了偏差。典型的坑包括：入度数组没初始化、邻接表方向搞反、入度更新漏了步骤，或者初始队列压根没把那些入度为0的节点全部装进去。下面就把这些症结逐一拆开，并给出直接的解决方案。

一、正确初始化入度数组与邻接表

入度数组必须覆盖全部节点编号范围，并且显式初始化为0——这一步看似基础，却常常被遗漏。残留的随机值会让你误判哪些节点入度为0，或者把不该入队的节点放进去。邻接表那边更简单：严格按有向边u→v存储，即graph[u]里包含所有v，这样BFS遍历出边时才能准确更新下游入度。

具体操作上：声明节点总数n后，立刻初始化入度数组：vector indegree(n, 0)，别偷懒用裸数组而不调用memset或std::fill。邻接表统一采用vector> graph(n)，避开map或unordered_map带来的哈希开销和未定义访问风险。读入每条有向边u→v时，同时执行graph[u].push_back(v)和indegree[v]++，千万别反向写成graph[v].push_back(u)或indegree[u]++。如果输入边是1-based（比如节点编号从1开始），读入后立刻执行u--, v--，确保下标落在[0, n−1]内。

二、构建初始 BFS 队列并确保覆盖所有入度为 0 的节点

初始队列必须包含所有满足indegree[i] == 0的有效节点——注意是所有，包括那些既没有入边也没有出边的孤立点，以及有出边但无入边的真正起点。很多人只扫描边列表中的from或to节点，结果那些从未出现在边中的编号直接被忽略，节点就丢了。

正确的做法是：遍历完整节点集：for (int i = 0; i ，对每个i检查if (indegree[i] == 0)，成立则q.push(i)。如果节点编号不连续或稀疏（比如最大编号是1e5但实际只有100个节点），改用unordered_map indegree，同时维护一个有效节点集合unordered_set nodes，初始化队列时只遍历该集合中indegree[x] == 0的x。

三、BFS 过程中实时更新入度并严格控制入队时机

BFS的核心不是“输出节点”，而是“模拟删边”。每次从队列弹出节点u后，必须立刻对其每个邻接点v执行入度减1，并且仅在减后为0时才入队。延迟判断或合并检查，都会导致节点漏处理，甚至死循环。

具体流程：取出节点u后，立即加入结果容器：result.push_back(u)。然后遍历graph[u]中的每个v，执行--indegree[v]，这个操作必须和判断紧挨着：if (indegree[v] == 0) q.push(v)。别拆成两步，也别添加多余条件（比如!visited[v]）。另外，不要事先把indegree[u]改成-1，也不用布尔数组标记已访问——indegree[v] == 0就是唯一且充分的入队依据。

四、环检测与失败判定的唯一可靠方式

判断是否存在环，不能靠队列是否为空、是否找到新入度为0的节点，或者剩余indegree是否全为0。唯一可信的依据是：最终拓扑序列的长度是否等于图中实际有效节点总数。

BFS循环结束后，直接比较：if (result.size() != n)。如果条件成立，立即返回空vector：return {};，意味着存在环，无合法拓扑序。如果使用unordered_map存储indegree，应该以nodes.size()作为totalNodes，而不是indegree.size()或图的最大编号。调试时如果发现result.size() < n，多半是入度更新有遗漏，或者初始队列漏了节点。

五、规避常见边界错误的硬性规范

90%的Kahn实现失败，根源并非算法逻辑，而是边界对齐失误。节点编号连续性、容器大小匹配性、初始化完整性，这些细节一旦错了，小样例可能蒙混过关，但大规模输入必定崩溃。

邻接表graph声明时必须指定大小n：vector> graph(n)，别指望后续resize或push_back动态扩展。即使n == 0或边集为空，也要执行完整的初始化流程——确保所有indegree[i] == 0的节点（也就是全部n个节点）都被推入初始队列。另外，禁止用stack或priority_queue替代queue，前者退化为DFS拓扑，失去环检测能力；后者只有在需要字典序最小序时才引入，否则徒增log n开销。最后，重边（多条u→v）需要在建图阶段去重，或者接受indegree[v]多次递增；如果不做去重却只执行一次indegree[v]--，那indegree[v]永远无法归零，节点就会卡死在那里。