有向图的拓扑序列C++

有向图的拓扑排序是一种将图中顶点按照依赖关系线性排列的方式，如果存在一条从u到v的有向边，那么在结果序列中，u会出现在v之前。这种排序通常应用于任务调度、数据流程分析等场景，保证了所有依赖于其他任务的任务都在其依赖完成之后。

在C++中，你可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来寻找拓扑序列。这里提供一种基于DFS的简单实现：

#include <vector>
#include <queue>

// 图结构定义
using namespace std;
struct Edge {
    int from, to;
};

class Graph {
private:
    vector<vector<int>> adj; // 存储邻接表

public:
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    bool isSafe(vector<int>& topo, int node) { // 检查是否存在环
        for (int i : adj[node])
            if (topo[i] > topo[node])
                return false;
        return true;
    }

    vector<int> topologicalSort() {
        vector<int> topo(adj.size(), 0); // 初始化拓扑序列表
        queue<int> q;
        int count = 0;

        for (int i = 0; i < adj.size(); ++i)
            if (!adj[i].size()) // 找到入度为0的节点（开始）
                q.push(i), topo[i] = ++count;

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

            if (isSafe(topo, node)) { // 如果当前节点安全，则更新其后续节点
                for (int neighbor : adj[node]) {
                    topo[neighbor]++;
                    if (topo[neighbor] == 1) // 当前节点的邻接节点入度变为0，加入队列
                        q.push(neighbor);
                }
            }
        }

        // 返回拓扑序列
        vector<int> result;
        for (int i = 0; i < adj.size(); ++i)
            if (topo[i] > 0)
                result.push_back(i);

        return result;
    }
};