c++中如何实现拓扑排序_c++拓扑排序实现方法-C++-PHP中文网

c++中如何实现拓扑排序_c++拓扑排序实现方法

冰火之心

发布： 2025-09-26 17:23:01

原创

894人浏览过

拓扑排序用于有向无环图，确保每条边的起点在序列中位于终点之前。C++中常用Kahn算法和DFS方法实现：1. Kahn算法通过维护入度队列，依次输出入度为0的节点，更新邻接点入度，直至队列为空，若结果包含所有节点则排序成功，否则图含环；2. DFS方法对每个未访问节点进行深度优先搜索，在回溯时将节点压栈，最终出栈顺序即为拓扑序，过程中通过递归栈检测环。两种方法均可有效实现拓扑排序，Kahn更直观，DFS更贴近搜索本质。

c++中如何实现拓扑排序_c++拓扑排序实现方法

拓扑排序用于有向无环图（DAG），将图中所有顶点排成线性序列，使得对于每条有向边 (u, v)，u 在序列中都出现在 v 之前。C++ 中常用两种方法实现：基于入度的 Kahn 算法和基于 DFS 的方法。

1. Kahn 算法（基于入度）

Kahn 算法通过不断选择入度为 0 的节点加入结果序列，并删除其出边，更新邻接点的入度。

步骤：

计算每个节点的入度
将所有入度为 0 的节点加入队列
从队列取节点，加入结果，遍历其邻接点，入度减 1；若减为 0 则入队
重复直到队列为空
若结果中节点数等于总节点数，则存在拓扑序；否则图中有环

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> topoSortKahn(int n, vector<vector<int>>& adj) {
    vector<int> indegree(n, 0);
    
    // 计算入度
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) {
            indegree[v]++;
        }
    }

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

    vector<int> result;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);

        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    if (result.size() != n) {
        cout << "图中存在环，无法进行拓扑排序\n";
        return {};
    }

    return result;
}

登录后复制

2. DFS 方法（基于后序遍历）

利用 DFS 遍历图，记录节点的“完成时间”，完成后按逆序输出即为拓扑序。

绘ai

ai绘图提示词免费分享

153

查看详情

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

思路：

对每个未访问的节点进行 DFS
递归访问其所有邻接点后，将当前节点压入栈
最后栈中元素从顶到底即为拓扑序

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

bool dfs(int u, vector<bool>& visited, vector<bool>& recStack,
         stack<int>& st, vector<vector<int>>& adj) {
    if (!visited[u]) {
        visited[u] = true;
        recStack[u] = true;

        for (int v : adj[u]) {
            if (!visited[v] && dfs(v, visited, recStack, st, adj))
                return true;
            if (recStack[v])
                return true; // 发现环
        }
    }
    recStack[u] = false;
    st.push(u);
    return false;
}

vector<int> topoSortDFS(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    vector<bool> recStack(n, false);
    stack<int> st;

    for (int i = 0; i < n; i++) {
        if (!visited[i] && dfs(i, visited, recStack, st, adj)) {
            cout << "图中存在环\n";
            return {};
        }
    }

    vector<int> result;
    while (!st.empty()) {
        result.push_back(st.top());
        st.pop();
    }
    return result;
}

登录后复制

3. 使用示例

假设图有 6 个节点，边为：0→1, 0→2, 1→3, 2→3, 3→4, 4→5

int main() {
    int n = 6;
    vector<vector<int>> adj(n);

    // 添加边
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(3);
    adj[3].push_back(4);
    adj[4].push_back(5);

    vector<int> order = topoSortKahn(n, adj);
    // 或者使用 topoSortDFS(n, adj)

    if (!order.empty()) {
        cout << "拓扑排序结果：";
        for (int x : order) {
            cout << x << " ";
        }
        cout << endl;
    }

    return 0;
}

登录后复制

基本上就这些。Kahn 算法更直观，适合理解入度变化；DFS 方法更贴近搜索本质，适合检测环的同时构造顺序。根据实际场景选择即可。

以上就是c++++中如何实现拓扑排序_c++拓扑排序实现方法的详细内容，更多请关注php中文网其它相关文章！