void bfs(int sx, int sy){ memset(st, 0, sizeof st); queue<PII> q; st[sx][sy] = true; q.push({sx, sy}); while(q.size()){ auto t = q.front(); q.pop(); cout << t.x << ' ' << t.y << endl; for(int u = 0; u < 4; u ++){ int a = dx[u] + t.x; int b = dy[u] + t.y; if(a < 0 || a >= n || b < 0 || b >= m) continue; if(st[a][b]) continue; if(g[a][b] == '#') continue; st[a][b] = true; q.push({a, b}); } } }

广度优先搜索 (BFS) 是一种用于遍历或搜索树或图数据结构的算法，它从树根 (或图的某个任意节点) 开始，逐层遍历所有节点，直到找到目标节点或遍历完所有节点。BFS 通常使用队列来实现，确保每一层的节点都被访问后再访问下一层的节点。13

🔍 BFS 的基本原理

• 队列的使用：BFS 的核心是使用队列来存储待访问的节点。初始时，将起始节点放入队列中，然后不断从队列中取出节点，访问其所有相邻节点，并将未访问过的相邻节点加入队列。2
• 标记已访问节点：为了避免重复访问节点，通常使用一个布尔数组 st 来标记已访问的节点。在访问一个节点时，首先检查它是否已经被访问过，如果没有，则将其标记为已访问并加入队列。4

🛠 BFS 的实现步骤

• 初始化：首先，初始化一个布尔数组 st 来标记已访问的节点，并创建一个队列 q 来存储待访问的节点。将起始节点 (sx, sy) 标记为已访问，并将其加入队列。2
• 循环遍历：在队列不为空的情况下，不断从队列中取出节点 t，访问其坐标 (t.x, t.y)，然后检查其所有相邻节点 (a, b)。如果相邻节点未被访问且满足条件（如不在边界外、不是障碍物等），则将其标记为已访问并加入队列。2
• 边界检查：在访问相邻节点时，需要检查其是否在边界内，避免访问无效节点。如果节点超出边界或已被访问，则跳过该节点。2

🌐 BFS 的应用场景

• 最短路径问题：BFS 常用于求解无权图中的最短路径问题。由于 BFS 逐层遍历的特性，它能够保证找到的路径是最短的。3
• 连通性检测：BFS 可以用于检测图中的连通分量。通过从任意节点开始 BFS，可以访问到所有与该节点连通的节点。4
• 迷宫问题：在迷宫问题中，BFS 可以用于寻找从起点到终点的最短路径。通过逐层扩展，BFS 能够找到最短的路径。2

📝 BFS 的代码实现

void bfs(int sx, int sy){
    memset(st, 0, sizeof st); // 初始化访问标记数组
    queue<PII> q; // 创建队列
    st[sx][sy] = true; // 标记起始节点为已访问
    q.push({sx, sy}); // 将起始节点加入队列

    while(q.size()){
        auto t = q.front(); // 取出队列中的第一个节点
        q.pop(); // 移除队列中的第一个节点

        cout << t.x << ' ' << t.y << endl; // 访问节点

        for(int u = 0; u < 4; u ++){ // 遍历相邻节点
            int a = dx[u] + t.x;
            int b = dy[u] + t.y;

            if(a < 0 || a >= n || b < 0 || b >= m) continue; // 边界检查
            if(st[a][b]) continue; // 检查是否已访问
            if(g[a][b] == '#') continue; // 检查是否为障碍物

            st[a][b] = true; // 标记相邻节点为已访问
            q.push({a, b}); // 将相邻节点加入队列
        }
    }
}

🚀 BFS 的优化与扩展

• 双向 BFS：在某些情况下，可以使用双向 BFS 来加速搜索过程。双向 BFS 从起点和终点同时开始 BFS，当两个方向的搜索相遇时，可以找到最短路径。5
• A 算法*：在有权图中，可以使用 A* 算法来替代 BFS，A* 算法结合了 BFS 和启发式搜索，能够更高效地找到最短路径。5

通过以上分析，可以看出 BFS 是一种强大且灵活的搜索算法，适用于多种场景，特别是在无权图的最短路径问题中表现尤为突出。掌握 BFS 的原理和实现方法，对于解决实际问题具有重要意义。13