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

从底层原理到实际应用：BFS 算法借助队列征服迷宫

article 2025/4/1 21:49:37

文章目录

一.题目分析
二、算法思路
三、BFS 算法详解

☆BFS算法中队列的操作
1. 初始化队列
2. 标记节点已访问 & 记录初始距离
3. 循环处理队列（核心逻辑）
4. 完整 BFS 示例（迷宫最短路径）
关键操作总结

在算法领域，迷宫问题一直是经典的挑战。本文将为您深入剖析BFS（广度优先搜索）算法和队列数据结构的紧密联系，揭示它们是如何高效解决迷宫最短路径问题的。
在这里插入图片描述
输入样例：

输出样例：

一.题目分析

这是一道典型的 最短路径求解问题，迷宫中每个点移动距离为 1，且保证存在路径。由于 BFS（广度优先搜索）天然按 “层” 遍历的特性，能确保首次到达终点的路径就是最短路径，因此非常适合用 BFS 解决。

二、算法思路

数据初始化
- 用二维数组 g 存储迷宫地图。
- 用二维数组 dist 记录每个点到起点的最短距离，初始化为 -1（表示未访问）。
- 定义队列 q 用于 BFS 遍历。
BFS 遍历
- 起点 (1, 1) 入队，标记其距离为 0。
- 循环处理队列：取出队头节点，遍历上下左右四个方向。
- 对每个新位置，检查是否越界、是否是墙壁、是否已访问。若合法，更新距离并加入队列。
- 一旦到达终点 (n, m)，直接返回当前距离。

三、BFS 算法详解

BFS 是一种图遍历算法，核心思想是 按层遍历：

适用场景：求无权图的最短路径（如本题，每次移动距离相同）。
实现流程
1. 初始化队列，加入起点。
2. 标记起点已访问。
3. 循环：
  - 取出队头节点。
  - 遍历所有相邻节点。
  - 处理合法节点（标记访问、记录距离、入队）。
优点：确保首次到达终点的路径最短，时间复杂度低（本题中为 O(n×m)）。

【代码示例】

☆BFS算法中队列的操作

在 BFS（广度优先搜索）算法中，队列是核心数据结构，其操作贯穿整个搜索过程，具体操作步骤及代码示例如下：

1. 初始化队列

操作：创建队列，并将起始节点加入队列。这是 BFS 搜索的起点。

代码示例

#include <queue>
using namespace std;
queue<节点类型> q;  // 节点类型可为坐标、数值等，例如迷宫问题中常用坐标 pair<int, int>
// 假设起点为 (x1, y1)
q.push({x1, y1});

2. 标记节点已访问 & 记录初始距离

操作：为避免重复访问节点，需标记起始节点为 “已访问”，同时记录其到起点的距离（通常起始节点距离为 0）。

代码示例（以迷宫问题为例，用二维数组dist记录距离，初始值 -1 表示未访问）：

int dist[N][N];  // N 为问题规模
memset(dist, -1, sizeof dist);  // 初始化所有节点为未访问
dist[x1][y1] = 0;  // 起点距离为 0，同时隐含标记“已访问”

3. 循环处理队列（核心逻辑）

操作：只要队列不为空，就取出队头节点，遍历其所有相邻节点。

代码框架

while (!q.empty()) {
    auto t = q.front();  // 取出队头节点
    q.pop();  // 队头节点出队

    // 遍历相邻节点（以迷宫上下左右四方向为例）
    for (int i = 0; i < 4; i++) {
        int new_x = t.x + dx[i];  // dx、dy 为方向偏移数组
        int new_y = t.y + dy[i];

        // 检查新节点是否合法（越界、是否可通行等）
        if (new_x 不合法) continue; 

        // 若未访问过，标记访问、记录距离、入队
        if (dist[new_x][new_y] == -1) {
            dist[new_x][new_y] = dist[t.x][t.y] + 1;  // 距离+1
            q.push({new_x, new_y});  // 新节点入队
        }
    }
}

4. 完整 BFS 示例（迷宫最短路径）

#include <queue>
#include <cstring>
using namespace std;
#define PII pair<int, int>

const int N = 105;
int n, m;
int g[N][N];  // 迷宫地图
int dist[N][N];  // 距离数组
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};  // 方向

int bfs() {
    queue<PII> q;
    q.push({1, 1});  // 起点 (1,1)
    memset(dist, -1, sizeof dist);
    dist[1][1] = 0;

    while (!q.empty()) {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int x = t.first + dx[i], y = t.second + dy[i];
            // 检查越界、是否是墙壁、是否已访问
            if (x < 1 || x > n || y < 1 || y > m) continue;
            if (g[x][y] != 0) continue;
            if (dist[x][y] != -1) continue;

            dist[x][y] = dist[t.first][t.second] + 1;
            q.push({x, y});
            if (x == n && y == m) return dist[n][m];  // 到达终点直接返回，避免不必要的搜索，提高算法效率
        }
    }
    return dist[n][m];  // 题目保证有解，理论不执行，保证代码的完整性和健壮性
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &g[i][j]);
    printf("%d\n", bfs());
    return 0;
}