拓扑排序必须在有向无环图（DAG）上进行，环存在则无解；c++标准库无内置实现，需手写DFS并用三态标记（0未访、1访问中、2已完成）检测环，逆后序入栈得结果。
拓扑排序的核心前提：必须是有向无环图（DAG）
如果图中存在环，topological sort 不存在——C++ 标准库不提供内置拓扑排序函数，必须手写。直接调用 std::sort 或基于比较的排序完全无效，因为边关系不是全序。先做环检测是必要步骤，否则结果不可靠。
用 DFS 实现拓扑排序（递归 + 状态标记）
常见错误是只用一个 visited 数组，导致无法区分「当前路径正在访问」和「已彻底处理完毕」。必须用三种状态：
-
0：未访问 -
1：正在当前 DFS 路径中（若再次遇到，说明有环） -
2：已访问完成（可安全加入结果）
逆后序（即 DFS 退出时压入栈）即为合法拓扑序。
#include #include using namespace std; vector topoSortDFS(const vector>& graph) { int n = graph.size(); vector state(n, 0); // 0=unvisited, 1=visiting, 2=done stack result; bool hasCycle = false; function dfs = [&](int u) { if (state[u] == 1) { hasCycle = true; return; } if (state[u] == 2) return; state[u] = 1; for (int v : graph[u]) { dfs(v); if (hasCycle) return; } state[u] = 2; result.push(u); }; for (int i = 0; i < n; ++i) { if (state[i] == 0) dfs(i); if (hasCycle) return {}; // 返回空表示失败 } vector ans; while (!result.empty()) { ans.push_back(result.top()); result.pop(); } return ans; } 用 BFS 实现拓扑排序（Kahn 算法）
更符合直觉：不断移除入度为 0 的节点，并更新邻居入度。关键点在于：
立即学习“C++免费学习笔记（深入）”；
- 必须预先计算每个节点的
indegree - 队列初始只含
indegree == 0的节点 - 最终结果长度 ≠ 图节点数 → 存在环
相比 DFS，Kahn 更易调试、天然支持多解（队列可用 std::queue 或 std::priority_queue 控制输出顺序），但需额外存储入度数组和队列。
#include #include using namespace std; vector topoSortKahn(const vector>& graph) { int n = graph.size(); vector indegree(n, 0); for (int u = 0; u < n; ++u) { for (int v : graph[u]) { indegree[v]++; } } queue q; for (int i = 0; i < n; ++i) { if (indegree[i] == 0) q.push(i); } vector ans; while (!q.empty()) { int u = q.front(); q.pop(); ans.push_back(u); for (int v : graph[u]) { indegree[v]--; if (indegree[v] == 0) q.push(v); } } return ans.size() == n ? ans : vector{}; // 有环则返回空 } 实际使用时最容易忽略的细节
图的节点编号是否从 0 连续？若输入是字符串或稀疏 ID（如 “A”, “task-3″），不能直接用 vector。得先做离散化映射：unordered_map。另外，边方向极易弄反——拓扑序要求「u → v」意味着 u 必须排在 v 前面，所以邻接表 graph[u] 应存的是 u 指向的节点，不是被指向的节点。
性能上，两种方法都是 O(V + E)，但 Kahn 的常数略大（需两次遍历建入度）；DFS 更省内存（无队列），但递归深度可能爆栈（对万级节点需手动改栈或转迭代 DFS）。