BFS 广度搜索算法
BFS主要使用对图的遍历，通过队列的逐层扩展，按层次搜索所有可能的节点，确保找到最短的路径（无权图），BFS的本质是对图的暴力穷举，适合解决一些寻路的问题，比如找迷宫的最短路径
核心机制
使用队列驱动，时间复杂度通常为O(N)，N为状态数。空间复杂度为O(N)，储存所有当前层节点。
- 初始化：标记地图和障碍物，标记已经访问过的节点
- 循环处理：从队列的头节点来遍历之下的相邻位置
- 当队列为空遍历结束/找到终点
特点：使用队列（FIFO）保证操作顺序
优化及其变种
- 双向BFS（bidirectional BFS）：从起点和终端同时进行BFS，相遇时停下
- A*搜索：结合BFS和启发式函数，优先搜索更接近目标的节点
示例：
- 问题：
- 给定一个 N x M 的二维矩阵表示迷宫
- 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();
通过队列回溯输出路径
定义一个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 |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
