为什么DFS而不是BFS在图中查找周期

Question

主要是DFS用于在图中找到循环而不是BFS.有什么原因？两者都可以在遍历树/图时查找是否已访问过节点.

Answer 1

深度优先搜索比广度优先搜索更有效,因为您可以更快地回溯.如果使用调用堆栈,它也更容易实现,但这依赖于没有溢出堆栈的最长路径.

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

如果你从BFS开始0,它将检测到周期存在,但实际上没有周期.

通过深度优先搜索,您可以在下降时将节点标记为已访问,并在您回溯时将其标记为未标记.有关此算法的性能改进,请参阅注释.

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

Answer 2

1. DFS更容易实现
2. 一旦DFS找到一个循环,堆栈将包含形成循环的节点.对于BFS也是如此,因此如果您还要打印找到的循环,则需要做额外的工作.这使得DFS更加方便.

Answer 3

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

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

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

Answer 4

我不知道为什么我的提要中会弹出这样一个老问题，但是以前的所有答案都很糟糕，所以...

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

在 DFS 中，每个顶点都被“访问过”，其中访问一个顶点意味着：

1. 顶点开始

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

3. 顶点完成。

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

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

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

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

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

BFS 没有提供这样的保证，所以它不起作用。（尽管非常好的循环查找算法包括 BFS 或类似的子过程）

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

Answer 5

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