2025年广度优先搜索是回溯吗（广度优先搜索是回溯吗知乎）

大家好，我是讯享网，很高兴认识大家。

 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <p></p>

讯享网

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个盒子

我们将手中空闲的牌按顺序放入盒子中，当放完后便走回上一个盒子取回原来的牌，然后继续按照顺序放入，手中牌放完后就输出盒子中牌的序列

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

广度优先搜索关键在于重放，回放是继续遍历先前已经遍历过的结点。

深度优先搜索与广度优先搜索都可用于迷宫问题，那么我们依然用迷宫问题作为例题

讯享网

深度优先搜索的关键在于回溯与递归（栈）
广度优先搜索的关键在于重放与队列
这两种方法常用于迷宫问题，其实他们的原理并不难，最重要是我们能够理解算法的步骤并对之加深印象

2025年广度优先搜索是回溯吗（广度优先搜索是回溯吗知乎）

相关推荐