拓扑排序前必须检查有向图是否无环，否则结果错误；DFS法需用三态标记检测环，Kahn法通过剩余节点数判断环存在。
拓扑排序前必须检查有向图是否无环
直接上算法不检查环，结果可能完全错误——topological_sort 只对 DAG（有向无环图）有效。实际中，输入图常来自用户配置、依赖描述或代码分析，无法保证无环。用 DFS 实现时，需在递归中维护「当前路径」状态（如用 recStack 数组标记），一旦遇到正在递归中的节点，立刻报 "cycle detected"；用入度法（Kahn 算法）时，若最终输出顶点数小于图中顶点总数，说明存在剩余入度 > 0 的节点，即存在环。
Kahn 算法：用队列 + 入度数组模拟“逐层剥洋葱”
核心是统计每个节点的入度，把所有入度为 0 的节点扔进队列，每次取一个并删掉它指向的所有边（对应邻居入度减 1），新入度为 0 的再入队。注意几个实操细节：
-
indegree数组大小必须覆盖所有可能节点编号，建议用vector<int> indegree(n, 0)</int>，其中n是顶点总数，不能仅靠边列表推断 - 建图用
vector<vector>> graph(n)</vector>，添加边u → v时只执行graph[u].push_back(v)，别反了 - 队列选
queue<int></int>即可，不需要优先级；但若要求字典序最小拓扑序，得换priority_queue（小顶堆） - 性能上，时间复杂度稳定
O(V + E)，空间多存一个入度数组和队列，比 DFS 法更易调试
DFS 实现拓扑排序：后序遍历逆序即解
DFS 法本质是利用「递归返回顺序」反映节点依赖关系：只有当一个节点所有后继都访问完，它才被加入结果。关键陷阱在于：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 不能只靠
visited布尔数组——必须区分「未访问」「访问中（在当前 DFS 路径）」「已访问完成」三种状态，否则环检测失效 - 结果要反转：每次
dfs(u)返回前result.push_back(u)，最后对result调用reverse()；漏这步会得到逆拓扑序 - 图可能不连通，必须对每个未访问节点调用
dfs()，不能只从0开始 - 递归深度大时（比如万级节点链状图），可能栈溢出；生产环境建议改用显式栈模拟 DFS
两种实现的边界与兼容性差异
入度法（Kahn）和 DFS 法输出的拓扑序不一定相同，这是正常的——只要满足所有边 u → v 在序列中 u 出现在 v 前即可。但它们对输入的要求和行为不同：
立即学习“C++免费学习笔记（深入）”；
- Kahn 法天然支持多起点，且能自然检测环（剩余节点数 > 0）；DFS 法环检测靠递归栈状态，更底层但也更易写错
- 如果图用邻接表存储且边稀疏，两者性能接近；但若频繁增删边，Kahn 法需重算全部入度，而 DFS 法每次都要重跑
- C++ 中若节点 ID 不是连续整数（如字符串或负数），Kahn 法需哈希映射到索引，DFS 法可用
unordered_map<string, vector<string>>直接建图，灵活性略高 - 编译器优化下，Kahn 的循环+队列通常比递归 DFS 更快，尤其在开启
-O2时
真正容易被忽略的是：无论哪种实现，都默认图是「简单有向图」——不含自环（u → u）和重边。遇到自环，入度法会在初始化时就把该点入度设为 1，永远进不了队列；DFS 法会立刻在 recStack[u] == true 时触发环判定。预处理阶段应先过滤自环。
