我理解DFS和BFS之间的区别,但是我想知道在选择DFS和BFS时应该考虑哪些因素。
比如对于非常深的树避免DFS,等等。
我理解DFS和BFS之间的区别,但是我想知道在选择DFS和BFS时应该考虑哪些因素。
比如对于非常深的树避免DFS,等等。
当前回答
一些算法依赖于DFS(或BFS)的特定属性来工作。例如,用于查找2连接组件的Hopcroft和Tarjan算法利用了这样一个事实,即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,
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.
根据DFS和BFS的性质。 例如,当我们要求最短路径时。 我们通常使用bfs,它可以保证“最短”。 但是DFS只能保证我们可以从这一点可以到达那一点,不能保证‘最短’。
一些算法依赖于DFS(或BFS)的特定属性来工作。例如,用于查找2连接组件的Hopcroft和Tarjan算法利用了这样一个事实,即DFS遇到的每个已经访问过的节点都位于从根节点到当前探索的节点的路径上。
我认为这取决于你所面临的问题。
简单图上的最短路径-> BFS 所有可能的结果-> DFS 在图上搜索(将树,martix也视为图)-> DFS ....