C++有向无环图DAG类的构建

以下是一个简单的C++ DAG类的构建：

#include <iostream>
#include <vector>

using namespace std;

class DAG {
private:
    vector<vector<int>> adjList; // 存储图的邻接表
    vector<int> inDegree; // 存储每个节点的入度

public:
    // 构造函数
    DAG(int numNodes) {
        adjList.resize(numNodes);
        inDegree.resize(numNodes, 0);
    }

    // 添加一条有向边
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        inDegree[v]++;
    }

    // 拓扑排序
    vector<int> topologicalSort() {
        vector<int> result;
        vector<bool> visited(adjList.size(), false);

        // 找到所有入度为0的节点
        for (int i = 0; i < adjList.size(); i++) {
            if (inDegree[i] == 0 && !visited[i]) {
                visited[i] = true;
                result.push_back(i);

                // 更新相邻节点的入度
                for (int j = 0; j < adjList[i].size(); j++) {
                    int neighbor = adjList[i][j];
                    inDegree[neighbor]--;
                }

                // 重置i，从头开始找入度为0的节点
                i = -1;
            }
        }

        return result;
    }
};

int main() {
    DAG dag(6);

    dag.addEdge(0, 1);
    dag.addEdge(1, 2);
    dag.addEdge(1, 3);
    dag.addEdge(2, 4);
    dag.addEdge(3, 4);
    dag.addEdge(4, 5);

    vector<int> result = dag.topologicalSort();

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }

    return 0;
}

在上面的代码中，我们定义了一个DAG类来表示有向无环图，它包含两个成员变量：邻接表 `adjList` 和每个节点的入度 `inDegree`。我们可以使用 `addEdge` 方法向图中添加一条有向边，并使用 `topologicalSort` 方法执行拓扑排序来得到一个可行的执行顺序。