Kahn算法必须用入度数组，因为仅靠队列是否为空无法判断是否存在剩余可调度节点，入度数组是唯一能实时反映各节点前置依赖是否清零的依据；若最终结果长度不等于n，则图中存在环。
为什么 Kahn 算法必须用入度数组，不能只靠队列判断？
因为拓扑排序本质是“逐层剥洋葱”：只有入度为 0 的节点才真正可调度。仅靠 queue 是否为空无法反映图中是否还有剩余有效起点——可能队列空了但仍有环内节点未处理。入度数组 indeg[] 是唯一能实时反映每个节点前置依赖是否已清除的依据。
实操建议：
- 初始化时对每个节点调用
indeg[v]++（而非indeg[u]++），方向必须是u → v边对应indeg[v] += 1 - 建图后务必遍历所有节点检查
indeg[i] == 0，漏掉孤立点（无边但存在）会导致结果缺失 - 若最终输出节点数
result.size() != n，说明图含环，不是 DAG —— 这是 Kahn 算法自带的环检测能力，别手动再加 DFS 判环
如何用 vector> 建邻接表并正确更新入度？
邻接表存的是出边，所以遍历 graph[u] 得到的是所有 v 满足 u → v。入度更新必须作用在 v 上，和邻接表逻辑严格对齐。
常见错误现象：indeg[u]++（反向更新）、或把边读成 v u 却仍按 u→v 处理
示例片段（关键行已标）：
int n = 6; vector<vector>> graph(n); vector<int> indeg(n, 0); // 假设输入边：0→1, 1→2, 2→3, 4→1, 4→5 // 正确建图与入度更新： graph[0].push_back(1); indeg[1]++; // ← 关键：indeg[v]++ graph[1].push_back(2); indeg[2]++; graph[2].push_back(3); indeg[3]++; graph[4].push_back(1); indeg[1]++; // ← 同一节点入度可累加 graph[4].push_back(5); indeg[5]++; </int></vector>
BFS 过程中修改入度时，为什么要检查 v 的入度是否已为 0？
因为多个前驱可能同时指向 v，每次只减 1；只有当 indeg[v] 减到 0 时，v 才真正就绪。不加判断直接 push 会重复入队、破坏顺序、甚至导致死循环（如果用了 visited 但没控入度）。
实操要点：
- 每次从队列取出
u后，遍历其所有邻接点v - 执行
if (--indeg[v] == 0) q.push(v)—— 必须是前置递减后判断 - 绝不能写成
indeg[v]--; if (indeg[v] == 0) ...，虽等价但多一次访问，且易在调试时误删判断 - 使用
std::queue即可，无需优先队列；如需字典序最小拓扑序，才换std::priority_queue
完整可运行的 Kahn 拓扑排序函数长什么样？
以下是最简可用版本，不含输入解析，聚焦核心逻辑。注意返回值是 vector，空表示有环。
vector<int> topologicalSort(int n, const vector<vector>>& graph) {
vector<int> indeg(n, 0);
for (int u = 0; u q;
for (int i = 0; i result;
while (!q.empty()) {
int u = q.front(); q.pop();
result.push_back(u);
for (int v : graph[u]) {
if (--indeg[v] == 0) {
q.push(v);
}
}
}
return result.size() == n ? result : vector<int>{}; // 空 vector 表示失败
}
</int></int></vector></int>
容易被忽略的一点：函数签名里 const vector 是引用传参，避免邻接表拷贝开销；而 indeg 和 result 必须在函数内构造，生命周期可控。实际项目中若图结构复用频繁，建议把 indeg 缓存为成员变量。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
