C++如何实现拓扑排序-C++-PHP中文网

拓扑排序必须先检测环，仅适用于有向无环图（dag）；dfs法用三色标记判环并逆序记录节点，bfs法（kahn算法）通过入度为0入队及最终结果长度判环，更直观易实现。

c++如何实现拓扑排序

拓扑排序需要先判断图是否有环

拓扑排序只对有向无环图（DAG）有效，如果图含环，topological_sort 无法给出合法序列。实际写代码时，不能跳过环检测——否则可能得到错误结果或无限循环。

常见做法是：在 DFS 或 BFS 过程中同步记录节点状态。比如用三个值标记节点：unvisited、visiting（当前递归栈中）、visited。一旦遇到 visiting 状态的邻接点，就说明成环。

DFS 实现时，回溯前把节点设为 visited；进入递归前设为 visiting
BFS 实现（Kahn 算法）中，若最终加入结果的节点数 != 总节点数，说明有环
注意：输入图可能不连通，需遍历所有节点启动 DFS 或检查所有入度为 0 的起点

Kahn 算法更易实现且天然支持环检测

相比 DFS 版本，Kahn 算法用队列和入度数组，逻辑更直白，也更容易调试。它模拟“不断剥离没有前置依赖的节点”的过程。

关键步骤：

统计每个节点的入度，把所有 in_degree[i] == 0 的节点入队
每次取出队首 u，加入结果 vector，并遍历其所有邻接点 v，执行 in_degree[v]--；若减为 0，立即入队
算法结束时，检查 result.size() == N，否则存在环

示例片段（假设节点编号 0 ~ N-1，graph 是邻接表）：

vector<int> topological_sort(const vector<vector>>& graph) {
    int n = graph.size();
    vector<int> in_degree(n, 0);
    for (int u = 0; u  q;
    for (int i = 0; i  res;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        res.push_back(u);
        for (int v : graph[u]) {
            if (--in_degree[v] == 0) q.push(v);
        }
    }
    return res.size() == n ? res : vector<int>{}; // 返回空表示有环
}</int></int></vector></int>

DFS 版本要注意递归顺序和结果翻转

DFS 拓扑排序本质是按“离开时间逆序”排列节点，所以必须在 dfs(u) 所有邻接点处理完后，才把 u 压入结果。这意味着最终结果要反转，或者用 deque 前插。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

容易出错的地方：

误在进入 dfs(u) 时就 push，导致顺序错乱
忘记对每个未访问节点调用 DFS（图不连通时漏节点）
状态数组没初始化或复用错误，多组测试时出问题

简写示意（仅核心逻辑）：

void dfs(int u, const vector<vector>>& graph, vector<int>& state, vector<int>& res) {
    state[u] = 1; // visiting
    for (int v : graph[u]) {
        if (state[v] == 0) dfs(v, graph, state, res);
        else if (state[v] == 1) throw runtime_error("cycle detected");
    }
    state[u] = 2; // visited
    res.push_back(u); // 离开时记录
}
// 调用后需 reverse(res.begin(), res.end())
</int></int></vector>

实际使用时优先考虑标准容器与索引稳定性

如果你的节点不是简单整数（比如是字符串、指针或自定义 ID），别硬套 0~N-1 下标。建议先做映射：map<string int> id_map</string>，统一转成整数索引再建图；否则 vector<vector>></vector> 无法直接使用。

另外注意：

vector<vector>></vector> 存稀疏图可能浪费内存，但访问快；超大图可改用 vector<unordered_set>></unordered_set> 去重边
多次调用拓扑排序时，避免重复构造图结构——把图和入度数组作为类成员缓存
STL 没有内置拓扑排序函数，<algorithm></algorithm> 里没有 topological_sort，别白找

真正卡住的往往不是算法逻辑，而是节点标识混乱、环检测漏判、或对空图/单点图的边界没处理。