数据结构c++拓扑排序

拓扑排序是一种基于有向无环图（DAG）的算法，用于对图中的节点进行排序。在进行拓扑排序时，我们需要先确定一个起点，然后按照一定的规则依次访问其他节点，直到所有节点都被访问过为止。具体实现方法如下：

1. 统计每个节点的入度（即有多少个节点指向该节点）。
2. 将所有入度为0的节点加入一个队列中。
3. 从队列中取出一个节点，将其所有邻接节点的入度减1。
4. 如果某个邻接节点的入度变为0，则将其加入队列中。
5. 重复步骤3和4，直到队列为空为止。

实现代码如下：

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

using namespace std;

void topoSort(vector<vector<int>>& graph, vector<int>& indegree) {
    queue<int> q;
    int n = graph.size();

    // 将所有入度为0的节点加入队列
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        cout << u << " ";

        // 将u的邻接节点的入度减1
        for (int v : graph[u]) {
            indegree[v]--;
            // 如果某个邻接节点的入度变为0，则加入队列中
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> graph(n);
    vector<int> indegree(n, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        indegree[v]++;
    }

    topoSort(graph, indegree);

    return 0;
}

在这个实现中，我们用了一个vector<vector<int>>来表示有向图，其中graph[u]表示节点u的邻接节点集合。我们还用了一个vector<int>来表示每个节点的入度。在统计入度时，我们遍历所有边，对于每条边 (u, v)，将节点v的入度加1。最后，我们调用topoSort函数进行拓扑排序，输出排序结果即可。