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

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


当前回答

这是一个很好的例子,说明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,

其他回答

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

For BFS, we can consider Facebook example. We receive suggestion to add friends from the FB profile from other other friends profile. Suppose A->B, while B->E and B->F, so A will get suggestion for E And F. They must be using BFS to read till second level. DFS is more based on scenarios where we want to forecast something based on data we have from source to destination. As mentioned already about chess or sudoku. Once thing I have different here is, I believe DFS should be used for shortest path because DFS will cover the whole path first then we can decide the best. But as BFS will use greedy's approach so might be it looks like its the shortest path, but the final result might differ. Let me know whether my understanding is wrong.

深度优先搜索

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

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

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


广度优先搜索

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

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

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

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