BFS和DFS的区别 [英] Difference between BFS and DFS

问题描述

我在阅​​读有关 DFS 的算法导论的由Cormen。以下是文字 片段。

  

不同于BFS，其predecessor子图形成一棵树，在predecessor   由DFS产生subgrpah可以由几个树，因为   搜索可以重复来自多个源。

在除了上述注释，以下提到

  

这似乎武断的BFS仅限于只有一个来源，其中作为   DFS可以从多个源中搜索。虽然概念，BFS   可能要从mutilple来源和DFS可能限于一个   源，我们的做法反映了这些搜索的结果如何   通常使用

我的问题是

1. 在任何一个可以给BFS如何使用多个来源的例子， DFS是使用单一来源？

解决方案

当它说，多个源是指搜索的开始节点。你会注意到的算法的参数是 BFS（G，S）和 DFS（G）。这应该已经是一个暗示，BFS是单源和DFS是不是，因为DFS不采取任何初始节点作为参数。<​​/ P>

这两者之间的主要区别，正如作者指出的是，BFS的结果总是一棵树，而DFS可以是一个森林（集合树）。这意味着，如果BFS从节点s运行，那么它将只构造的那些节点从s可达的树中，但如果有图中其它节点，将不会接触它们。 DFS但是将继续通过整个图形的搜索，构建所有这些连接组件的森林。这是，因为他们解释，在大多数使用情况每个算法的所期望的结果。

正如作者所提到的，我们并不阻止轻微的修改，使DFS单一来源。其实这种变化是很容易。我们简单地接受另一个参数取值，并在常规 DFS （而不是 DFS_VISIT ），而不是5-7行迭代通过图中的所有节点，我们只需执行 DFS_VISIT（S）。

的

类似地，改变BFS能够使其与多个源中运行。我发现了一个实现在线：<一href="http://algs4.cs.princeton.edu/41undirected/BreadthFirstPaths.java.html">http://algs4.cs.princeton.edu/41undirected/BreadthFirstPaths.java.html尽管这是略有不同，另一种可能的实现，这将自动创建单独的树。含义，即算法看起来像这样 BFS（G，S）（其中取值是节点的集合），而你可以实现 BFS（G），并自动做出独立的树。这是一个轻微修改排队，我会离开它作为一个练习。

正如作者指出的，这些都没有做的原因是，主要采用各种算法借给他们是有用的，因为它们是。虽然也为思考该做的，这是一个应该被理解很重要的一点。

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

1. Can any one give an example how BFS is used with multiple source and DFS is used with single source?

解决方案

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) and DFS(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 routine DFS (not DFS_VISIT) instead of lines 5-7 iterating through all nodes in the graph, we simply execute DFS_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) (where S is a collection of nodes) whereas you can implement BFS(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.

这篇关于BFS和DFS的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！