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

#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;
}

#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;
}

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;
}