如果拓扑排序使用 DFS，它如何在断开连接的图上成功？

Question

我的知识有差距，但我不确定具体在哪里。拓扑排序可以使用深度优先搜索来完成，如wikipedia explains。但是我只看到深度优先搜索是针对树实现的，而拓扑排序是针对 DAG 的。

树是 DAG 的特例，其中边的隐含方向是从根节点向下
用于拓扑排序的算法不是真正的DFS，只是很像吗？

例如，拓扑排序可以处理断开连接的图，因为 DFS 无法遍历没有边连接的节点...可以吗？

Answer 1

因为当用于拓扑排序时，您会在每个节点上执行 DFS。如果 children 之一已经被之前的 DFS 访问过（黑色）。然后它已经被推入输出向量，所以你的依赖已经完成。

引用你的link（强调我的）：

The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search ...

由于维基百科文章有点令人困惑（在我看来）我会尽量更好地描述算法：

     V: set of vertices
     E: set of edges
     E.adj(v): set of vertices adjacent to vertex v

 0 function topological_sort(V,E):
 1   for v in V:
 2     paint v white
 3
 4   for v in V:
 5     if v is white:
 6       dfs(v)

 7 function dfs(v):
 8   paint v grey
 9   for child in E.adj(v)
10     if child is white:
11       dfs(child)
12   paint v black
13   push v to output

我们可以很容易地计算复杂度：

我们为每个顶点绘制一次白色、灰色和黑色的顶点：O(V)
我们检查每个顶点一次 5 行的顶点颜色：O(V)
我们检查每条边线 10 处顶点的颜色：O(E)
我们将顶点推送到第 13 行输出，每个顶点一次：O(V)

所以最终的复杂度是：O(V+E)。效率很高。

该算法的优势之一是它不需要修改输入图。我们可以通过大小为 O(V) 的临时哈希表轻松实现着色。其他一些拓扑排序算法需要在进行时销毁图（通过删除边）。这将需要在运行拓扑排序之前复制图表，如果您仍然需要图表在排序之后。

Answer 2

您可能希望尝试向图中添加一个新的 "source" 节点，并使用有向边将其与每个其他节点连接起来。然后从这个新节点开始你的search/traverse。这种方法可能适合也可能不适合您的需要。

如果拓扑排序使用 DFS，它如何在断开连接的图上成功？

If topological sort uses DFS, how can it succeed on disconnected graphs?

algorithm

graph

depth-first-search

topological-sort