第七章：深度优先搜索

不撞南墙不回头-深度优先搜索

广度优先搜索BFS是每次将当前状态能够一步拓展出的所有状态，全部拓展出来依次存入队列。而深度优先搜索是将当前状态按照一定的规则顺序，先拓展一步得到一个新状态，再对这个这个新状态递归拓展下去。如果无法拓展，则退回一步到上一步的状态，再按照原先设定的规则顺序重新寻找一个状态拓展。如此搜索，直到找到目标状态，或者遍历完所有的状态。

深度优先搜索

深度优先搜索（Depth First Search，DFS），简称深搜，其状态“退后一步”的顺序符合“后进先出”的特点，所以采用“栈”存储状态。深搜的空间复杂度较小，因为它只存储了初始状态到当前状态的一条搜索路径。但是，深搜找到的第一个解不一定是最优解，要找最优解必须搜索整棵“搜索树”。所以，深搜适用于要求所有解方案的题目。

相信通过上面的描述，同学们还是对深度优先搜索一头雾水。下面我们结合一个例子，和大家一起探索下什么是深度优先搜索。深度优先搜索可以这样想，一个人迷路了，遇到很多分叉路口，他只有一个人，并且想走出去，所以他只能一个个路线的去尝试，一条道路走到黑，发现到头了，然后再退回去走刚才这条路的其他分叉路口，最后发现这条路的所有分叉路口走完了，选择另外一条路继续以上操作，直到所有的路都走过了。

而广度优先并不是这样，一个人迷路了，但是他有特异技能（就好比火影里面鸣人的影分身一样）， 他遇到分叉路口，不是选一个走，而是分身多个人每个路口都去试试 ，比如有A、B、C三个分叉路口，A路走一步，紧接着B路也走一步，然后C路也赶紧走一步，步伐整齐统一，直到所有的路走过了。

深度优先搜索的步骤

深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标，这里称之为递归下去。否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路，这便是回溯上来。下面结合具体例子来理解。如图所示，在一个迷宫中，黑色块代表玩家所在位置，红色块代表终点，问是否有一条到终点的路径。

我们用深度优先搜索的方法去解这道题，由图可知，我们可以走上下左右四个方向，我们规定按照 左下右上 的方向顺序走（逆时针方向），即如果左边可以走，我们先走左边。然后递归下去，没达到终点，我们再回溯上来，等又回溯到这个位置时，左边已经走过了，那么我们就走下边，按照这样的顺序与方向走。并且我们把走过的路标记一下代表走过，不能再走。所以我们从黑色起点首先向左走，然后发现还可以向左走，最后我们到达图示位置。

已经连续向左走到左上角的位置了，这时发现左边不能走了，这时我们就考虑往下走，发现也不能走，同理，上边也不能走， 右边已经走过了也不能走，这时候无路可走了 ，代表这条路是死路不能帮我们解决问题， 所以现在要回溯上去，回溯到上一个位置。

在这个位置我们由上可知走左边是死路不行，上下是墙壁不能走，而右边又是走过的路，已经被标记过了，不能走。所以只能再度回溯到上一个位置寻找别的出路。

最终我们回溯到最初的位置，同理，左边证明是死路不必走了，上和右是墙壁， 所以我们走下边 。然后递归下去

到了这个格子，因为按照左下右上的顺序，我们走左边，递归下去

一直递归下去到最左边的格子，然后左边行不通，走下边，一直往下走，正好可以找到目标位置。

广度优先搜索较之深度优先搜索之不同在于，深度优先搜索旨在不管有多少条岔路， 先一条路走到底，不成功就返回上一个路口然后就选择下一条岔路 ，而广度优先搜索旨在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作，用图形来表示则是这样的，例子同上。