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

Question

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

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

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

Answer 1

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

引用你的链接(强调我的):

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) 的临时哈希表轻松实现着色。其他一些拓扑排序算法需要在进行时销毁图(通过删除边)。如果在排序之后您仍然需要图表，这将需要在运行拓扑排序之前复制图表。