algorithm - 为什么这种基于 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) 返回后未 visited[] 的任何内容要么与 0 或其后代无关(因此可以稍后添加)，要么在它们之前(因此应该稍后添加)。