代码随想录 广度优先搜索理论基础

一、BFS的使用场景

1.BFS的搜索方式适合于解决两个点之间的最短路径问题。这是因为BFS是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。

2.有一些问题是广搜和深搜都能够解决的，比如岛屿问题。这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且属性相同的节点标记上就行。

二、BFS的过程：是一圈一圈的搜索。

1.用一个方格画图。假如每次搜索的方向为上下左右（不包含斜上方），那么给出一个start起始位置，BFS就是从四个方向走出的第一步。

2.如果再加上一个end终止位置，那么适用BFS的搜索过程如下图所示。

从上图可以看出，从start起点开始，是一圈一圈向外搜索。方格编号1是第一步遍历的节点，方格编号2是第二步遍历的节点，第四步的时候可以找到终止点end。正是因为BFS一圈一圈的遍历方式，所以一旦遇到终止点，那么一定是一条最短路径。

而且地图还可能有障碍，如下图所示。

（在第五步、第六步只把关键的节点染色了，其他方向周边没有去染色，只要关注关键地方染色的逻辑即可）

从上图可以看出，如果添加了障碍，那么是第六步才能走到end终点。

因此只要BFS能搜到终点，那么就一定是一条最短路。

三、代码框架：

1.这一圈一圈的搜索过程，需要放在一个特定的容器里，然后去遍历。这个容器用队列、栈甚至是数组都是可以的。

（1）用队列的话：保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。这是因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。

（2）用栈的话：第一圈顺时针遍历，第二圈逆时针遍历，第三圈又顺时针遍历。这是因为栈是先进后出，加入元素和弹出元素的顺序改变了。

以队列为例，给出广搜代码模板，该代码模板针对的就是上面的四方格地图。

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向 // grid 是地图，也就是一个二维数组 // visited标记访问过的节点，不要重复访问 // x,y 表示开始搜索节点的下标 void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) { queue<pair<int, int>> que; // 定义队列 que.push({x, y}); // 起始节点加入队列 visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点 while(!que.empty()) { // 开始遍历队列里的元素 pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素 int curx = cur.first; int cury = cur.second; // 当前节点坐标 for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历 int nextx = curx + dir[i][0]; int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标 if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 坐标越界了，直接跳过 if (!visited[nextx][nexty]) { // 如果节点没被访问过 que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点 visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问 } } } }