为什么这种基于 DFS 的拓扑排序算法有效？

Question

这是我从 this competitive programming resource 中提取的算法。

int n; // number of vertices
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> ans;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
    ans.push_back(v);
}

void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
    reverse(ans.begin(), ans.end());
}

该算法如何避免将顶点添加到具有传入有向边的拓扑排序集合中？例如，for 循环检查的第一个顶点（本例中为 0）具有来自顶点 (1) 的传入有向边。在首先确保 (1) 已输出之前，是什么阻止该算法输出 (0)？

Answer 1

它正在反向构建输出向量。如果有从顶点 (1) 到顶点 (0) 的传入有向边，您希望在 (1) 之前输出 (0)。

请注意，dfs(int v) 仅在递归到其所有后代后才调用 ans.push_back(v)。这确保 v 之后的任何内容都将在 v 之前添加到输出向量中。在 dfs(0) returns 之后不是 visited[] 的任何内容要么与 0 或其后代无关（因此可以稍后添加），要么在它们之前（因此应该稍后添加） .

Answer 2

据我所知，DFS 方法要求图形没有任何循环。如果图确实有循环，DFS 将不会检测到它并给出错误的结果。如果图没有循环，DFS 将起作用。除了 DFS 之外，用于查找拓扑排序的某些其他算法可以检测循环并在任何循环存在时正确地给出错误，因为拓扑排序对于具有循环的图是不可能的。所以，这是一个非常好的问题。

为什么这种基于 DFS 的拓扑排序算法有效？

Why does this DFS-based topological sort algorithm work?

algorithm

topological-sort