DFS 主要用于在图中找到循环,而不是 BFS。有什么理由吗?两者都可以在遍历树/图时查找节点是否已被访问。
10 回答
深度优先搜索比广度优先搜索更节省内存,因为您可以更快地回溯。如果您使用调用堆栈也更容易实现,但这依赖于最长的路径不会溢出堆栈。
此外,如果您的图表是定向的,那么您不仅要记住您是否访问过某个节点,还要记住您是如何到达那里的。否则你可能会认为你找到了一个循环,但实际上你只有两条独立的路径 A->B,但这并不意味着有一条路径 B->A。例如,
如果您从 开始执行 BFS 0
,它将检测到存在循环,但实际上没有循环。
通过深度优先搜索,您可以在下降时将节点标记为已访问,并在回溯时取消标记它们。有关此算法的性能改进,请参阅评论。
对于在有向图中检测循环的最佳算法,您可以查看Tarjan 的算法。
- DFS 更容易实现
- 一旦 DFS 找到一个循环,堆栈将包含形成循环的节点。BFS 并非如此,因此如果您还想打印找到的循环,则需要做额外的工作。这使得 DFS 更加方便。
如果图是无向的,则 BFS 可能是合理的(作为我的客人展示使用 BFS 的有效算法,该算法将报告有向图中的循环!),其中每个“交叉边”定义一个循环。如果交叉边是{v1, v2}
,并且包含这些节点的根(在 BFS 树中)是r
,那么循环是r ~ v1 - v2 ~ r
(~
是路径,-
单边),这几乎可以像在 DFS 中一样容易地报告。
使用 BFS 的唯一原因是,如果您知道您的(无向)图将有长路径和小路径覆盖(换句话说,又深又窄)。在这种情况下,BFS 的队列需要的内存比 DFS 的堆栈要少(当然两者仍然是线性的)。
在所有其他情况下,DFS 显然是赢家。它适用于有向图和无向图,并且报告循环很简单——只需将任何后边连接到从祖先到后代的路径,就可以得到循环。总而言之,在这个问题上,比 BFS 好得多,实用得多。
我不知道为什么我的提要中出现了这么老的问题,但是以前的所有答案都是不好的,所以...
DFS 用于在有向图中查找循环,因为它有效。
在 DFS 中,每个顶点都被“访问”,其中访问顶点意味着:
- 顶点开始
访问从该顶点可到达的子图。这包括跟踪从该顶点可到达的所有未跟踪边,并访问所有可到达的未访问顶点。
顶点完成。
关键特征是在顶点完成之前跟踪从顶点到达的所有边。这是 DFS 的一个特性,但不是 BFS。其实这就是DFS的定义。
由于这个特性,我们知道当一个循环中的第一个顶点开始时:
- 没有跟踪循环中的任何边缘。我们知道这一点,因为您只能从循环中的另一个顶点到达它们,而我们正在谈论要开始的第一个顶点。
- 从该顶点可到达的所有未跟踪边将在完成之前被跟踪,这包括循环中的所有边,因为它们中没有一条被跟踪。因此,如果有一个循环,我们会在它开始之后,但在它结束之前找到一条回到第一个顶点的边;和
- 由于跟踪的所有边都可以从每个开始但未完成的顶点到达,因此找到到这样一个顶点的边总是表示一个循环。
所以,如果有一个环,那么我们保证找到一个开始但未完成的顶点的边(2),如果我们找到这样的边,那么我们保证有一个环(3)。
这就是为什么使用 DFS 在有向图中查找循环的原因。
BFS 不提供此类保证,因此它不起作用。(尽管包含 BFS 或类似子程序的非常好的循环查找算法)
另一方面,无向图只要在任何一对顶点之间有两条路径,即当它不是一棵树时,就有一个循环。这在 BFS 或 DFS 期间很容易检测到——追踪到新顶点的边形成一棵树,任何其他边都表示一个循环。
BFS 不适用于有向图寻找循环。将 A->B 和 A->C->B 视为图中从 A 到 B 的路径。BFS 会说,在沿着 B 被访问的路径之一走之后。当继续下一条路径时,它会说再次找到标记的节点B,因此,那里有一个循环。显然这里没有循环。
如果你将一个循环放置在一棵树中的一个随机点上,当它覆盖了大约一半的树时,DFS 将倾向于击中循环,一半的时间它已经遍历循环所在的位置,一半的时间它不会(并且平均会在树的其余一半中找到它),因此它将平均评估树的大约 0.5*0.5 + 0.5*0.75 = 0.625。
如果您将循环放置在树中的随机位置,则 BFS 只有在评估该深度的树层时才会倾向于命中循环。因此,您通常最终不得不评估平衡二叉树的叶子,这通常会导致评估更多的树。特别是,有 3/4 的时间,两个链接中的至少一个出现在树的叶子中,在这些情况下,您必须平均评估树的 3/4(如果有一个链接)或 7/树的 8 个(如果有两个),所以你已经达到了搜索 1/2*3/4 + 1/4*7/8 = (7+12)/32 = 21/32 = 的期望0.656... 的树,甚至没有增加搜索树的成本,并且在远离叶子节点的地方添加了一个循环。
此外,DFS 比 BFS 更容易实现。因此,除非您对周期有所了解(例如,周期可能位于您搜索的根附近,此时 BFS 为您提供了优势),否则它就是您要使用的。
要证明一个图是循环的,你只需要证明它有一个循环(边直接或间接指向自身)。
在 DFS 中,我们一次取一个顶点并检查它是否有循环。一旦找到一个循环,我们就可以省略检查其他顶点。
在 BFS 中,我们需要同时跟踪许多顶点边,并且通常在最后你会发现它是否有循环。随着图大小的增长,与 DFS 相比,BFS 需要更多的空间、计算和时间。
这有点取决于您是在谈论递归还是迭代实现。
Recursive-DFS 访问每个节点两次。Iterative-BFS 访问每个节点一次。
如果要检测循环,则需要在添加邻接关系之前和之后调查节点——无论是在节点上“开始”还是在节点上“结束”时。
这需要在 Iterative-BFS 中做更多的工作,因此大多数人选择 Recursive-DFS。
请注意,使用 std::stack 的 Iterative-DFS 的简单实现与 Iterative-BFS 具有相同的问题。在这种情况下,您需要将虚拟元素放入堆栈中以跟踪您何时“完成”在节点上的工作。
有关 Iterative-DFS 如何需要额外工作来确定何时“完成”节点的更多详细信息,请参阅此答案(在 TopoSort 的上下文中回答):
希望这可以解释为什么人们偏爱 Recursive-DFS 来解决您需要确定何时“完成”处理节点的问题。
我发现BFS和DFS都可以用来检测循环。有些问题提到 BFS 不能与有向图一起使用。我谦虚不同意。
在 BFS-Queue 中,我们可以跟踪父节点列表/集,如果再次遇到相同的节点(直接父节点除外),我们可以将其标记为循环。所以这种方式 BFS 也应该与有向图一起使用。
尽管与 DFS 相比,这将是非常低效的内存,这也是我们主要使用 DFS 的原因。
- DFS 内存高效
- DFS 更容易可视化,因为它已经使用了显式/隐式堆栈