当前位置：首页 > article >正文

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

article 2025/2/8 7:46:46

引言：当算法遇见迷宫

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