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

#include 
#include 
#include 
using namespace std;

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

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

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

#include 
#include 
#include 
using namespace std;

bool dfs(int u, vector& visited, vector& recStack,
         stack& st, vector>& 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 topoSortDFS(int n, vector>& adj) {
    vector visited(n, false);
    vector recStack(n, false);
    stack st;

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

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

int main() {
    int n = 6;
    vector> 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 order = topoSortKahn(n, adj);
    // 或者使用 topoSortDFS(n, adj)

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

    return 0;
}