拓扑排序 c++算法实现

拓扑排序是一种常用的有向无环图（DAG）的排序算法，用于解决有向图中的依赖关系问题。其基本思想是通过不断删除入度为0的顶点，直到所有顶点都被删除或者发现存在环，从而确定一个有向图的拓扑序列。

C++实现拓扑排序的基本思路是使用一个队列来存储当前入度为0的顶点，并通过邻接表来记录每个顶点的入度和出度。具体步骤如下：

1. 初始化：将所有入度为0的顶点加入队列中。
2. 循环：不断从队列中取出一个顶点，将其邻接点的入度减1，如果减1后入度为0，则将其加入队列中。
3. 直到队列为空：如果队列为空时还有顶点的入度不为0，则说明存在环；否则，按照队列中的顺序输出拓扑序列。

以下是C++代码实现：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> topoSort(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> inDegree(n, 0);
    vector<int> res;
    queue<int> q;
    // 计算每个顶点的入度
    for (int i = 0; i < n; i++) {
        for (auto j : graph[i]) {
            inDegree[j]++;
        }
    }
    // 将所有入度为0的顶点加入队列
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    // 循环取出队列中的顶点，并更新其邻接点的入度
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        res.push_back(u);
        for (auto v : graph[u]) {
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
    // 如果存在入度不为0的顶点，则说明存在环
    if (res.size() != n) {
        res.clear();
    }
    return res;
}

int main() {
    vector<vector<int>> graph = {{1, 2}, {2, 3}, {4}, {3, 4}};
    vector<int> res = topoSort(graph);
    if (res.empty()) {
        cout << "存在环" << endl;
    } else {
        cout << "拓扑序列为：";
        for (auto x : res) {
            cout << x << " ";
        }
        cout << endl;
    }
    return 0;
}