拓扑排序要求图是有向无环图（DAG）；Kahn算法基于BFS和入度维护，初始将所有入度为0的节点入队，每次处理节点时更新其后继入度，若降为0则入队，最终结果长度不等于n说明存在环。
拓扑排序能跑通，前提是图有向无环（DAG）；Kahn 算法本质是 BFS + 入度维护，不是 DFS 的变种，别一上来就写递归。
为什么入度为 0 的节点必须先入队
拓扑序要求：所有边 u → v 中，u 必须排在 v 前面。所以只有当 v 的所有前驱（即所有指向它的节点）都已处理完，v 才能被加入序列——这等价于 v 的入度降为 0。Kahn 算法靠持续找入度为 0 的点来推进，不是靠“从某个起点深搜”，所以初始队列只包含当前入度为 0 的所有节点。
- 若图中存在环，最终队列会空但仍有节点未输出，此时可判定非 DAG
- 入度数组不能用
vector<int> indeg(n, 0)</int>就完事——必须遍历所有边显式累加，比如对每条u → v执行indeg[v]++ - 邻接表建议用
vector<vector>></vector>，不用map或unordered_map，避免常数开销和哈希冲突干扰 BFS 时序
queue<int></int> 里存的是节点索引，不是边或权值
BFS 过程中，queue 只承载待处理的、入度已清零的节点编号。每次出队一个节点 u，就扫描它所有后继 v，对每个 v 执行 indeg[v]--；若减后为 0，才把 v 入队。这里容易错写成 “把边入队” 或 “把 indeg[v] 入队”。
- 别用
priority_queue替代queue，除非你明确要字典序最小拓扑序（那是额外需求） - 出队后立即把
u推进结果vector，不要等到 BFS 结束再排序 - 如果图含多个连通分量，只要每个分量都是 DAG，算法仍有效；但若某分量有环，整个图就不是 DAG
完整可运行的 Kahn 核心逻辑（C++17）
以下代码省略输入解析，聚焦算法主干。假设节点编号为 0 到 n-1，graph 是邻接表：
立即学习“C++免费学习笔记（深入）”；
vector<int> topo_sort(int n, const vector<vector<int>>& graph) {
vector<int> indeg(n, 0);
for (int u = 0; u < n; ++u) {
for (int v : graph[u]) {
indeg[v]++;
}
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (indeg[i] == 0) q.push(i);
}
vector<int> res;
while (!q.empty()) {
int u = q.front(); q.pop();
res.push_back(u);
for (int v : graph[u]) {
if (--indeg[v] == 0) {
q.push(v);
}
}
}
if ((int)res.size() != n) return {}; // 有环，返回空 vector
return res;
}
注意：--indeg[v] == 0 是原子判断，别拆成两行（否则可能漏推）；返回空 vector 是常见错误信号，调用方应检查大小是否等于 n。
实际调试时最常卡住的三个点
不是算法逻辑错，而是数据准备或边界没对齐：
- 图用邻接表存，但输入给的是边列表（如
vector<pair>></pair>），忘了建graph就直接跑算法 → 结果全空 - 节点编号不连续（比如出现 1、3、7），却用
n = max_id + 1当尺寸，导致indeg数组越界或漏统计 → 出现未定义行为 - 把有向边
u → v错存为graph[v].push_back(u)（方向反了）→ 入度统计对象颠倒，结果完全乱序
拓扑序本身不唯一，但 Kahn 给出的一定是合法解；验证只需遍历结果中每对相邻位置 i ，检查是否存在边 <code>res[j] → res[i]——若有，说明实现肯定错了。
