c++ 拓扑排序代码

C++中的拓扑排序是一种用于有向无环图（DAG）的排序算法，它可以确定图中节点的线性顺序，使得对于任意一对有向边 (u, v)，节点 u 在排序中都出现在节点 v 之前。

以下是一个简单的C++代码示例来实现拓扑排序：

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

using namespace std;

vector<int> topologicalSort(vector<vector<int>>& graph, vector<int>& inDegree) {
    int numCourses = graph.size();
    vector<int> result;
    queue<int> q;

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

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        result.push_back(curr);

        // 更新相邻节点的入度
        for (int neighbor : graph[curr]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // 如果结果中的节点数量不等于总节点数量，则存在环
    if (result.size() != numCourses) {
        result.clear(); // 清空结果
    }

    return result;
}

int main() {
    int numCourses = 4;
    vector<vector<int>> graph(numCourses);
    vector<int> inDegree(numCourses, 0);

    // 构建图和计算入度
    graph[1].push_back(0);
    inDegree[0]++;
    graph[2].push_back(1);
    inDegree[1]++;
    graph[3].push_back(1);
    inDegree[1]++;
    graph[3].push_back(2);
    inDegree[2]++;

    vector<int> result = topologicalSort(graph, inDegree);

    if (result.empty()) {
        cout << "存在环，无法进行拓扑排序" << endl;
    } else {
        cout << "拓扑排序结果：";
        for (int node : result) {
            cout << node << " ";
        }
        cout << endl;
    }

    return 0;
}

这段代码实现了一个简单的拓扑排序算法。首先，我们构建了一个有向图，并计算每个节点的入度。然后，我们使用队列来存储入度为0的节点，并依次将其出队并加入结果中。在出队的过程中，我们更新相邻节点的入度，并将入度变为0的节点加入队列。最后，如果结果中的节点数量不等于总节点数量，则说明存在环。