c++中如何实现拓扑排序_c++有向无环图拓扑排序算法

拓扑排序必须在有向无环图（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++免费学习笔记（深入）”；

神卷标书

神卷标书，专注于AI智能标书制作、管理与咨询服务，提供高效、专业的招投标解决方案。支持一站式标书生成、模板下载，助力企业轻松投标，提升中标率。

下载

• 必须预先计算每个节点的 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）。