广度优先搜索

广度优先搜索（Breadth First Search，简称BFS）是一种用于遍历或搜索树或图的算法。它从树的根（或图中的某个节点）开始，探索邻近的节点，然后再对每个邻近节点做同样的操作，层层递进。这个过程持续进行，直到找到目标节点或遍历完所有节点。

BFS的核心思想是使用队列来实现搜索过程。在搜索的每一步中，算法都会取出队列中的第一个节点，检查它是否为目标节点，如果不是，就将其所有未访问过的邻近节点加入队列。这样，队列中的节点就像是在按层次扩展，先进入队列的节点会先被探索。

这种搜索策略不仅可以用来确定从源节点到目标节点是否存在路径，还可以用来找到最短路径，因为在无权图中，BFS首次访问到的路径便是最短路径。

队列解决迷宫问题

思路：从一个节点开始，寻找所有接下来能继续走的点，继续不断寻找，知道找到出口

使用队列存储当前正在考虑的节点

C++

#include <iostream> // 引入输入输出流库
#include <vector> // 引入向量容器库
#include <queue> // 引入队列容器库

using namespace std; // 使用标准命名空间

const int N = 10; // 定义迷宫的大小为 10x10

// 初始化迷宫数组，1 表示墙壁，0 表示通路
vector<vector<int>> maze = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
    {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
    {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
    {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
    {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
    {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
    {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
    {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

// 定义四个可能的移动方向
vector<pair<int, int>> dirs = {
    {1, 0}, // 向右移动
    {-1, 0}, // 向左移动
    {0, -1}, // 向上移动
    {0, 1} // 向下移动
};

// 打印路径函数
void print_r(const vector<pair<int, int>>& path) {
    for (const auto& node : path) { // 遍历路径中的每个节点
        cout << "(" << node.first << ", " << node.second << ") "; // 打印节点坐标
    }
    cout << endl; // 换行
}

// 迷宫路径搜索函数
bool maze_path_queue(int x1, int y1, int x2, int y2) {
    queue<pair<int, int>> q; // 创建队列用于存储待探索的节点
    q.push({x1, y1}); // 将起点加入队列
    vector<pair<int, int>> path; // 创建路径向量

    while (!q.empty()) { // 当队列不为空时循环
        auto curNode = q.front(); // 获取队列前端的节点作为当前节点
        q.pop(); // 弹出当前节点
        path.push_back(curNode); // 将当前节点加入路径

        if (curNode.first == x2 && curNode.second == y2) { // 如果当前节点是终点
            print_r(path); // 打印路径
            return true; // 返回成功
        }

        for (const auto& dir : dirs) { // 遍历每个可能的移动方向
            int nx = curNode.first + dir.first; // 计算新位置的 x 坐标
            int ny = curNode.second + dir.second; // 计算新位置的 y 坐标
            if (maze[nx][ny] == 0) { // 如果新位置是通路
                q.push({nx, ny}); // 将新位置加入队列
                maze[nx][ny] = 2; // 标记新位置为已访问
            }
        }
    }

    cout << "没有路径。" << endl; // 如果没有找到路径，打印信息
    return false; // 返回失败
}

// 主函数
int main() {
    maze_path_queue(1, 1, 8, 8); // 调用迷宫路径搜索函数
    return 0; // 程序结束
}

Python

from collections import deque

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

dirs = [
    lambda x, y: (x + 1, y),
    lambda x, y: (x - 1, y),
    lambda x, y: (x, y - 1),
    lambda x, y: (x, y + 1)
]


def print_r(path):
    curNode = path[-1]

    realpath = []

    while curNode[2] == -1:
        realpath.append(curNode[0:2])
        curNode = path[curNode[2]]

    realpath.append(curNode[0:2])  # 起点
    realpath.reverse()
    for node in realpath:
        print(node)


def maze_path_queue(x1, y1, x2, y2):
    queue = deque()
    queue.append((x1, y1, -1))
    path = []
    while len(queue) > 0:
        curNode = queue.pop()
        path.append(curNode)
        if curNode[0] == x2 and curNode[1] == y2:
            # 终点
            print_r(path)
            return True
        for dir in dirs:
            nextNode = dir(curNode[0], curNode[1])
            if maze[nextNode[0]][nextNode[1]] == 0:
                queue.append((nextNode[0], nextNode[1], len(path) - 1))  # 后续节点进队，记录哪个节点带他来的
                maze[nextNode[0]][nextNode[1]] = 2  # 标记为已经走过
    else:
        print("没有路")
        return False


maze_path_queue(1, 1, 8, 8)