BFS和DFS

这两者“遍历”的序列到底有何差别？

那本篇文章就单纯来讲讲它们的区别和各自的应用，不会涉及任何代码。

广度优先搜索算法（Breadth-First-Search，缩写为BFS），是一种利用队列实现的搜索算法。简单来说，其搜索过程和“湖面丢进一块石头激起层层涟漪”类似。

深度优先搜索算法（Depth-First-Search，缩写为DFS），是一种利用递归实现的搜索算法。简单来说，其搜索过程和“不撞南墙不回头”类似。

BFS的重点在于队列，而DFS的重点在于递归。这是它们的本质区别。

举个典型例子，如下图，灰色代表墙壁，绿色代表起点，红色代表终点，规定每次只能走一步，且只能往下或右走。求一条绿色到红色的最短路径。

对于上面的问题，BFS和DFS都可以求出结果，它们的区别就是在复杂度上存在差异。我可以先告诉你，该题BFS是较佳算法。

BFS

如上图所示，从起点出发，对于每次出队列的点，都要遍历其四周的点。所以说BFS的搜索过程和“湖面丢进一块石头激起层层涟漪”很相似，此即“广度优先搜索算法”中“广度”的由来。

DFS

如上图所示，从起点出发，先把一个方向的点都遍历完才会改变方向......所以说，DFS的搜索过程和“不撞南墙不回头”很相似，此即“深度优先搜索算法”中“深度”的由来。

总结

现在，你不妨对照着图，再去看看你打印出的遍历序列，是不是一目了然呢？

最后我再说下它们的应用方向。

BFS常用于找单一的最短路线，它的特点是"搜到就是最优解"，而DFS用于找所有解的问题，它的空间效率高，而且找到的不一定是最优解，必须记录并完成整个搜索，故一般情况下，深搜需要非常高效的剪枝（剪枝的概念请百度）。