讨论/算法和数据结构/BFS 与 DFS 到底哪个更快?/
BFS 与 DFS 到底哪个更快?

深度优先与广度优先搜索都是二叉树中极为常见的操作。粗粗看来,它们好像非常接近,那它们到底有什么区别?到底谁更快?各自有什么应用场景呢?

展开讨论

对于结点的全遍历,二者性能相当。
对于求最短路径,BFS快,你想啊,BFS从起点开始一圈圈往外扩,但凡见到终点即结束遍历,大概率不会把结点全遍历完。但是对于DFS,必须每条路径都走一遍,经过所有路径长度比较后,才敢确定最短的那条,所以,DFS一定要遍历完所有结点,时间当然长了。

1