广度优先搜索是回溯吗（广度优先搜索序列怎么做）

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

 <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>参考文章&#xff1a;https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E6%90%9C%E7%B4%A2.md</p>

讯享网

广度优先搜索是按层来处理顶点的，距离开始点最近的那些顶点首先被访问，而最远的那些顶点则最后被访问。BFS的代码使用了一个队列。搜索的步骤：

首先选择一个顶点作为起始顶点，将起始顶点放入队列中
从队列首部选出一个顶点，将与之相邻并且没有被访问的结点依次加入到队列的队尾，然后访问这些与之相邻并且没有被访问过的结点，将队列队首的结点删去。
按照步骤2处理队列中下一个结点，直到找到要找的结点或者队列中没有结点结束。

讯享网

我们用一道LeedCode上面的题目讲解，题目位置：

需要一个队列，来记录下一次访问的结点，因为该队列是记录结点位置的（访问结点的下标），如果一维数组可以搞定，定义个，如果是二维，定义.
需要一个备忘录，记录已经被访问的结点，备忘录用数组表示
每一层结点数就是可以访问的结点，这里题目是 8 个方向上的单元格

在这里插入图片描述
讯享网

广度优先搜索一层一层遍历，每一层得到的所有新节点，要用队列存储起来以备下一层遍历的时候再遍历。

而深度优先搜索在得到一个新节点时立即对新节点进行遍历：从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。

从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种 可达性 问题。

在程序实现 DFS 时需要考虑以下问题：

栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。
每个结点有多少个子树（也就是一个结点遍历完，深度优先遍历时，有几个可选的结点可以遍历，比如上图的0，可以有1、2、5、6四个结点可以选择）

我们用LeedCode上面的题目来讲解：

695. 岛屿的最大面积

讯享网

求岛屿最大面积，也就是从一个结点出发，我们按前后左右方向走，可以走的最大格子数（可达最大区域）。

我们访问过一个位置后，使用深度优先遍历的话，我们可以有四个选择，也就是水平或者竖直的四个方向上，这对应深度优先遍历，就是每个结点都有四个子树。
对于可以访问的结点，访问过后，我们将其值1置为0，表示已经访问过了（0在这个题目当中不需要访问）。
对于栈，这题我们用递归，因为有四个选择，我们在递归时，需要加上四个dfs函数。
结果：
在这里插入图片描述

Backtracking（回溯）属于 DFS。

普通 DFS 主要用在可达性问题，这种问题只需要执行到特点的位置然后返回即可。
而 Backtracking 主要用于求解排列组合问题，例如有 { ‘a’,‘b’,‘c’ } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。

因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：

在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

讯享网

在这里插入图片描述

广度优先搜索是回溯吗（广度优先搜索序列怎么做）

相关推荐