为什么DFS而不是BFS在图表中查找循环

DFS主要用于在图中find一个循环,而不是BFS。 有什么理由? 在遍历树/图时,两者都可以find一个节点是否已经被访问过。

深度优先search比宽度优先search更有效率,因为您可以更快地回溯。 如果使用调用堆栈,实现起来也比较容易,但是这依赖于最长的path而不是溢出堆栈。

此外,如果您的graphics是直接指向的,那么您不仅要记住是否已经访问了一个节点,还要知道如何到达那里。 否则,你可能会认为你已经find了一个循环,但实际上你所拥有的只是两条独立的pathA-> B,但并不意味着有一条pathB-> A。 例如,

如果你从0开始执行BFS,它会检测到循环存在,但实际上没有循环。

通过深度优先search,您可以将节点标记为随着您的下降而被访问,并在您回溯时取消标记。 查看有关此algorithm性能改进的注释。

对于在有向图中检测周期的最佳algorithm,你可以看看Tarjan的algorithm 。

  1. DFS更容易实现
  2. 一旦DFS发现一个周期,堆栈将包含形成周期的节点。 BFS也是如此,所以如果你想打印find的循环,则需要做额外的工作。 这使得DFS更加方便。

如果图是无向的,那么BFS可能是合理的(我的客人在展示一个使用BFS的有效algorithm,它将在有向图中报告周期!),其中每个“交叉边”定义一个周期。 如果交叉边是{v1, v2} ,并且包含这些节点的根(在BFS树中)是r ,则循环是r ~ v1 - v2 ~ r~是path, -单个边)。这可以像在DFS中一样轻松地报告。

使用BFS的唯一原因是,如果您知道您的(无向)图将有长path和小path覆盖(换句话说,深和窄)。 在这种情况下,BFS比DFS的堆栈(当然两者仍然是线性的)要求其队列的内存要less一些。

在所有其他情况下,DFS显然是赢家。 它适用于有向图和无向图,并且报告周期是微不足道的 – 只要将任何后沿连接到从祖先到后代的path,就可以获得循环。 总而言之,这个问题比BFS更好,更实用。

如果你在树上的一个随机点上放置一个循环,DFS将会覆盖大约一半的树,并且在循环中已经遍历的时间的一半,平均可以在树的其余部分find它的一半),所以它将平均评估约0.5 * 0.5 + 0.5 * 0.75 = 0.625的树。

如果将一个循环放置在树中的一个随机点上,那么只有当BFS在该深度处对树的层进行评估时,BFS才会倾向于进入循环。 因此,通常最终不得不评估一个平衡二叉树的叶子,这通常会导致对更多的树进行评估。 特别是,3/4的时间至less有两个链接中的一个出现在树的叶子,在这些情况下,你必须平均评估树的3/4(如果有一个链接)或7 / (如果有两个),所以你已经达到了search1/2 * 3/4 + 1/4 * 7/8 =(7 + 12)/ 32 = 21/32 = 0.656 …甚至没有增加search具有从叶节点附加的周期的树的成本。

另外,DFS比BFS更容易实现。 所以这是一个使用,除非你知道一些关于你的周期(例如周期可能接近你search的根源,在这一点上BFS给你一个优势)。

BFS不会在有向图中寻找周期。 考虑A-> B和A-> C-> B作为图中从A到B的path。 BFS将会沿着B被访问的path之一走过去。 当继续前进下一个path时,将会说已标记的节点B已被再次find,因此有一个循环。 显然这里没有周期。

为了certificate一个图是循环的,你只需要certificate它有一个循环(直接或间接指向自己的边)。

在DFS中,我们每次取一个顶点并检查它是否有循环。 只要find一个循环,我们可以省略检查其他顶点。

在BFS中,我们需要同时跟踪许多顶点边缘,而不是最终发现它是否有循环。 随着graphics大小的增加,与DFS相比,BFS需要更多的空间,计算和时间。

如果你正在谈论recursion或者迭代实现,那么这取决于它。

recursion-DFS访问每个节点两次。 迭代-BFS访问每个节点一次。

如果要检测循环,则需要在添加邻接点之前和之后调查节点 – 无论是在节点上“启动”还是在节点“完成”时。

这需要在迭代BFS中做更多的工作,所以大多数人selectrecursion-DFS。

请注意,迭代DFS与std :: stack的简单实现具有与迭代BFS相同的问题。 在这种情况下,您需要将虚拟元素放置到堆栈中以跟踪何时“完成”在节点上工作。

请参阅此答案,了解有关迭代DFS如何需要额外工作以确定何时“完成”节点(在TopoSort的上下文中回答)的更多详细信息:

使用DFS进行拓扑sorting,无需recursion

希望这可以解释为什么人们为了确定何时“完成”处理节点而需要确定recursionDFS的问题。