我正在读关于DFS in 算法简介由科门.以下为正文
片段。
与 BFS 不同，BFS 的前驱子图形成一棵树，
DFS产生的subgrpah可能由几棵树组成，因为
可以从多个来源重复搜索。
除上述注释外，还提到以下内容。
BFS 仅限于一个源，这似乎是任意的，其中
DFS 可以从多个源进行搜索。尽管从概念上讲，BFS
可以从多个来源进行，而 DFS 可以仅限于一个来源
来源，我们的方法反映了这些搜索的结果如何
通常使用。
我的问题是
- 任何人都可以举例说明如何将 BFS 与多个源一起使用
DFS 与单一源一起使用吗？
当它说多个源时，它指的是搜索的起始节点。您会注意到算法的参数是BFS(G, s) and DFS(G)。这应该已经暗示 BFS 是单源的，而 DFS 不是，因为 DFS 不接受任何初始节点作为参数。
正如作者指出的，这两者之间的主要区别在于 BFS 的结果始终是一棵树，而 DFS 可以是一个森林（树的集合）。这意味着，如果 BFS 从节点 s 运行，那么它将仅构建从 s 可到达的那些节点的树，但如果图中还有其他节点，则不会触及它们。然而，DFS 将继续搜索整个图，并构建所有这些连接组件的森林。正如他们所解释的，这是大多数用例中每种算法的期望结果。
正如作者提到的，没有什么可以阻止轻微修改以使 DFS 成为单一源。事实上这个改变很容易。我们简单地接受另一个参数s，并且在日常工作中DFS (not DFS_VISIT）而不是第 5-7 行迭代图中的所有节点，我们只需执行DFS_VISIT(s).
同样，更改 BFS 可以使其与多个源一起运行。我在网上找到了一个实现：http://algs4.cs.princeton.edu/41undirected/BreadthFirstPaths.java.html http://algs4.cs.princeton.edu/41undirected/BreadthFirstPaths.java.html尽管这与另一种可能的实现略有不同，后者自动创建单独的树。意思是，该算法看起来像这样BFS(G, S) (where S是节点的集合），而你可以实现BFS(G)并自动生成单独的树。这是对队列的轻微修改，我将把它作为练习。
正如作者指出的，这些没有完成的原因是每种算法的主要用途使得它们本身就有用。尽管思考这一点做得很好，但这是一个应该理解的重要点。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
