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

Question

我的知识存在差距,但我不确定究竟在哪里.维基百科解释说,拓扑排序可以使用深度优先搜索来完成.但是我只看到了为树实现的深度优先搜索,其中拓扑排序是针对DAG的.

1. 树是DAG的特殊情况,其中边的隐含方向是从根节点向下
2. 用于拓扑排序的算法不是真正做DFS,只有很多类似的东西吗？

例如,拓扑排序可以处理断开连接的图形,其中DFS无法遍历节点而没有边缘连接它...可以吗？

Answer 1

因为当用于拓扑排序时,您在每个节点上都执行DFS .如果之前的DFS(彩色黑色)已经访问过其中一个孩子.然后它已被推入输出向量中,因此您已经完成了依赖性.

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

该算法以任意顺序循环遍历图的每个节点,启动深度优先搜索 ...

由于维基百科的文章有点令人困惑(在我看来),我会尝试更好地描述算法:

     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).一些其他拓扑排序算法需要在它们继续时(通过去除边缘)销毁图形.如果在排序后仍需要图形,则需要在运行toplogical排序之前复制图形.