我理解DFS和BFS之间的区别,但是我想知道在选择DFS和BFS时应该考虑哪些因素。

比如对于非常深的树避免DFS,等等。


当前回答

BFS的一个重要优势是,它可以用于寻找未加权图中任意两个节点之间的最短路径。 然而,我们不能用DFS来做同样的事情。

其他回答

一些算法依赖于DFS(或BFS)的特定属性来工作。例如,用于查找2连接组件的Hopcroft和Tarjan算法利用了这样一个事实,即DFS遇到的每个已经访问过的节点都位于从根节点到当前探索的节点的路径上。

当树的深度可以变化时,宽度优先搜索通常是最好的方法,并且您只需要搜索树的一部分来寻找解决方案。例如,寻找从起始值到最终值的最短路径是使用BFS的好地方。

深度优先搜索通常用于需要搜索整个树的情况。它比BFS更容易实现(使用递归),并且需要更少的状态:BFS需要存储整个“边界”,DFS只需要存储当前元素的父节点列表。

根据DFS和BFS的性质。 例如,当我们要求最短路径时。 我们通常使用bfs,它可以保证“最短”。 但是DFS只能保证我们可以从这一点可以到达那一点,不能保证‘最短’。

深度优先搜索

深度优先搜索通常用于模拟游戏(以及现实世界中的类似游戏场景)。在典型的游戏中,你可以从几种可能的行动中选择一种。每个选择都会引出更多的选择,每个选择又会引出更多的选择,如此循环往复,形成一个不断扩大的可能性树形图。

例如,在国际象棋和井字游戏中,当你决定走哪一步时,你可以在脑海中想象一步,然后是对手可能的反应,然后是你的反应,等等。你可以通过观察哪一步会带来最好的结果来决定做什么。

在游戏树中只有一些路径能够引导你获胜。有些会导致你的对手获胜,当你到达这样的结局时,你必须后退或回溯到前一个节点,并尝试不同的路径。通过这种方式,您可以探索树,直到找到一条具有成功结论的路径。然后沿着这条路迈出第一步。


广度优先搜索

宽度优先搜索有一个有趣的特性:它首先找到距离起点一条边的所有顶点,然后是距离起点两条边的所有顶点,依此类推。如果你试图找到从起始顶点到给定顶点的最短路径,这是很有用的。你开始一个BFS,当你找到指定的顶点时,你知道你到目前为止跟踪的路径是到该节点的最短路径。如果有更短的路径,BFS早就找到了。

宽度优先搜索可用于在BitTorrent等对等网络中查找相邻节点,GPS系统用于查找附近位置,社交网站用于查找指定距离内的人等等。

DFS比BFS更节省空间,但可能会深入到不必要的深度。

它们的名字揭示了:如果有很大的广度(即大的分支因子),但深度非常有限(例如有限的“移动”数量),那么DFS可能比BFS更受欢迎。


关于国际发展基金

应该提到的是,有一个不太为人所知的变体,它结合了DFS的空间效率,但(累积)BFS的水平顺序访问,是迭代深化深度优先搜索。该算法对一些节点进行了重访,但只贡献了一个常数因子的渐近差分。