C++ 广度优先搜索 (BFS) 学习记录

~~DFS 都学完了，不接着看看 BFS 吗？~~ 其实是我做题用到了。。

广度优先搜索是一种用于遍历或搜索树或图的算法。所谓“广度优先”，就是在遍历更深的节点之前，先把这一层的节点全部遍历。

我的理解是这样的：

还是有一个人去某景区旅游，他现在在景区入口，景区里的一些路，有的能通到出口，有的不能。~~怎么又是你。。~~

这个人呢喜欢欣赏沿途的风景，他不喜欢一次走到底，而是每走到一个交叉路口，都会把这个路口上的景点全看完，再往下走。

他走过了第一条路，来到了分叉点。他把这个分叉点对应的几个景点全游览一遍，然后才选择一条路往下走。走到下一个分叉点，再游览这一层所有的景点，然后才往下走……

如果把这样一个景区抽象为一个图，那么也就是说，广度优先的搜索就是不走完这一层绝不罢休。

与深度优先搜索的比较

广度优先搜索由于是逐层遍历，不需要回溯，因此也不像深度优先那样，容易因递归过多导致栈溢出。

一般来说，对于一道需要用搜索的题目，使用广度优先和深度优先理论上都可以解出来，但是广度优先需要考虑时间问题，深度优先则需要考虑空间问题。

复杂度

假设图中有 V 个顶点和 E 条边。

时间复杂度	空间复杂度
O(V+E) (最坏情况) 或 O(V) (稀疏图)	O(V)

最坏情况是指遍历所有的顶点和边；稀疏图是边数与顶点数成正比的图。

实现

最短路径走迷宫

我们以经典迷宫问题为例，用 BFS 实现最短路径查找：

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

struct Node { int x, y, step; };

int dx[] = {-1,1,0,0};  // 方向数组：上下左右
int dy[] = {0,0,-1,1};

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> maze(n);
    for(auto &s : maze) cin >> s;
    
    queue<Node> q;
    // 寻找起点
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if(maze[i][j] == 'S') {
                q.push({i,j,0});
                maze[i][j] = '#';  // 标记已访问
            }
    
    while(!q.empty()) {
        auto cur = q.front();
        q.pop();
        
        // 尝试四个方向
        for(int i=0; i<4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if(nx>=0 && nx<n && ny>=0 && ny<m) {
                if(maze[nx][ny] == 'T') {  // 找到终点
                    cout << cur.step + 1;
                    return 0;
                }
                if(maze[nx][ny] == '.') {  // 可通行
                    q.push({nx, ny, cur.step+1});
                    maze[nx][ny] = '#';    // 标记已访问
                }
            }
        }
    }
    cout << -1;  // 无法到达终点
    return 0;
}

代码关键点说明：

C++ 虽说有现成的队列容器 queue，但是这里我们使用结构体存储坐标和步数。其实我觉得是因为不需要那么复杂的容器，直接一个结构体就能满足需求了。

方向数组也是我们的老朋友了，在 DFS 中我们也用到了，作用是通过预定义方向简化代码。

逐层扩展是 BFS 的核心，每次处理完一层才会处理下一层，保证最先到达终点的路径最短。

算法步骤总结

将起点加入队列并标记
循环直到队列为空：
- 取出队首元素
- 如果是终点则返回步数
- 向四个方向扩展：
  - 越界则跳过
  - 遇到障碍或已访问则跳过
  - 合法位置则入队并标记
队列为空仍未找到则返回 -1

应用场景

BFS 特别适合解决以下类型的问题：

最短路径问题（无权图）
连通性检测
层级遍历（如二叉树的层序遍历）
扩散类问题（如病毒传播模拟）

注意事项

记得在入队时立即标记已访问，否则可能重复入队导致 MLE
使用方向数组可以让代码更简洁
队列的 size 在每次处理完一层后可以获取当前层的节点数（适用于需要区分层的情况）
当需要记录路径时，可以增加一个 prev 指针或使用二维数组记录前驱节点

~~最后还是要说：BFS 写起来比 DFS 麻烦，但找最短路径是真的香！~~