BFS 和 DFS 的区别
我正在 Cormen 的算法简介中阅读关于DFS的内容。以下为正文 片段。
与 BFS 不同，BFS 的前驱子图形成一棵树，前驱子图形成树 DFS产生的subgrpah可能由几棵树组成，因为 可以从多个来源重复搜索。
除上述注释外，还提到以下内容。
BFS 仅限于一个源，这似乎是任意的，因为 DFS 可以从多个源进行搜索。尽管从概念上讲，BFS 可以从多个来源进行，而 DFS 可以仅限于一个来源 来源，我们的方法反映了这些搜索的结果如何 通常使用。
我的问题是
- 任何人都可以举例说明如何将 BFS 与多个源一起使用 DFS 与单一源一起使用吗？
I am reading about DFS in Introduction to Algorithms by Cormen. Following is text
snippet.
Unlike BFS, whose predecessor subgraph forms a tree, the predecessor
subgrpah produced by DFS may be composed of several trees, because
search may be repeated from multiple sources.
In addition to above notes, following is mentioned.
It may seem arbitrary that BFS is limited to only one source where as
DFS may search from multiple sources. Although conceptually, BFS
could proceed from mutilple sources and DFS could limited to one
source, our approach reflects how the results of these searches are
typically used.
My question is
- Can any one give an example how BFS is used with multiple source and
DFS is used with single source?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
当它说多个源时，它指的是搜索的起始节点。您会注意到算法的参数是
BFS(G, s)和DFS(G)。这应该已经暗示 BFS 是单源的，而 DFS 不是，因为 DFS 不接受任何初始节点作为参数。正如作者指出的，这两者之间的主要区别在于 BFS 的结果始终是一棵树，而 DFS 可以是一个森林（树的集合）。这意味着，如果 BFS 从节点 s 运行，那么它将仅构建从 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)> 并自动创建单独的树。这是对队列的轻微修改，我将把它作为练习。正如作者指出的，这些没有完成的原因是每种算法的主要用途使得它们本身就有用。尽管思考这一点做得很好，但这是一个应该理解的重要观点。
When it says multiple sources it is referring to the start node of the search. You'll notice that the parameters of the algorithms are
BFS(G, s)andDFS(G). That should already be a hint that BFS is single-source and DFS isn't, since DFS doesn't take any initial node as an argument.The major difference between these two, as the authors point out, is that the result of BFS is always a tree, whereas DFS can be a forest (collection of trees). Meaning, that if BFS is run from a node s, then it will construct the tree only of those nodes reachable from s, but if there are other nodes in the graph, will not touch them. DFS however will continue its search through the entire graph, and construct the forest of all of these connected components. This is, as they explain, the desired result of each algorithm in most use-cases.
As the authors mentioned there is nothing stopping slight modifications to make DFS single source. In fact this change is easy. We simply accept another parameter
s, and in the routineDFS(notDFS_VISIT) instead of lines 5-7 iterating through all nodes in the graph, we simply executeDFS_VISIT(s).Similarly, changing BFS is possible to make it run with multiple sources. I found an implementation online: http://algs4.cs.princeton.edu/41undirected/BreadthFirstPaths.java.html although that is slightly different to another possible implementation, which creates separate trees automatically. Meaning, that algorithm looks like this
BFS(G, S)(whereSis a collection of nodes) whereas you can implementBFS(G)and make separate trees automatically. It's a slight modification to the queueing and I'll leave it as an exercise.As the authors point out, the reason these aren't done is that the main use of each algorithm lends to them being useful as they are. Although well done for thinking about this, it is an important point that should be understood.
你明白定义了吗？你看到圣书上的一些图片了吗？
当它说 DFS 可能由几棵树组成时，这是因为它会更深，直到到达叶子，然后回溯。因此，本质上想象一棵树，首先搜索左子树，然后搜索右子树。左子树可能包含多个子树。这就是原因。
当你想到 BFS 时，它是基于级别的。换句话说，级别优先搜索。因此，您只有一个源（节点），而不是搜索该级别的所有子节点。
如果只有一个子节点，则具有单源的 DFS，因此只有 1 个源。我认为如果将源作为父节点，会更清楚。
Did you understand the definition? Did you see some pictures on the holy book?
When it says that DFS may be composed of several trees it is because, it goes deeper until it reaches to a leaf and then back tracks. So essentially imagine a tree, first you search the left sub tree and then right subtree. left sub tree may contain several sub trees. that s why.
When you think about BFS, it s based on level. level first search in other words. so you have a single source (node) than you search all the sub nodes of that level.
DFS with single source if there is only one child node, so you have only 1 source. i think it would be more clear if you take the source as parent node.