ven*_*rty 4 algorithm breadth-first-search depth-first-search
我读约DFS在算法导论由Cormen.以下是文字摘要.
与其前身子图形成树的BFS不同,由DFS产生的前身subgrpah可以由若干树组成,因为可以从多个源重复搜索.
除上述说明外,还提到了以下内容.
BFS仅限于一个来源似乎是任意的,因为DFS可以从多个来源搜索.虽然从概念上讲,BFS可以从多个来源进行,而DFS可以限制为一个来源,但我们的方法反映了这些搜索的结果通常如何使用.
我的问题是
当它说多个来源时,它指的是搜索的起始节点.您会注意到算法的参数是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)自动实现和生成单独的树.这是排队的一个小修改,我将把它留作练习.
正如作者所指出的那样,没有做到这一点的原因是每种算法的主要用途都使它们有用.虽然考虑到这一点做得很好,但这是一个应该被理解的重点.