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

Question

这是我从这个竞争性编程资源中提取的算法。

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或其后代无关(因此可以在以后添加(，要么在它们之前(因此应该稍后添加(。

Answer 2

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