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

Question

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

null