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

2 回答

• 0

  因为当用于拓扑排序时，您在 every 节点上执行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排序之前复制图形 .

  回复于 2024-04-27T21:54:02+08:00
• 11

  您可能希望尝试向图表添加新的“源”节点，并使用有向边连接每个其他节点 . 然后从这个新节点开始搜索/遍历 . 这种方法可能适合也可能不适合您的需求 .

  回复于 2024-04-27T21:54:02+08:00