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。
步骤
[*]初始化地图 标记数组 方向数组：
#include <bits/stdc++.h>
using namespace std;
int maze = {
{0, 0, 0, 0},
{1, 1, 0, 1},
{0, 0, 0, 0},
{0, 1, 1, 0}
};
int visited;
struct point {
int x;
int y;
int step;
queue<point> backpoint;
};
int dx = {0, 0, -1, 1}; // 上 下 左 右
int dy = {-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 = 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;
int ty = r.front().y + dy;
if (tx >= 0 && tx < n && ty >= 0 && ty < m && maze == 0 && visited == 0) {
temp.x = tx;
temp.y = ty;
temp.step = r.front().step + 1;
temp.backpoint = r.front().backpoint;
visited = 1;
r.push(temp);
}
}
r.pop();到达终点，坐标(3, 3), 共6步
通过队列回溯输出路径
定义一个parent来记录每一次的前驱节点坐标，注意要初始化起始点的前驱
pair parent; // 记录前驱节点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 = p.first; y = p.second; } // 逆序输出路径 reverse(path.begin(), path.end()); cout
页:
[1]