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

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


当前回答

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

其他回答

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

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

这在很大程度上取决于搜索树的结构以及解的数量和位置(也就是搜索项)。

If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster. If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

但这些只是经验法则;你可能需要尝试一下。

我认为在实践中,你通常不会以纯粹的形式使用这些算法。可能会有一些启发式方法,有助于首先探索搜索空间中有希望的部分,或者您可能希望修改搜索算法,以便能够有效地并行化它。

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

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

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