DFS（Depth-First Search）：深度优先搜索属于图算法的一种，其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
深度优先搜索其实是围绕着一词“回溯”展开，我们若是理解了回溯，那么对理解深度优先有十分大的帮助。
因为DFS是一种关于图的算法，所以我们从图的角度展开理解，回溯对于图来说，就相当于对已经走过的路进行新的尝试。
首先因为DFS是一种关于图的算法，所以笔者在此用文字对其进行简单的描述，后文会通过图片来进一步理解。
深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。
否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来
在此笔者贴出几张丑陋的图片供读者理解。以下是迷宫中一个人运用DFS走到终点的路径：
1.首先向右走
2.其次打叉的地方是障碍物，我们走不通，呢么根据方向顺序我们需要尝试向下走，走通了，那么我们可以向下走
3.然后我们继续尝试向右
4.最后我们一次类推走到终点
但是我们显然还要尝试别的走法，那么我们就需要退回去继续尝试，那么这里就要用到我们回溯的思想了
例如我们回溯到下面这步，我们在没回溯此步之前是向下走的，那么我们按照顺序就需要依次尝试向左与向上了，左边是障碍物，上面是我们已经走过的路，那么四个方向都不能走时，我们就需要继续回溯。
在这里有些小伙伴可能会问了，怎么知道我们已经走过哪些路了呢，那么就需要我们额外设立一个数组进行记录，如果下一步要走的路已经在我们记录的路中，那么我们就不会走这一步，同时，当我们回溯到上一步时，也会将数组中此步的坐标删除。
我们常常使用深度优先搜索解决迷宫问题，那么我们就以我上面的图为迷宫的原型，问小人走到终点所需的最短步数。
在此代码笔者运用了递归的方法，其实用栈也可以实现，因为栈的本质其实就是递归。学习c++后笔者将会考虑补上栈法的代码
输入：
5 4 （迷宫行列）
（迷宫地图，1代表障碍物，0代表可以走）
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3（分别为起点与终点坐标）
输出：
7
我们以此道例题为例，不过我们将3个盒子变为9个盒子
我们将手中空闲的牌按顺序放入盒子中，当放完后便走回上一个盒子取回原来的牌，然后继续按照顺序放入，手中牌放完后就输出盒子中牌的序列
广度优先搜索较之深度优先搜索之不同在于，深度优先搜索旨在不管有多少条岔路，先一条路走到底，不成功就返回上一个路口然后就选择下一条岔路，而广度优先搜索旨在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作，用图形来表示则是这样的
广度优先搜索关键在于重放，回放是继续遍历先前已经遍历过的结点 。
深度优先搜索与广度优先搜索都可用于迷宫问题，那么我们依然用迷宫问题作为例题
深度优先搜索的关键在于回溯与递归（栈）
广度优先搜索的关键在于重放与队列
这两种方法常用于迷宫问题，其实他们的原理并不难，最重要是我们能够理解算法的步骤并对之加深印象
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/bcyy/41001.html