kahn算法是c++中稳定、可检测环的拓扑排序实现，需先统计入度并用bfs：初始化时将入度为0的节点入队，每次取队首节点加入结果并更新邻接点入度，若最终序列长度小于节点数则存在环。
拓扑排序在 C++ 中不能只靠 DFS 递归模拟来“假装跑通”——入度统计 + BFS（Kahn 算法）才是生产环境真正稳定、可检测环、易调试的实现方式。
为什么必须先统计每个节点的入度
入度为 0 是启动拓扑排序的唯一合法起点。不显式维护 indegree 数组，就无法在 O(1) 时间内判断哪个节点当前可加入队列；DFS 版本隐式依赖调用栈和回溯标记，一旦图含环或数据规模大，极易栈溢出或漏判。
实操建议：
- 用
vector<int></int>存储每个节点的入度，下标即节点编号（假设节点编号为 0 ~ n-1） - 建图时每添加一条边
u → v，立刻执行indegree[v]++ - 初始化队列前，遍历所有节点，把
indegree[i] == 0的i入队 - 别用 map 或 unordered_map 存入度——除非节点编号稀疏且极大，否则纯属增加常数开销和哈希冲突风险
用 queue 实现 BFS 拓扑排序的核心逻辑
这是 Kahn 算法的骨架，关键在于“删边”动作必须同步更新入度，并检查新产生的入度为 0 的节点。
常见错误现象：queue 为空但结果序列长度小于节点总数 → 图中存在环，应提前返回失败。
实操建议：
- 使用
queue<int></int>（非priority_queue），除非你明确需要字典序最小的拓扑序 - 每次从队首取节点
u，将其加入结果topo向量 - 遍历
graph[u]中所有邻接点v，执行indegree[v]--；若此时indegree[v] == 0，立即将v入队 - 循环结束后检查
topo.size() == n，不等则说明有环，返回空vector
邻接表怎么建才不踩内存与性能坑
邻接表是图的标准表示，但 C++ 中容易因类型或初始化方式引入越界、重复 push 或缓存不友好问题。
使用场景：适用于大多数稀疏有向图（边数远小于节点数平方）
实操建议：
- 统一用
vector<vector>></vector>，而非vector<list>></list>——vector连续内存，遍历时 CPU 缓存命中率高 - 构造时预分配容量：
graph.resize(n); for (int i = 0; i （按平均出度预估） - 加边函数写成内联或直接展开，避免函数调用开销：
graph[u].push_back(v); - 不要在 BFS 过程中修改
graph结构（如erase）——只需改入度，图结构只读即可
完整可运行片段（无环检测版本）
下面是最小可用代码，去掉了异常处理和输入解析，聚焦核心逻辑：
vector<int> topo_sort(int n, const vector<vector>>& edges) {
vector<vector>> graph(n);
vector<int> indegree(n, 0);
for (const auto& e : edges) {
int u = e[0], v = e[1];
graph[u].push_back(v);
indegree[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]) {
indegree[v]--;
if (indegree[v] == 0) q.push(v);
}
}
return topo.size() == n ? topo : vector<int>(); // 返回空表示有环
}
</int></int></int></vector></vector></int>
注意：实际项目中，节点编号可能不连续或从 1 开始，这时需做映射或调整 indegree 和 graph 大小；而环检测逻辑一旦被省略，后续依赖该序列的流程（如任务调度）就会静默失败——这点比算法本身更值得盯紧。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
