BFS 广度优先搜索算法

BFS 广度搜索算法

BFS主要使用对图的遍历，通过队列的逐层扩展，按层次搜索所有可能的节点，确保找到最短的路径（无权图），BFS的本质是对图的暴力穷举，适合解决一些寻路的问题，比如找迷宫的最短路径
核心机制

使用队列驱动，时间复杂度通常为O(N)，N为状态数。空间复杂度为O(N)，储存所有当前层节点。

• 初始化：标记地图和障碍物，标记已经访问过的节点
  
• 循环处理：从队列的头节点来遍历之下的相邻位置
  
• 当队列为空遍历结束/找到终点
  

特点：使用队列（FIFO）保证操作顺序
优化及其变种

• 双向BFS（bidirectional BFS）：从起点和终端同时进行BFS，相遇时停下
  
• A*搜索：结合BFS和启发式函数，优先搜索更接近目标的节点
  

示例：

• 问题：
  
  
  
  • 给定一个 N x M 的二维矩阵表示迷宫
    
  • 
    
    
    
    • 0 表示可以通行的空地。
      
    
    
  • 1 表示障碍物，不可通行。
    
  • 起点为 (0, 0)，终点为 (N-1, M-1)。
    
  • 每次移动可以向上、下、左、右四个方向行走一格，求从起点到终点的最短路径步数。如果无法到达终点，返回 -1。
    
  
  

步骤

• 初始化地图 标记数组 方向数组：
  

1. #include <bits/stdc++.h>
2. using namespace std;
3. int maze[4][4] = {
5.     {0, 0, 0, 0},
7.     {1, 1, 0, 1},
9.     {0, 0, 0, 0},
11.     {0, 1, 1, 0}
13. };
14. int visited[4][4];
16. struct point {
18.     int x;
20.     int y;
22.     int step;
24.     queue<point> backpoint;
26. };
28. int dx[4] = {0, 0, -1, 1}; // 上 下 左 右
30. int dy[4] = {-1, 1, 0, 0};
32. queue<point> r;
34. int main() {
36.     int n = 3,m = 3;
38.     int startx = 0, starty = 0; // 起点位置
40.     int endx = 3, endy = 3;
42. }

复制代码

• 初始化队列
  

1.         point p;
3.     p.x = startx;
5.     p.y = starty;
7.     p.step = 0;
9.     visited[startx][starty] = 1;
11.   
13.     r.push(p);
15.   
17.     while(!r.empty()) {
19.         if (r.front().x == endx && r.front().y == endy) {
21.             printf("到达终点，坐标(%d, %d), 共%d步\n", r.front().x, r.front().y, r.front().step);
23.             return 0;
25.     }

复制代码

• 访问头节点附近节点
  

1.  for (int i = 0; i < 4; i++) {
3.         point temp;
5.         int tx = r.front().x + dx[i];
7.         int ty = r.front().y + dy[i];
9.         if (tx >= 0 && tx < n && ty >= 0 && ty < m && maze[tx][ty] == 0 && visited[tx][ty] == 0) {
11.             temp.x = tx;
13.             temp.y = ty;
15.             temp.step = r.front().step + 1;
17.             temp.backpoint = r.front().backpoint;
19.             visited[tx][ty] = 1;
21.             r.push(temp);
23.         }
25.     }
27.     r.pop();

复制代码

到达终点，坐标(3, 3), 共6步
通过队列回溯输出路径

定义一个parent来记录每一次的前驱节点坐标，注意要初始化起始点的前驱
[code]pair parent[4][4]; // 记录前驱节点void printPath(int endX, int endY) {    vector path;    int x = endX, y = endY;    // 从终点回溯到起点    while (x != -1 && y != -1) {        path.push_back({x, y});        auto p = parent[x][y];        x = p.first;        y = p.second;    }    // 逆序输出路径    reverse(path.begin(), path.end());    cout