一尘不染

什么时候使用深度优先搜索(DFS)和广度优先搜索(BFS)?

algorithm

我了解DFS和BFS之间的区别,但是我想知道什么时候使用另一种比较实用?

谁能举例说明DFS如何胜过BFS,反之亦然?


阅读 841

收藏
2020-07-28

共1个答案

一尘不染

这在很大程度上取决于搜索树的结构以及解决方案(又名搜索项目)的数量和位置。

  • 如果您知道解决方案离树的根并不远,那么广度优先搜索(BFS)可能更好。
  • 如果树很深并且解决方案很少,则深度优先搜索(DFS)可能会花费很长时间,但BFS可能会更快。

  • 如果树很宽,则BFS可能需要太多内存,因此可能是完全不切实际的。

  • 如果解决方案很常见但位于树的深处,则BFS可能不切实际。

  • 如果搜索树非常深,则无论如何都需要限制深度优先搜索(DFS)的搜索深度(例如,使用迭代加深)。

但是,这些只是经验法则。您可能需要进行实验。

2020-07-28