拓扑排序成功执行的前提是图必须为有向无环图（DAG）；Kahn算法通过入度数组与BFS模拟任务依赖过程，天然支持环检测——若最终结果长度不等于节点总数n，则图中存在环。
拓扑排序能成功执行，只有一种前提：图必须是有向无环图（DAG）；Kahn 算法一旦在 BFS 过程中发现还有剩余节点但入度队列已空，就说明存在环，排序失败。
为什么用入度数组 + 队列，而不是 DFS 回溯？
Kahn 算法本质是模拟“任务依赖完成”的过程：只有所有前置任务（入边）都做完，当前任务才能开始。它天然适合用入度统计 + BFS 实现，逻辑直白、无递归栈溢出风险、容易检测环。
常见错误现象：std::queue 为空但 result.size() ，却没检查是否成环，直接返回部分结果——这会掩盖图含环的事实。
- 入度数组（
indeg）必须初始化为 0，再遍历所有边累加，不能靠 vector 默认构造值（若节点编号不连续或从 1 开始，易越界） - 队列只推入
indeg[i] == 0的节点，且入队后立即把indeg[i]设为 -1 或用布尔数组标记已访问，避免重复入队 - BFS 中每弹出一个节点
u，需遍历其所有邻接点v，并对每个v执行indeg[v]--；仅当indeg[v] == 0时才入队
std::vector<:vector>></:vector> 邻接表 vs std::vector<:list>></:list> 性能差异
对 Kahn 算法而言，邻接表结构只用于「遍历 u 的所有后继」，操作频次 = 边数 E，因此随机访问性能影响极小。但实际编码中更倾向用 std::vector<:vector>></:vector>：
- 内存局部性更好，cache 友好，尤其当图较稠密时
- 无需额外
#include <list></list>，代码更轻量 -
adj[u].size()和adj[u][i]比adj[u].size()+ 迭代器遍历更简洁（注意：不要用for (auto v : adj[u])在修改indeg时隐式拷贝）
若图稀疏且动态增删边频繁，才考虑 std::vector<:list>></:list>；但 Kahn 是离线一次性处理，不在此列。
如何正确处理节点编号不连续或非 0 起始？
很多题设节点编号是 1~n，或给的是字符串 ID（如 "A", "B"），直接用 vector<int> indeg(n)</int> 会错位或越界。
- 最稳妥做法：先收集全部唯一节点 ID，映射到
0 ~ N-1，例如用std::unordered_map<string int> id2idx</string> - 若确定编号范围是
1~max_id，则申请indeg(max_id + 1)，并只使用下标1到max_id区间 - 切忌用
indeg[node]前不校验node —— 这类越界在 debug 模式可能不报错，但 release 下行为未定义
示例片段（安全索引）：
if (v >= 0 && v <h3>环检测与结果验证的最小必要检查</h3><p>Kahn 算法不是“排完序再验环”，而是在过程中实时暴露环——这是它比 DFS 拓扑更易调试的关键优势。</p>
- 初始化时统计总节点数
N（不是边数） - BFS 结束后，严格比较
result.size() == N；不等即含环，此时不应返回result，而应返回空 vector 或抛异常 - 无需额外 DFS 验证环：若
result.size() ，剩余节点必然构成至少一个环，因为它们的入度始终 > 0，无法进入队列 - 若业务允许部分排序（如“尽可能排无依赖任务”），需明确文档化该行为，而非静默截断
真正容易被忽略的是：**入度数组的生命周期必须覆盖整个 BFS 过程，且不能在中间被 resize 或 move**——尤其在封装成函数时，别把 indeg 声明在 for 循环内。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
