迷宫路径搜索：广度优先搜索（BFS）详解

---

1. 什么是广度优先搜索（BFS）？

广度优先搜索（BFS） 是一种在图或网格结构中逐层扩展节点的搜索算法，适合用于解决最短路径问题。
特点：

1. 逐层扩展：按距离从近到远逐层访问节点。
2. 最短路径保证：在无权图中，BFS找到的路径总是最短的。
3. 依赖队列结构：利用队列先进先出的特性来实现节点扩展。

在迷宫中，BFS 的应用如下：

• 每个格子视为一个节点。
• 上、下、左、右为节点之间的邻接关系。
• 起点到终点的最短路径可以通过 BFS 找到。

---

2. BFS解决迷宫路径问题的步骤

1. 初始化队列：将起点加入队列。
2. 标记访问：避免重复访问，记录已访问的节点。
3. 逐步扩展：从当前节点扩展到其四个方向的邻居，加入队列。
4. 路径记录：通过辅助数组 prev 记录路径中的前驱节点，用于反推完整路径。
5. 终止条件：找到终点（出口）时停止搜索。
6. 路径反推：从终点开始，根据前驱节点反向回溯到起点，得到最短路径。

---

3. BFS代码实现（完整代码）

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

// 定义方向
const int DIRECTIONS[4][2] = {
    {0, 1},  // 右
    {1, 0},  // 下
    {0, -1}, // 左
    {-1, 0}  // 上
};

// 迷宫状态
const int PATH = 0;     // 可行路径
const int WALL = 1;     // 墙
const int VISITED = 2;  // 已访问

// BFS 实现
bool bfsShortestPath(vector<vector<int>>& maze, int rows, int cols, vector<pair<int, int>>& path) {
    if (maze.empty() || maze[0][0] == WALL || maze[rows - 1][cols - 1] == WALL) {
        return false; // 起点或终点是墙
    }

    // 定义队列，存储当前坐标
    queue<pair<int, int>> q;
    q.push({0, 0});

    // 辅助数组记录前驱节点
    vector<int> prev(rows * cols, -1); // -1 表示无前驱
    maze[0][0] = VISITED; // 标记起点已访问

    // BFS 主循环
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        // 判断是否到达出口
        if (x == rows - 1 && y == cols - 1) {
            // 反推路径
            int idx = x * cols + y;
            while (idx != -1) {
                path.push_back({idx / cols, idx % cols});
                idx = prev[idx];
            }
            reverse(path.begin(), path.end()); // 路径从起点到出口
            return true;
        }

        // 扩展四个方向
        for (auto [dx, dy] : DIRECTIONS) {
            int nx = x + dx, ny = y + dy;

            // 检查边界条件和访问状态
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && maze[nx][ny] == PATH) {
                maze[nx][ny] = VISITED; // 标记已访问
                q.push({nx, ny});       // 新节点入队
                prev[nx * cols + ny] = x * cols + y; // 记录前驱
            }
        }
    }
    return false; // 无法到达出口
}

int main() {
    // 输入迷宫
    vector<vector<int>> maze = {
        {0, 0, 1, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 0, 1},
        {1, 1, 1, 0, 0},
        {0, 0, 0, 1, 0}
    };

    int rows = maze.size();
    int cols = maze[0].size();

    vector<pair<int, int>> path; // 用于存储路径

    // 执行 BFS
    if (bfsShortestPath(maze, rows, cols, path)) {
        cout << "找到最短路径：" << endl;
        for (const auto& p : path) {
            cout << "(" << p.first << ", " << p.second << ") ";
        }
        cout << endl;
    } else {
        cout << "无法到达终点" << endl;
    }

    return 0;
}

---

4. 代码详解

1. 初始化数据

   • 迷宫表示：maze 是输入的二维数组，0 表示路径，1 表示墙。
   • 起点和终点：起点为 (0, 0)，终点为 (rows - 1, cols - 1)。
   • 辅助数据结构：
     • queue 用于存储待处理的节点。
     • prev 数组记录路径信息。

2. BFS 主循环

   • 每次从队列中取出一个节点，扩展其四个方向的邻居。
   • 若扩展的节点是可行路径（未访问且不为墙），将其加入队列，并记录前驱节点。
   • 当队列为空或找到终点时，退出循环。

3. 路径反推

   • 若找到出口，则通过 prev 数组从终点反推到起点，得到完整路径。
   • 使用 reverse 函数将路径反转，从起点到终点输出。

4. 终止条件

   • 若在扩展过程中找到出口，立即结束搜索。
   • 若队列为空且未找到出口，则无解。

---

5. 示例运行

输入迷宫：

0 0 1 0 0
0 1 0 1 0
0 0 0 0 1
1 1 1 0 0
0 0 0 1 0

输出结果：

找到最短路径：
(0, 0) (0, 1) (1, 2) (2, 2) (2, 3) (3, 3) (4, 3) (4, 4)

---

6. 时间和空间复杂度

1. 时间复杂度：

   • 每个节点最多访问一次，每次访问最多检查四个方向。
   • 假设迷宫大小为 ( n \times m )，则时间复杂度为 ( O(n \times m) )。

2. 空间复杂度：

   • 队列最多存储 ( O(n \times m) ) 个节点。
   • prev 数组的大小为 ( O(n \times m) )。
   • 总空间复杂度为 ( O(n \times m) )。

---

7. BFS的优势与改进

优势：

1. 保证最短路径：逐层扩展，路径最短。
2. 简单高效：使用队列和循环即可实现。

改进方向：

1. 双向 BFS：同时从起点和终点进行搜索，缩短搜索时间。
2. 启发式搜索：结合 A* 算法，引入代价估计函数（如曼哈顿距离），适合大规模图。

---

8. 总结

通过 BFS，可以高效解决迷宫路径搜索问题。其核心逻辑是逐层扩展节点，记录访问状态与前驱关系，最终反推路径。完整代码实现了从输入迷宫到输出路径的全过程，便于理解和实践。