本课件并不深入剖析 DFS 和 BFS 算法的代码。本课件只希望让大家留下一个印象，什么是 BFS ，什么是 DFS ，他们的区别是什么。学习这个内容的时候要文字和图像结合，下面有个动画，这个动作做得很好。这也是为什么我参考了这篇文章的原因。

1 什么是 BFS

BFS（Breadth First Search 广度优先搜索）是一种图遍历算法，它从一个起始点开始，逐层扩展搜索范围，直到找到目标节点为止。

这种算法通常用于解决 最短路径 问题，比如在迷宫中找到从起点到终点的最短路径。

首先，你会从起点开始，检查所有与它相邻的位置，也就是距离起点为 1 的位置

然后，你会继续向外扩展，检查所有距离起点为 2 的位置，以此类推，直到找到出口

在 BFS 中，你可以使用队列来存储待搜索的节点。起始点首先加入队列中，然后不断从队列中取出节点，检查它是否是目标节点。如果不是，就将它的所有未被访问过的邻居加入队列中。这样，队列中的节点总是按照它们距离起点的距离排序，先加入队列的节点总是先被取出来搜索。

通过这种方式，BFS 可以找到起点到目标节点的最短路径。在实际应用中，BFS还可以用于拓扑排序、连通性检测等问题的解决。

2 什么是 DFS

DFS（Depth First Search 深度优先搜索）是一种图遍历算法，它从一个起始点开始，一直往下走直到不能再走为止，然后返回到前一个节点，继续探索它的其他分支，直到找到目标节点为止。这种算法通常用于解决“遍历”问题，比如在树中查找所有的叶子节点。

要理解 DFS，也还可以想象自己在迷宫中寻找所有可行的路径

首先，你会从起点开始，顺着一条路一直走，直到你走到一个死胡同

再返回到前一个节点，继续探索其他分支

在探索过程中，你可以使用栈来存储已经访问过的节点，以便后续回溯。

在 DFS 中，你可以使用递归或栈来实现深度优先搜索。通过这种方式，DFS 可以找到所有可行的路径，或者在树中查找所有的叶子节点。

在实际应用中，DFS 还可以用于拓扑排序、连通性检测等问题的解决。与BFS相比，DFS 通常更适合处理深度优先的问题，而BFS更适合处理广度优先的问题。

3 BFS 与 DFS 的比较

如果分别用 DFS 与 BFS 将二叉树的所有结点遍历一遍，那么它们遍历结点的顺序分别如下所示。

上面的这个动图，很像倒过来一棵树，对，在数据结构里面，它就叫树。树是有根的，数据结构里的树也有根。讲这种纯理论理论的东西，小朋友特别迷糊，我们还是要结合一个具体的例子来讲述。

例如我们的题目小老鼠走迷宫.1，题目说小老鼠从迷宫的左上角出发，出口在迷宫的右下角，迷宫里有障碍物，数字 1 表示那个位置不能走，数字 0 表示是可以走的。所以，一开始，小老鼠是站在出发点（1,1）上的，（1,1） 表示的是 第 1 行的 第 1 列。

从这个位置出发，小老鼠下一步就是要去探索，从（1,1）向上下左右 4 个方向探索，有一些方向是超越了迷宫的范围，所以可以跳过（continue），有一些地方可能是障碍物，也要跳过，探索成功的地方就是小老鼠走 1 步之后能到达的地点，然后我们新探索到的地点再去找新的可到达点，这个过程就是搜索的过程，所以，我们叫这种探寻、搜索的算法叫搜索算法。

而小老鼠是从出发点开始走的，所以，出发点其实就是上面动画里面的树根。树根探寻出来的可到达点就是树根的儿子、孙子、孙子的孙子。结合这条题，一个点最多有 4 个儿子，就是上下左右 4 个位置了。但是，也有可能不够 4 个儿子，因为，如果上下左右 4 个位置中有一些位置是超越了棋盘的位置，或者是障碍物的点，那这个点就不会成为儿子。

而 BFS 和 DFS 讲述的就是两种不一样的探索顺序。

1. BFS 算法是一层一层的往外探索：先找出 1 步所有的可到达点（“所有”是关键词，DFS 在这里就不是“所有”），也就是说，先找到根节点的所有儿子；然后，根据第 1 步到到达的点，找出所有 2 步可以到达的点；然后再找所有 3 步可以到达的点......知道到达目的地

2. DFS 算法是尽量尽快往更远的地方走的探索模式：从根节点找到一个儿子（不是所有，找到 1 个就可以）就继续从这个儿子出发找它的儿子，然后重复......一直到某个时候，找不到儿子了，那么就往回走（算法里面把这个称为回溯）,我们用平白一点的语言讲，就是往回退 1 步，看看有没有别的儿子（因为之前并非是找了所有的儿子的，因此可能会漏掉了一些别的儿子），如果有，就从这个新找到的儿子出发去找儿子，如果没有，就再退 1 步......

上面的理论知识讲到：BFS 算法一般是使用队列来实现的；DFS 算法一般基于递归或者栈来实现，更严格来说，递归也是基于栈来实现的。

4 什么时候用 BFS ，什么时候用 DFS

如果题目问的是，最少通过多少步能得到一个什么状态或者什么变换结果，这类型的题目往往用 BFS。因为，BFS 的过程依赖于队列，而队列内的元素是根据变换次数从小到大排列的。不断的从队列中拿出队首元素，然后对这个元素进行状态变化，变化的结果是放在队列尾部。所以，一旦变化的结果是满足题目最终条件的，就可以认为这是最少变化的答案。

如果题目要求你枚举每一种状态变化的路径（从最初的状态如何一步步变化得到最终状态），这时候很可能用 DFS。DFS 其实也是一种枚举，它能罗列每一种情况，而且能跟踪整个变化的细节（动态规划算法是不能跟踪细节的，例如，它能找到方案数，但是不能列举每一种方案是什么）。如果题目要求你输出每一种方案，或者是要你基于每一种方案进一步去算一个什么东西，这时候 DFS 往往能派的上用场。

本课件有很多内容参考：https://blog.csdn.net/v_JULY_v/article/details/6111353