广度优先搜索（BFS）算法详解—

广度优先搜索（BFS）算法详解——以走迷宫问题为例

引言：当算法遇见迷宫

想象你置身于一个复杂的迷宫，如何在最短时间内找到出口？这个问题不仅存在于童话故事中，更是计算机科学中经典的路径搜索问题。本文将带你通过走迷宫问题，深入理解广度优先搜索（BFS）这一强大的算法工具。

一、BFS算法原理剖析

1.1 BFS & DFS

在这里插入图片描述

1.2 算法核心思想

广度优先搜索采用"层层推进"的策略：

使用队列数据结构管理待探索节点
在每一个点处，所有可能到达的不重复的下一个节点都会被添加到队列中

简单来说，在遇到岔路时，会进行分身,两边同时进行探索。

1.3 算法实现框架

void bfs(起点) {初始化队列标记起点已访问while (队列不为空) {取出队首节点if (到达终点) {返回结果}for (所有相邻节点) {if (节点合法且未访问) {标记已访问加入队列}}}
}

1.4 算法特性分析

时间复杂度： $O (V + E)$ （ $V$ 为顶点数， $E$ 为边数）
空间复杂度： $O (V)$
优势：保证找到最短路径
局限：空间开销较大

二、走迷宫问题建模

2.1 问题描述

给定一个 $n * m$ 的迷宫：

$0$ 表示可通行的路径
$1$ 表示障碍物
从左上角 $(1, 1)$ 出发，寻找到达右下角 $(n, m)$ 的最短路径

2.2 问题转化

将迷宫建模为图：

节点：每个可通行的格子
边：相邻可通行格子之间的连接
权重：每条边的权重为 $1$

三、BFS解法的精妙实现

ACWing 走迷宫

3.1 关键数据结构

队列：存储待探索节点
方向数组：定义移动方向
访问标记：记录已访问节点（这里标记数组和迷宫地图可以进行公用）

#include <iostream>
#include <queue>
using namespace std;const int MAXN = 107; // 最大地图尺寸
int maze[MAXN][MAXN]; // 迷宫地图
int n, m;             // 迷宫行数和列数// 定义节点结构
struct Node {int x, y;   // 当前坐标int steps;  // 已走步数Node(int x, int y, int steps) : x(x), y(y), steps(steps) {}
};// 方向数组：右、左、下、上
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};// BFS求解最短路径
int bfs(int startX, int startY) {queue<Node> q;q.push(Node(startX, startY, 0));maze[startX][startY] = 1; // 标记起点已访问while (!q.empty()) {Node current = q.front();q.pop();// 到达终点if (current.x == n && current.y == m) {return current.steps;}// 尝试四个方向for (int i = 0; i < 4; i++) {int nx = current.x + dx[i];int ny = current.y + dy[i];// 检查新位置是否合法if (nx < 1 || ny < 1 || nx > n || ny > m || maze[nx][ny]) {continue;}maze[nx][ny] = 1; // 标记已访问q.push(Node(nx, ny, current.steps + 1));}}return -1; // 如果没有找到路径
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> maze[i][j];}}cout << bfs(1, 1) << endl;return 0;
}