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。
- 给定一个
步骤
- 初始化地图 标记数组 方向数组：
#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;}
- 初始化队列
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; }
- 访问头节点附近节点
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("起始点不可通行！起始点值：%d\n", maps[startx][starty]); return 0; } if (maps[endx][endy] != 0) { printf("终点不可通行！终点值：%d\n", 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;}