如何通过入度统计法和BFS实现图的拓扑排序（Kahn算法）？

本文共计1085个文字，预计阅读时间需要5分钟。

由于题目要求不使用伪代码，不尝试图解，不使用数数，且不超过100字，以下是对原内容的简化：

常见错误是只建图、不做入度数组，或者入度初始化漏掉孤立节点（即既无入边也无出边的点），导致它们永远进不了队列，结果序列缺元素。

• 入度数组大小必须覆盖所有可能的节点编号，建议用 vector<int> indeg(n)</int>，其中 n 是节点总数（不是边数）
• 如果节点编号不连续（比如出现 1, 3, 7），别硬套下标，改用 map<int int></int> 或离散化
• 有向边 u → v 意味着要执行 indeg[v]++，不是 indeg[u]++

如何用 BFS 正确维护拓扑序列

BFS 在这里不是为了找最短路，而是模拟“逐层剥离源头”的过程：每次取出一个入度为 0 的节点，加入结果，再把它所有出边删掉（即对每个邻居 v 执行 indeg[v]--），若减后为 0 就立即入队。

关键在于「入队时机」：必须在 indeg[v] == 0 刚成立时立刻入队，不能等到下一轮 BFS 再检查——否则会漏节点或死循环。

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

• 用 queue<int></int> 存当前可扩展的节点，别用 stack（那是 DFS 拓扑，逻辑不同）
• 每 pop 一个节点，就把它加进结果 topo vector；不要在入队时就 push
• 如果最终 topo.size() != n，说明图中有环，不存在合法拓扑序

C++ 实现中容易忽略的边界与性能点

标准实现看似简单，但实际写错多在初始化和容器选择上。比如用 vector<vector>></vector> 存邻接表时，忘了 resize 图大小；或用 list 替代 queue 导致常数变大；还有把 indeg 声明成局部变量却没初始化为 0。

一个典型错误示例：vector<int> indeg;</int> 而没调用 indeg.resize(n, 0)，此时访问 indeg[i] 是未定义行为。

• 邻接表推荐用 vector<vector>> graph(n)</vector>，比 vector<list>></list> 缓存友好
• 入度数组务必显式初始化： vector<int> indeg(n, 0)</int>
• 输入含重边？Kahn 不怕，但 indeg[v]++ 会重复加——需去重或用 set 预处理；一般题目默认无重边
• 节点数 n 和边数 m 都得从输入读，别硬编码

完整可运行的 Kahn 拓扑排序代码片段

以下是最简可用版本，支持节点编号 0 到 n-1，返回空 vector 表示有环：

vector<int> kahnTopo(int n, const vector<vector<int>>& edges) { vector<vector<int>> graph(n); vector<int> indeg(n, 0); for (auto& e : edges) { int u = e[0], v = e[1]; graph[u].push_back(v); indeg[v]++; } queue<int> q; for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i); vector<int> topo; while (!q.empty()) { int u = q.front(); q.pop(); topo.push_back(u); for (int v : graph[u]) { indeg[v]--; if (indeg[v] == 0) q.push(v); } } return topo.size() == n ? topo : vector<int>(); }

调用时传入边列表，例如 {{0,1},{1,2},{0,2}}，返回 {0,1,2}；若传入 {{0,1},{1,2},{2,0}}，返回空 vector。

真正难的不是写对这个函数，而是当图结构动态变化、或需要输出所有拓扑序、或带权重约束时，Kahn 的扩展逻辑很容易崩——那些时候，入度维护和队列策略就得重新推演。