C++如何实现拓扑排序_C++有向无环图(DAG)的拓扑排序算法

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++如何实现拓扑排序_C++有向无环图(DAG)的拓扑排序算法

2025-11-22

浏览次数：次

返回列表

拓扑排序用于有向无环图（DAG），通过入度法或DFS法将顶点排成线性序列，使得每条有向边(u,v)中u在v之前。1. 入度法（Kahn算法）基于贪心思想，计算各节点入度，将入度为0的节点入队，依次出队并更新邻接点入度，直至队列为空；若结果序列长度等于节点数，则存在有效拓扑排序，否则图含环。2. DFS法通过深度优先搜索，在回溯时将节点加入结果序列，需标记节点状态（未访问、访问中、已完成），若遍历中遇到“正在访问”的节点则说明有环，最后反转结果序列得到拓扑序。两种方法时间复杂度均为O(V+E)，Kahn算法逻辑清晰适合初学者，DFS法适用于熟悉递归和状态标记的场景。正确性依赖于判断是否存在环，是实现拓扑排序的关键前提。

c++如何实现拓扑排序_c++有向无环图(dag)的拓扑排序算法

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

使用入度法（Kahn 算法）实现拓扑排序

该方法基于贪心思想：每次选择入度为 0 的节点加入结果序列，并删除其出边，更新邻接点的入度。

步骤如下：

计算每个节点的入度
将所有入度为 0 的节点加入队列
从队列中取出节点，加入结果序列
遍历该节点的所有邻接点，将其入度减 1；若入度变为 0，则加入队列
重复直到队列为空

如果最终结果序列长度等于节点数，则存在有效拓扑排序；否则图中有环。

// 示例代码：Kahn 算法实现拓扑排序

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

vector<int> topologicalSort(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;
    // 将入度为 0 的节点入队
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

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

        // 遍历 u 的所有邻接点
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 检查是否存在环
    if (topo.size() != n) {
        return {}; // 说明图中有环
    }

    return topo;
}

使用 DFS 实现拓扑排序

DFS 方法通过深度优先搜索，在回溯时将节点加入结果序列（逆序）。需要标记节点状态：未访问、正在访问、已完成。

CA.LA

第一款时尚产品在线设计平台，服装设计系统

94 查看详情 CA.LA

核心逻辑：

对每个未访问节点调用 DFS
在 DFS 中，先标记当前节点为“正在访问”
递归访问所有邻接点；若遇到“正在访问”的节点，说明有环
回溯前将节点加入结果数组
最后反转数组得到拓扑序列

// 示例代码：DFS 实现拓扑排序

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

bool dfs(int u, vector<int>& state, vector<vector<int>>& adj, vector<int>& result) {
    state[u] = 1; // 正在访问

    for (int v : adj[u]) {
        if (state[v] == 1) return false; // 发现环
        if (state[v] == 0) {
            if (!dfs(v, state, adj, result)) return false;
        }
    }

    state[u] = 2; // 已完成
    result.push_back(u);
    return true;
}

vector<int> topologicalSortDFS(int n, vector<vector<int>>& adj) {
    vector<int> state(n, 0); // 0:未访问, 1:访问中, 2:已完成
    vector<int> result;

    for (int i = 0; i < n; i++) {
        if (state[i] == 0) {
            if (!dfs(i, state, adj, result)) {
                return {}; // 存在环
            }
        }
    }

    reverse(result.begin(), result.end());
    return result;
}

完整测试示例

假设有一个包含 6 个节点的 DAG，边为：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 = topologicalSort(n, adj);
    // 或者使用：topologicalSortDFS(n, adj)

    if (order.empty()) {
        cout << "图中存在环，无法进行拓扑排序\n";
    } else {
        cout << "拓扑排序结果：";
        for (int x : order) {
            cout << x << " ";
        }
        cout << endl;
    }

    return 0;
}

输出可能为：0 1 2 3 4 5，具体顺序取决于算法实现和图结构。

基本上就这些。两种方法时间复杂度都是 O(V + E)，推荐初学者使用 Kahn 算法，逻辑清晰且易于理解。DFS 方法适合已有 DFS 基础的场景。注意判断环的存在是拓扑排序的关键前提。

以上就是C++如何实现拓扑排序_C++有向无环图(DAG)的拓扑排序算法的详细内容，更多请关注其它相关文章！

# c++ # 网站优化关键词排名监控 # 谷城网站推广途径 # 都是 # 为空 # 时将 # 每条 # 如何实现 # 游戏开发 # 遍历 # 图中 # 两种 # 递归 # 排序算法 # stream # ios # ai # 郑州企业推广营销 # 栾城区网站建设广告 # 渭南seo外包服务 # 房地产视频关键词排名 # seo优化交流排名 # 嵩明制造业营销推广公司 # 安宁庄商城网站建设 # 辽宁网站建设口碑好