BFS和DFS的区别

Question

我正在阅读Cormen的算法导论，学习关于DFS的知识。下面是一段文字片段：

与BFS形成树状前驱子图不同，DFS所产生的前驱子图可能由多棵树组成，因为可以从多个源进行搜索。

除了以上注释外，还提到了以下内容：

BFS仅限于一个源时似乎是任意的，而DFS可以从多个源搜索。尽管在概念上，BFS也可以从多个源进行，DFS也可以限制为一个源，但我们的方法反映了这些搜索结果通常如何使用。

我的问题是：

1.谁能举个例子说明BFS如何用于多个源，以及DFS如何用于单个源？

- venkysmarty

Answer 1

当它说多源时，它是指搜索的起始节点。你会注意到算法的参数是 BFS(G, s) 和 DFS(G)。这应该已经是一个提示，BFS 是单源的，而 DFS 不是，因为 DFS 不需要任何初始节点作为参数。

正如作者所指出的主要区别，BFS 的结果始终是一棵树，而 DFS 可能是一片森林（树的集合）。意思是，如果从节点 s 运行 BFS，则它只会构造从 s 可达的节点的树，但如果图中还有其他节点，它将不会触及它们。然而，DFS 会继续在整个图中搜索，并构造所有这些连通分量的森林。正如他们解释的那样，在大多数用例中，每个算法的期望结果都是这样的。

正如作者所提到的，没有什么能阻止稍微修改使 DFS 成为单源。事实上，这种改变很容易。我们只需接受另一个参数 s，并在例程 DFS 中（而不是 DFS_VISIT）不是通过迭代图中的所有节点来执行行 5-7，而是执行 DFS_VISIT(s)。

类似地，可以更改 BFS 以使其运行具有多个源。我在网上找到了一个实现：http://algs4.cs.princeton.edu/41undirected/BreadthFirstPaths.java.html，尽管它与另一种可能的实现略有不同，后者会自动创建单独的树。这意味着该算法看起来像这样 BFS(G, S)（其中 S 是节点集合），而你可以实现 BFS(G) 并自动创建单独的树。这是队列化的轻微修改，我将把它作为练习留下。

正如作者所指出的，这些未被执行的原因是每个算法的主要用途使它们作为它们所使用的工具非常有用。虽然想到这一点很棒，但这是一个重要的要点，应该得到理解。

- davin

Answer 2

你理解了定义吗？在圣书上看到了一些图片吗？

当说DFS可能由几棵树组成时，是因为它会深入到达叶子节点，然后回溯。所以本质上想象一棵树，首先搜索左子树，然后右子树。左子树可能包含多个子树。这就是为什么。

当你考虑BFS时，它是基于层级的。也就是说，首先搜索层级。所以你有一个单一的源（节点），然后搜索该层级的所有子节点。

如果只有一个子节点，则使用单源DFS，因此您只有一个源。我认为如果将源视为父节点，则更清晰。

- DarthVader