拓扑排序必须基于有向无环图（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<:vector>>& graph) {
std::vector<int> in_degree(n, 0);
for (int u = 0; u q;
for (int i = 0; i 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;
}
</int></:vector></int></algorithm></queue></vector>
DFS 实现需小心递归状态标记，避免误判环
DFS 版本更节省空间（不用队列），但状态管理稍复杂。必须区分三种节点状态：unvisited（未访问）、visiting（当前 DFS 路径中）、visited（已处理完毕）。仅当遇到 visiting 状态节点时才确认有环。
- 用
state[i]表示状态：0=unvisited，1=visiting，2=visited - 递归进入节点前设为
visiting，回溯前 push 到结果并设为visited - 若在
visiting状态下再次访问同一节点，立即返回 false（环存在） - 注意：结果是逆序生成的（DFS 回溯时加入），最后要
std::reverse
0
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
