讨论/技术交流/为什么 BFS 的时间比 DFS 时间要久?/
为什么 BFS 的时间比 DFS 时间要久?

不懂就问,如题

共 5 个回复

要讨论这个问题缺少一些前提条件:

  • 执行时间和时间复杂度是两个概念,如果只是遍历,绝大多数情况下,BFS 和 DFS 的时间复杂度是一样的;
  • 执行时间和测试用例强相关;
  • 不同场景下,遍历各有特点:
    • 如果找最短路径,BFS 一般会比 DFS 快,这是因为 DFS 需要遍历完整个图结构或者树结构;
    • 如果是回溯算法,DFS 比 BFS 快,这是因为 BFS 需要保存所有中间那的状态,保存所有中间状态这件事情就很耗时,DFS 只需要保存需要的结果。

因此我的观点是具体问题具体分析,没有那么绝对。

9

兄弟回答的靠谱!解释的很好。

你还没见过递归深度过大导致的超时吧....遇到了要改成bfs了

我还想了半天你的如题指的题怎么还没加载出来,后来才反应过来你想涵盖所有。。那显然是不成立的

从访问节点次数的方面来说,这两个方法最终都会把每个节点访问一次,平均来说,时间是没有区别的。dfs有方法递归调用的问题,bfs通常是用一个队列完成,方法不存在递归调用。所以dfs会相对慢一些