如何通过入度统计法和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 再检查——否则会漏节点或死循环。