拓扑排序必须基于有向无环图（DAG），否则无解；C++实现时若含环，算法可能失败或返回不完整结果；Kahn算法最易实现且天然支持环检测，是生产环境首选。
拓扑排序必须基于有向无环图（DAG），否则无解
拓扑排序本身不负责检测环，它只在图确定为 DAG 的前提下给出一个合法的顶点线性序列。C++ 中实现时，如果输入图含环，topological_sort 算法要么中途失败（如 DFS 回溯发现后向边），要么返回不完整结果（如 BFS 入度法中剩余节点无法入队）。实际使用前务必先做环检测，或把环检测逻辑集成进排序过程。
Kahn 算法（BFS + 入度统计）最易实现且天然支持环检测
这是生产环境首选：逻辑清晰、容易调试、能自然识别环（最终输出序列长度
-
in_degree[v]表示节点v的入度，初始为 0 - 遍历所有边
u → v，对每个v执行in_degree[v]++ - 将所有
in_degree[v] == 0的节点入队 - 每次出队一个节点
u，将其所有邻接点v的in_degree[v]--；若减为 0，则入队 - 结束时检查结果容器大小是否等于节点总数
#include <vector>
#include <queue>
#include <algorithm>
std::vector<int> kahnTopoSort(int n, const std::vector<std::vector<int>>& graph) {
std::vector<int> in_degree(n, 0);
for (int u = 0; u < n; ++u) {
for (int v : graph[u]) {
in_degree[v]++;
}
}
std::queue<int> q;
for (int i = 0; i < n; ++i) {
if (in_degree[i] == 0) q.push(i);
}
std::vector<int> result;
while (!q.empty()) {
int u = q.front(); q.pop();
result.push_back(u);
for (int v : graph[u]) {
if (--in_degree[v] == 0) {
q.push(v);
}
}
}
if (result.size() != n) return {}; // 含环，返回空 vector
return result;
}
DFS 实现需小心递归状态标记，避免误判环
DFS 版本更节省空间（不用队列），但状态管理稍复杂。必须区分三种节点状态：unvisited（未访问）、visiting（当前 DFS 路径中）、visited（已处理完毕）。仅当遇到 visiting 状态节点时才确认有环。
- 用
state[i]表示状态：0=unvisited，1=visiting，2=visited - 递归进入节点前设为
visiting，回溯前 push 到结果并设为visited - 若在
visiting状态下再次访问同一节点，立即返回 false（环存在） - 注意：结果是逆序生成的（DFS 回溯时加入），最后要
std::reverse
#include <vector>
#include <algorithm>
bool dfsVisit(int u, std::vector<int>& state,
const std::vector<std::vector<int>>& graph,
std::vector<int>& result) {
state[u] = 1; // visiting
for (int v : graph[u]) {
if (state[v] == 0) {
if (!dfsVisit(v, state, graph, result)) return false;
} else if (state[v] == 1) {
return false; // cycle detected
}
}
state[u] = 2;
result.push_back(u);
return true;
}
std::vector<int> dfsTopoSort(int n, const std::vector<std::vector<int>>& graph) {
std::vector<int> state(n, 0);
std::vector<int> result;
for (int i = 0; i < n; ++i) {
if (state[i] == 0) {
if (!dfsVisit(i, state, graph, result)) {
return {}; // cycle
}
}
}
std::reverse(result.begin(), result.end());
return result;
}
实际使用时要注意图表示与索引一致性
上面两个实现都假设节点编号为 0 到 n-1 的整数。如果你的图节点是字符串、指针或自定义 ID，必须先做离散化映射（如 std::unordered_map<:string int></:string>），否则无法直接使用 in_degree 数组或 state 数组。另外，graph 是邻接表形式：索引 u 对应从 u 出发的所有边终点列表；不是邻接矩阵，也不是边列表。
立即学习“C++免费学习笔记（深入）”；
性能上，Kahn 算法时间复杂度 O(V + E)，空间 O(V + E)；DFS 版本空间最坏 O(V)（递归栈），但常数略高。两者都可扩展支持多起点、输出所有可能拓扑序（需回溯+剪枝），但那属于进阶需求，基础场景用上述任一即可。
