Kahn算法必须用入度数组而非出度，因为拓扑排序需优先输出无前置依赖的节点，入度为0精确标识该状态；误用出度会导致节点在其前驱未处理时被提前弹出，破坏依赖顺序并漏检环。
为什么 Kahn 算法必须用入度数组而非出度
因为拓扑排序本质是找“没有前置依赖”的节点优先输出，而入度为 0 正好刻画这个条件。indeg[v] 表示还有多少条边指向 v，只有当它降为 0，才说明所有前驱都已处理完毕。若误用出度，你会在节点还有未访问后继时就把它弹出队列，破坏依赖顺序。
常见错误现象：std::queue 里提前弹出有未处理子节点的节点，导致输出序列中某节点出现在其前驱之前；或最终结果长度小于图中节点数（漏点），说明存在环但没被检测出来。
- 初始化时必须遍历所有节点设置
indeg[i] = 0，不能只对有入边的节点赋值——孤立节点入度也是 0 - 建图时每添加一条
u → v边，仅递增indeg[v]，绝不碰indeg[u] - 若图用邻接表
vector存储，> indeg数组长度必须等于节点总数（哪怕编号不连续，也要按最大编号+1分配）
如何用 BFS 正确驱动 Kahn 算法流程
BFS 在这里不是为了最短路径，而是保证“层序消解依赖”：每轮只处理当前所有入度为 0 的节点，并批量更新它们邻居的入度。这天然契合队列的 FIFO 特性。
关键细节在于更新时机和判断逻辑：
- 初始时把所有
indeg[i] == 0的i入队，不能漏掉任何一个 - 每次
pop后立刻将该节点加入结果topo向量，这是拓扑序的生成点 - 对每个邻居
v，执行if (--indeg[v] == 0) q.push(v)—— 必须用前置减，且只在减到 0 时才入队 - 循环结束后，必须检查
topo.size() != n，若成立说明图含环，无法拓扑排序
C++ 实现中 vector 和 queue 的典型误用场景
新手常在容器使用上触发越界或逻辑错位。例如用 graph.size() 当节点总数，但图可能从 1 开始编号；或把 queue 声明在 while 内部导致每次重置。
一个最小可运行片段的核心骨架如下（假设节点编号为 0 到 n-1）：
vector<vector>> 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 topo;
while (!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
for (int v : graph[u])
if (--indeg[v] == 0) q.push(v);
}
if (topo.size() != n) // 有环
</int></int></vector>
注意：graph[u].push_back(v) 中 u 是源，v 是目标；indeg[v]++ 对应；两者方向必须严格一致，否则整个依赖关系反转。
环检测失败的三个隐蔽原因
即使写了 topo.size() != n 判断，仍可能漏检环，尤其在输入不规范时。
- 节点编号超出
[0, n-1]范围，导致indeg数组访问越界或未覆盖，部分节点入度始终为 0（假阳性） -
edges中存在自环u → u：此时indeg[u]至少为 1，永远无法入队，但你的n若按最大编号算，topo.size()会小于n，这反而是正确表现；问题在于你是否把自环当作非法输入提前过滤 - 图含多个连通分量，其中某个分量成环，但其余分量正常——这时
topo.size() 仍成立，检测有效；真正容易忽略的是：你是否确保所有节点编号都出现在edges或显式初始化中？缺失的节点若没被indeg数组包含，就根本不会参与环判断
最稳妥的做法是：先扫描所有 edges 提取全部出现的节点编号，去重后作为实际节点集，再据此确定 n 和分配 indeg。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
