c++中如何实现拓扑排序_c++有向无环图排序算法代码【详解】

拓扑排序必须基于有向无环图（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 
#include 
#include 

std::vector kahnTopoSort(int n, const std::vector>& graph) {
    std::vector in_degree(n, 0);
    for (int u = 0; u < n; ++u) {
        for (int v : graph[u]) {
            in_degree[v]++;
        }
    }

    std::queue q;
    for (int i = 0; i < n; ++i) {
        if (in_degree[i] == 0) q.push(i);
    }

    std::vector 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 
#include 

bool dfsVisit(int u, std::vector& state,
              const std::vector>& graph,
              std::vector& 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 dfsTopoSort(int n, const std::vector>& graph) {
    std::vector state(n, 0);
    std::vector 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>），否则无法直接使用 in_degree 数组或 state 数组。另外，graph 是邻接表形式：索引 u 对应从 u 出发的所有边终点列表；不是邻接矩阵，也不是边列表。

Remove.bg

AI在线抠图软件，图片去除背景

下载

立即学习“C++免费学习笔记（深入）”；

性能上，Kahn 算法时间复杂度 O(V + E)，空间 O(V + E)；DFS 版本空间最坏 O(V)（递归栈），但常数略高。两者都可扩展支持多起点、输出所有可能拓扑序（需回溯+剪枝），但那属于进阶需求，基础场景用上述任一即可。