98

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

4

10 回答 10

84

深度优先搜索比广度优先搜索更节省内存,因为您可以更快地回溯。如果您使用调用堆栈也更容易实现,但这依赖于最长的路径不会溢出堆栈。

此外,如果您的图表是定向的,那么您不仅要记住您是否访问过某个节点,还要记住您是如何到达那里的。否则你可能会认为你找到了一个循环,但实际上你只有两条独立的路径 A->B,但这并不意味着有一条路径 B->A。例如,

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

通过深度优先搜索,您可以在下降时将节点标记为已访问,并在回溯时取消标记它们。有关此算法的性能改进,请参阅评论。

对于在有向图中检测循环的最佳算法,您可以查看Tarjan 的算法

于 2010-05-19T21:44:45.090 回答
31
  1. DFS 更容易实现
  2. 一旦 DFS 找到一个循环,堆栈将包含形成循环的节点。BFS 并非如此,因此如果您还想打印找到的循环,则需要做额外的工作。这使得 DFS 更加方便。
于 2010-05-19T21:51:24.560 回答
13

如果图是无向的,则 BFS 可能是合理的(作为我的客人展示使用 BFS 的有效算法,该算法将报告有向图中的循环!),其中每个“交叉边”定义一个循环。如果交叉边是{v1, v2},并且包含这些节点的根(在 BFS 树中)是r,那么循环是r ~ v1 - v2 ~ r~是路径,-单边),这几乎可以像在 DFS 中一样容易地报告。

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

在所有其他情况下,DFS 显然是赢家。它适用于有向图和无向图,并且报告循环很简单——只需将任何后边连接到从祖先到后代的路径,就可以得到循环。总而言之,在这个问题上,比 BFS 好得多,实用得多。

于 2010-05-20T08:53:01.610 回答
10

我不知道为什么我的提要中出现了这么老的问题,但是以前的所有答案都是不好的,所以...

DFS 用于在有向图中查找循环,因为它有效

在 DFS 中,每个顶点都被“访问”,其中访问顶点意味着:

  1. 顶点开始
  2. 访问从该顶点可到达的子图。这包括跟踪从该顶点可到达的所有未跟踪边,并访问所有可到达的未访问顶点。

  3. 顶点完成。

关键特征是在顶点完成之前跟踪从顶点到达的所有边。这是 DFS 的一个特性,但不是 BFS。其实这就是DFS的定义。

由于这个特性,我们知道当一个循环中的第一个顶点开始时:

  1. 没有跟踪循环中的任何边缘。我们知道这一点,因为您只能从循环中的另一个顶点到达它们,而我们正在谈论要开始的第一个顶点。
  2. 从该顶点可到达的所有未跟踪边将在完成之前被跟踪,这包括循环中的所有边,因为它们中没有一条被跟踪。因此,如果有一个循环,我们会在它开始之后,但在它结束之前找到一条回到第一个顶点的边;和
  3. 由于跟踪的所有边都可以从每个开始但未完成的顶点到达,因此找到到这样一个顶点的边总是表示一个循环。

所以,如果有一个环,那么我们保证找到一个开始但未完成的顶点的边(2),如果我们找到这样的边,那么我们保证有一个环(3)。

这就是为什么使用 DFS 在有向图中查找循环的原因。

BFS 不提供此类保证,因此它不起作用。(尽管包含 BFS 或类似子程序的非常好的循环查找算法)

另一方面,无向图只要在任何一对顶点之间有两条路径,即当它不是一棵树时,就有一个循环。这在 BFS 或 DFS 期间很容易检测到——追踪到新顶点的边形成一棵树,任何其他边都表示一个循环。

于 2019-10-03T01:59:12.417 回答
5

BFS 不适用于有向图寻找循环。将 A->B 和 A->C->B 视为图中从 A 到 B 的路径。BFS 会说,在沿着 B 被访问的路径之一走之后。当继续下一条路径时,它会说再次找到标记的节点B,因此,那里有一个循环。显然这里没有循环。

于 2015-01-29T06:00:38.337 回答
2

如果你将一个循环放置在一棵树中的一个随机点上,当它覆盖了大约一半的树时,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 为您提供了优势),否则它就是您要使用的。

于 2010-05-19T21:53:05.163 回答
1

BFS当您想在有向图中找到包含给定节点的最短循环时,您必须使用它。

例如:在此处输入图像描述

如果给定节点是 2,则存在三个循环,它是 - [2,3,4][2,3,4,5,6,7,8,9]&的一部分[2,5,6,7,8,9]。最短的是[2,3,4]

为了使用 BFS 实现这一点,您必须使用适当的数据结构显式维护访问节点的历史记录。

但是对于所有其他目的(例如:寻找任何循环路径或检查循环是否存在),DFS由于其他人提到的原因,这是明确的选择。

于 2020-05-28T10:02:33.677 回答
1

要证明一个图是循环的,你只需要证明它有一个循环(边直接或间接指向自身)。

在 DFS 中,我们一次取一个顶点并检查它是否有循环。一旦找到一个循环,我们就可以省略检查其他顶点。

在 BFS 中,我们需要同时跟踪许多顶点边,并且通常在最后你会发现它是否有循环。随着图大小的增长,与 DFS 相比,BFS 需要更多的空间、计算和时间。

于 2015-07-28T01:32:24.767 回答
0

这有点取决于您是在谈论递归还是迭代实现。

Recursive-DFS 访问每个节点两次。Iterative-BFS 访问每个节点一次。

如果要检测循环,则需要在添加邻接关系之前和之后调查节点——无论是在节点上“开始”还是在节点上“结束”时。

这需要在 Iterative-BFS 中做更多的工作,因此大多数人选择 Recursive-DFS。

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

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

使用没有递归的 DFS 进行拓扑排序

希望这可以解释为什么人们偏爱 Recursive-DFS 来解决您需要确定何时“完成”处理节点的问题。

于 2016-02-09T20:28:46.703 回答
0

我发现BFS和DFS都可以用来检测循环。有些问题提到 BFS 不能与有向图一起使用。我谦虚不同意。

在 BFS-Queue 中,我们可以跟踪父节点列表/集,如果再次遇到相同的节点(直接父节点除外),我们可以将其标记为循环。所以这种方式 BFS 也应该与有向图一起使用。

尽管与 DFS 相比,这将是非常低效的内存,这也是我们主要使用 DFS 的原因。

  1. DFS 内存高效
  2. DFS 更容易可视化,因为它已经使用了显式/隐式堆栈
于 2021-11-21T08:17:07.063 回答