BFS 广度优先搜索算法

BFS 广度搜索算法

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

核心机制

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

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

特点：使用队列（FIFO）保证操作顺序

优化及其变种

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

示例：

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

步骤

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

#include <bits/stdc++.h> using namespace std; int maze[4][4] = {      {0, 0, 0, 0},      {1, 1, 0, 1},      {0, 0, 0, 0},      {0, 1, 1, 0}  }; int visited[4][4];  struct point {      int x;      int y;      int step;      queue<point> backpoint;  };  int dx[4] = {0, 0, -1, 1}; // 上 下 左 右  int dy[4] = {-1, 1, 0, 0};  queue<point> r;  int main() {      int n = 3,m = 3;      int startx = 0, starty = 0; // 起点位置      int endx = 3, endy = 3;  } 

2. 初始化队列

	point p;      p.x = startx;      p.y = starty;      p.step = 0;      visited[startx][starty] = 1;          r.push(p);          while(!r.empty()) {          if (r.front().x == endx && r.front().y == endy) {              printf("到达终点，坐标(%d, %d), 共%d步n", r.front().x, r.front().y, r.front().step);              return 0;      } 

3. 访问头节点附近节点

 for (int i = 0; i < 4; i++) {          point temp;          int tx = r.front().x + dx[i];          int ty = r.front().y + dy[i];          if (tx >= 0 && tx < n && ty >= 0 && ty < m && maze[tx][ty] == 0 && visited[tx][ty] == 0) {              temp.x = tx;              temp.y = ty;              temp.step = r.front().step + 1;              temp.backpoint = r.front().backpoint;              visited[tx][ty] = 1;              r.push(temp);          }      }      r.pop(); 

到达终点，坐标(3, 3), 共6步

通过队列回溯输出路径

定义一个parent来记录每一次的前驱节点坐标，注意要初始化起始点的前驱

pair<int, int> parent[4][4]; // 记录前驱节点  void printPath(int endX, int endY) {      vector<pair<int, int>> 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 << "最短路径：" << endl;      for (auto p : path) {          cout << "(" << p.first << ", " << p.second << ") ";      }      cout << endl;  }    

完整代码：

#include <bits/stdc++.h>  using namespace std;      int maze[4][4] = {      {0, 0, 0, 0},      {1, 1, 0, 1},      {0, 0, 0, 0},      {0, 1, 1, 0}  };      int visited[4][4];      struct point {      int x;      int y;      int step;  };      int dx[4] = {0, 0, -1, 1}; // 上 下 左 右  int dy[4] = {-1, 1, 0, 0};      queue<point> r;  pair<int, int> parent[4][4]; // 记录前驱节点      int flag = 0;      void printPath(int endX, int endY) {      vector<pair<int, int>> 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 << "最短路径：" << endl;      for (auto p : path) {          cout << "(" << p.first << ", " << p.second << ") ";      }      cout << endl;  }      int main() {      int n = 4,m = 4;      int startx = 0, starty = 0; // 起点位置      int endx = 3, endy = 3;          point p;      p.x = startx;      p.y = starty;      p.step = 0;      visited[startx][starty] = 1;      parent[startx][starty] = {-1, -1}; // 起点无前驱          r.push(p);          while(!r.empty()) {          if (r.front().x == endx && r.front().y == endy) {              printf("到达终点，坐标(%d, %d), 共%d步n", r.front().x, r.front().y, r.front().step);              flag = 1;              break;      }          for (int i = 0; i < 4; i++) {          point temp;          int tx = r.front().x + dx[i];          int ty = r.front().y + dy[i];          if (tx >= 0 && tx < n && ty >= 0 && ty < m && maze[tx][ty] == 0 && visited[tx][ty] == 0) {              temp.x = tx;              temp.y = ty;              temp.step = r.front().step + 1;              visited[tx][ty] = 1;              parent[tx][ty] = {r.front().x, r.front().y}; // 记录前驱              r.push(temp);          }      }      r.pop();  }      if (flag == 1) {      printPath(endx, endy);  }         if (flag == 0) puts("无法到达目标");  return 0;         } 

应用

用一个ctf逆向题来学习这个算法：

使用c++的队列来处理，先完成一次寻路，到达终点后再回溯最短路径

#include <bits/stdc++.h>  using namespace std;      int maps[58][58] = {{1,0,1}}; //省略地图     int visited[60][60] = {0};  struct point {      int x;      int y;      int step;      vector<pair<int, int>> path;  };  int dx[4] = {0, 0, -1, 1}; // 上 下 左 右  int dy[4] = {-1, 1, 0, 0};  queue<point> r;  string path1 = "S";  int main() {      int n = 56, m = 56;  // 实际地图大小      int startx = 1, starty = 1;      int endx = 15, endy = 32;      // 检查起始点和终点      if (maps[startx][starty] != 0) {          printf("起始点不可通行！起始点值：%dn", maps[startx][starty]);          return 0;      }      if (maps[endx][endy] != 0) {          printf("终点不可通行！终点值：%dn", maps[endx][endy]);          return 0;      }      printf("起始点：(%d,%d)，终点：(%d,%d)n", startx, starty, endx, endy);      point p;      p.x = startx;      p.y = starty;      p.step = 0;      visited[startx][starty] = 1;      r.push(p);      while (!r.empty()) {          point current = r.front();          int x = r.front().x, y = r.front().y;          // 判断是否到达终点          if (x == endx && y == endy) {              printf("到达终点，共%d步n", r.front().step);              for (int i = 0; i < current.path.size(); i++) {                  printf("第%d步: (%d, %d)", i+1, current.path[i].first, current.path[i].second);                  if (i > 0) {                      int dx = current.path[i].first - current.path[i-1].first;                      int dy = current.path[i].second - current.path[i-1].second;                      if (dx == -1) printf(" [从(%d,%d)向上移动]", current.path[i-1].first, current.path[i-1].second), path1 += "W";                      else if (dx == 1) printf(" [从(%d,%d)向下移动]", current.path[i-1].first, current.path[i-1].second), path1 += "S";                      else if (dy == -1) printf(" [从(%d,%d)向左移动]", current.path[i-1].first, current.path[i-1].second), path1 += "A";                      else if (dy == 1) printf(" [从(%d,%d)向右移动]", current.path[i-1].first, current.path[i-1].second), path1 += "D";                  }              printf("n");          }              std::cout << "结果为：" << path1 << 'n';              return 0;          }          for (int j = 0; j < 4; j++) {              int tx = x + dx[j];              int ty = y + dy[j];              // 修正边界检查和通行条件              if (tx >= 0 && ty >= 0 && tx < n && ty < m &&                  maps[tx][ty] == 0 && visited[tx][ty] == 0) {                  point temp;                  temp.x = tx;                  temp.y = ty;                  temp.step = current.step + 1;                  temp.path = current.path;  // 复制当前路径                  temp.path.push_back({tx, ty});  // 添加新位置                  r.push(temp);                  visited[tx][ty] = 1;              }          }          r.pop();      }      puts("未找到结果！");      return 0;  }