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

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


当前回答

我认为这取决于你所面临的问题。

简单图上的最短路径-> BFS 所有可能的结果-> DFS 在图上搜索(将树,martix也视为图)-> DFS ....

其他回答

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

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

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


关于国际发展基金

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

因为深度优先搜索在处理节点时使用堆栈,所以DFS提供回溯。由于宽度优先搜索使用队列而不是堆栈来跟踪正在处理的节点,BFS不提供回溯。

这是一个很好的例子,说明BFS在某些情况下优于DFS。https://leetcode.com/problems/01-matrix/

当正确实现时,两个解决方案都应该访问比当前单元格+1距离更远的单元格。 但DFS效率低,重复访问同一单元,导致复杂度为O(n*n)。

例如,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,

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