使用DFS由二维空间构成的有向图的拓扑排序

Question

这是我在int_main中创建有向图的方式：

int edges, vertices;

    cout << "Number of edges" << endl;
    cin >> edges;

    cout << "Number of verticles" << endl;
    cin >> vertices;

    vector<vector<int>> graph(vertices); 

    int a, b;
    for (int i = 0; i < edges; i++) {
        cin >> a >> b; 
        graph[a].push_back(b);
    }

我的任务是使用DFS对有向图进行拓扑排序。这是我尝试实现DFS和拓扑排序的方法：

void dfs(vector<vector<int>> &graph, vector<bool> &used, int nodeIndex) {
    used[nodeIndex] = true;
    for (auto i : graph[nodeIndex]) {
        if (!used[i])
            dfs(graph, used, i);
    }
}

void topologicalSort(vector<vector<int>> &graph, vector<bool> &used, int nodeIndex) {
    vector<int> answer;
    for (int i = 0; i < graph.size(); i++)
        used[nodeIndex] = false;
    answer.clear();
    for (int i = 0; i < graph.size(); ++i)
        if (!used[i])
            dfs(graph, used, i);
    reverse(answer.begin(), answer.end());
}

但是拓扑排序似乎无效，并且我不知道该怎么办才能解决此问题。

Answer 1

您需要在参数中传递答案，并在最后传递push_back(nodeIndex)：

void dfs(vector<vector<int>> &graph, vector<bool> &used, int nodeIndex, vector<int> &answer) {
    used[nodeIndex] = true;
    for (auto i : graph[nodeIndex]) {
        if (!used[i])
            dfs(graph, used, i);
    }
    answer.push_back(nodeIndex);
}