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

广搜的使用场景

广搜的搜索方式就适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。

当然，也有一些问题是广搜 和 深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。 （我们会在具体题目讲解中详细来说）

比如下面这个图，从start开始慢慢向外扩展，第4次扩展才到end，那么最短路径的长度就是4，

一旦遇到终止点，那么一定是一条最短路径。

BFS模板

针对这个图，有下面的BFS模块，目的是遍历整个二维网格，并且记录哪些位置已经被访问过。

/*
广度优先搜索的模板，也就是bfs函数。
*/

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 定义四个可能的移动方向
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
/**
 * 使用广度优先搜索（BFS）遍历二维网格
 * @param grid 二维网格，通常表示为二维数组
 * @param visited 记录网格中各位置是否已被访问过的二维布尔数组
 * @param x 起始位置的x坐标
 * @param y 起始位置的y坐标
 * 此函数的目的是通过BFS算法遍历网格中所有连接的位置
 */
void bfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y)
{
    // 使用队列来实现BFS算法
    queue<pair<int, int>> que;
    // 将起始位置(x, y)加入队列，并标记为已访问
    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;
            }
        }
    }
}

算法从起始位置 (x, y) 开始，探索四个相邻的方向，并访问所有与起始位置连通的区域。使用队列来管理待访问的位置，并且使用 visited 数组来防止重复访问。

BFS的应用问题

• 迷宫问题：BFS 可以用于寻找迷宫的最短路径，或者探索从起始点出发，能到达的所有位置。

• 图的遍历：BFS 广泛应用于图的遍历中，特别是无权图中寻找最短路径时。

• 搜索问题：可以在很多搜索问题中使用 BFS，如路径规划、连通区域的计算等。