c++怎么实现一个拓扑排序_c++拓扑排序算法实现与思路

拓扑排序用于有向无环图，通过入度法或DFS法生成线性序列。1. 入度法每次选入度为0的节点，更新邻接点入度，直至处理所有节点或发现环。2. DFS法利用深度优先搜索记录完成时间，回溯时加入结果并反转，通过状态标记检测环。两种方法时间复杂度均为O(V+E)，入度法直观易懂，DFS法更易扩展。

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

1. 入度法（Kahn 算法）

思路是每次选择入度为 0 的节点加入结果序列，并删除该节点的所有出边，更新其邻居的入度。重复此过程直到处理完所有节点或发现环。

• 统计每个节点的入度。
• 将所有入度为 0 的节点加入队列。
• 从队列取节点，加入结果，遍历其邻接节点，入度减一；若减为 0，则加入队列。
• 若结果序列长度等于节点数，则排序成功；否则存在环。

代码实现：

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

vector<int> topologicalSort(int n, vector<vector<int>>& edges) {
    vector<int> indegree(n, 0);
    vector<vector<int>> graph(n);
    
    // 建图并统计入度
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
        indegree[e[1]]++;
    }
    
    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 : graph[u]) {
            if (--indegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    if (result.size() != n) {
        return {}; // 存在环
    }
    return result;
}

2. DFS 法（深度优先搜索）

通过 DFS 遍历图，记录节点的“完成时间”——即回溯时将节点加入结果。最后反转结果即得拓扑序。需用状态数组标记节点是否访问、是否在当前递归栈中以检测环。

小微助手

微信推出的一款专注于提升桌面效率的助手型AI工具

下载

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

• 0：未访问
• 1：正在访问（在递归栈中）
• 2：已访问完毕

代码实现：

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

bool dfs(int u, vector<int>& status, vector<vector<int>>& graph, vector<int>& result) {
    status[u] = 1; // 正在访问
    for (int v : graph[u]) {
        if (status[v] == 1) return false; // 发现环
        if (status[v] == 0) {
            if (!dfs(v, status, graph, result)) return false;
        }
    }
    status[u] = 2;
    result.push_back(u);
    return true;
}

vector<int> topologicalSortDFS(int n, vector<vector<int>>& edges) {
    vector<vector<int>> graph(n);
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
    }
    
    vector<int> status(n, 0); // 0:未访问, 1:访问中, 2:已完成
    vector<int> result;
    
    for (int i = 0; i < n; ++i) {
        if (status[i] == 0) {
            if (!dfs(i, status, graph, result)) {
                return {}; // 有环
            }
        }
    }
    
    reverse(result.begin(), result.end());
    return result;
}

使用示例

假设我们有 4 个节点，边为：0→1, 0→2, 1→3, 2→3

int main() {
    int n = 4;
    vector<vector<int>> edges = {{0,1}, {0,2}, {1,3}, {2,3}};
    
    auto res = topologicalSort(n, edges);
    // 或者使用 topologicalSortDFS
    
    if (res.empty()) {
        cout << "图中有环" << endl;
    } else {
        for (int x : res) cout << x << " ";
        cout << endl; // 可能输出：0 1 2 3
    }
    return 0;
}