队列

by.Qin3Yu

本文将通过使用队列和广度优先搜索算法一步一步完成BFS算法走迷宫最短路径问题，题目描述和完整代码在文章末尾。
特别声明：本文为了尽可能使用简单描述，可能部分专有名词使用不准确。文章内容主要讲究简单明了，我妈看了都能学会！

文中所有代码默认已使用std命名空间

using namespace std;

概念速览

什么是队列？

  • 队列（Queue）是一种先进先出（First-In-First-Out，FIFO）的数据结构，与栈相反，最先进入的数据会被最先处理。它类似于现实生活中排队的概念，最先排队的人能第一个买到票，最后排队的人最后买到票。

优势：

  1. 简单易懂：队列的概念非常直观，且大部分情况下只涉及队列两段的操作，操作简单。
  2. 先进先出：队列遵循FIFO原则，适用于需要按照添加顺序进行处理的场景。
  3. 高效：向队列的两端添加/移除元素的操作的时间复杂度为O(1)。

缺点：

  1. 随机访问困难：在队列中间插入或删除元素的操作相对复杂，通常需要重新排列元素。
  2. 容量有限：队列的容量是有限的，当队列已满时无法继续添加元素。
  • 此外，使用队列还要导入以下头文件：
#include <queue>

什么是BFS算法？

  • 以下内容较为抽象，您可以选择性略读，在后文中会详细讲解。

  • BFS（广度优先搜索）是一种图遍历算法，BFS从给定的起始节点开始并展开其相邻节点，然后依次遍历其相邻节点的相邻节点，依此类推，直到遍历完所有可达的节点。

  • BFS的基本思想是按照层级逐层遍历，即从起始节点开始，首先访问其所有的相邻节点，然后再访问相邻节点的相邻节点，以此类推。这样可以保证先访问的节点距离起始节点更近。

BFS的过程一般使用队列来实现，具体步骤如下：

  1. 将起始节点放入队列中，并将其标记为已访问。
  2. 从队列中取出一个节点，访问该节点并将其未访问的相邻节点放入队列中。
  3. 标记取出的节点的相邻节点为已访问。
  4. 重复步骤2和3，直到队列为空或找到目标。

ps.本文的代码案例会涉及部分基础 vector 操作和 结构体 的定义，如遇到问题可参考我的往期博文，本文将在默认读者已经掌握 vector顺序表 的前提下讲解案例。
【C++数据结构 | 顺序表速通】使用顺序表完成简单的成绩管理系统.by.Qin3Yu
\color{Red}{}

队列相关操作

声明队列（ queue ）

  • 队列是一种基础的数据结构，我们可以直接使用 queue<T> name; 声明一个队列，其中 T 代表队列内存放数据的数据类型，name 表示队列的名字。在本文中，我们在队列中存储的数据为迷宫地图上的点 Point ，因此，我们先声明一个 Point 结构体，然后声明一个存放 Point 的队列 q ：
//构造函数，一个point类型包含x表示行和y表示列
struct Point {
    int x, y;
    Point(int i = 0, int j = 0) : x(i), y(j) { }
};
//声明一个成员类型为Student的队列q
queue<Point> q;

入队与取值（ push_back & front ）

  • 队列的简单之处就在于它只需要考虑队列两端的操作。通常情况下，我们只会向队尾添加元素，push_back(val); 方法可以用来向队尾添加一个元素，称为入队。
  • 在本文案例中，我们需要将迷宫的起点第一个入队，让程序知道该从哪里“出发”：
Point start(0, 0);  //实例化一个起点 ( 0 , 0 )，即地图的左上角
q.push(start);  //将起始点放入队列
  • 将元素入队以后，我们还需要在调用时获取他的值，q.front(); 方法将会返回队头元素的值；
Point cur = q.front();  //实例化一个点cur，用来保存当前的点，即 ( 0 , 0 )
//让程序知道，自己现在走到哪个点了

出队与判空（ pop & empty ）

  • 当程序在迷宫中出发后，将不会再回头走走过的路，这也是广度优先搜索的特点。q.pop(); 方法将删除队头元素，称为出队：
q.pop();  //将队头元素弹出
  • 在上述例子中，我们将会把起点出队。但是在代码运行时，我们通常不知道队列中是否还有元素，若队列为空，我们还使用 p.pop() ，可能会导致程序崩溃。因此，在出队之前，我们通常需要使用 q.empty() 判断队列是否为空，称为判空：
while (!q.empty()) {  //如果队列内还有剩余元素（不为空）
    q.pop();  //则一直出队
}
至此，队列的基本用法讲解完毕，是不是很简单（=
后文是BFS相关内容，会涉及到顺序表的操作

BFS算法实现

细说BFS算法

  • 广度优先搜索（ BFS , Breadth First Search ）是一种基础的图遍历算法，他的核心为搜索初始点的相邻点：
    相邻搜索

  • 然后再搜索相邻点的相邻点，直到搜索完全部范围或搜索到目标为止：
    广度搜索

  • 如图所示，BFS算法会逐层向外搜索，搜索范围逐渐扩散，越来越广，因此而得名。

因此，对于BFS算法，我们需要关心以下五个内容（下文统称为BFS五要素）：

  1. 遍历范围（迷宫的大小）；
  2. 初始点和目标点（即迷宫的起点和终点）；
  3. 搜索方向（在本例中，我们搜索上下左右四个方向，通常情况下也是如此）；
  4. 访问标记（即是否已经访问过需要访问的位置，BFS不存在二次访问）；
  5. 父结点 （即我是因为访问了哪个节点，才需要访问这个结点）。

初始化迷宫地图

  • 既然要走迷宫，那么就要先有迷宫地图。在本题中，题目要求使用10×10规格的地图，但此处为了便于讲解，我们使用4×4规格的地图，原理都是相同的。若要改为10×10规格，改变对应变量即可（详见结尾代码）。

地图

  • 在上面的地图中，每个格子代表一个点，用对应的字母表示，A为起点，P为终点，白色代表可通行路径，黑色代表障碍物。
  • 如何用代码实现以上地图结构？遵循BFS五要素：
    1. 遍历范围
// 迷宫大小为 n 行 m 列
const int n = 4;
const int m = 4;
// 用二维数组表示迷宫的状态信息，0 表示空白，1 表示障碍
int maze[n][m] = {
    {0, 0, 1, 0},
    {0, 0, 0, 0},
    {1, 1, 0, 1},
    {0, 0, 0, 0},};

2. 初始点和目标点

Point start(0, 0);  //起点（左上角）
Point endPoint(n - 1, m - 1);  //终点（右下角）

3. 搜索方向

//用二维数组表示方向，分别对应上下左右四个方向，后文称为方向数组
int direction[4][2] = {
    {-1, 0}, {1, 0}, {0, -1}, {0, 1}};

4. 访问标记

//用二维数组记录是否访问，地图上的每个点都对应一个bool值
bool visited[n][m];

5. 父节点

//BFS不走回头路，所以每个结点只有一个父结点
//用二维数组记录父结点，地图上的每个点（除起点外）都对应一个父结点
Point parent[n][m];

检索相邻点

  • 我们先将起点放入队列，作为搜索的初始点：
q.push(start);  //将起始点放入队列
visited[start.x][start.y] = true;  //将起始点标记为已经访问
  • 随后，我们要开始检索初始点的相邻点
while (!q.empty()) {  //如果队列中还有元素则继续循环
    Point cur = q.front();  //将队列的头值传入 当前结点cur
    q.pop();  //出队
    for (int i = 0; i < 4; i++) {  //分别遍历当前结点的四个方向的相邻节点
        int nx = cur.x + direction[i][0];  //根据当前节点 cur 的位置以及方向数组，计算相邻节点的位置
        int ny = cur.y + direction[i][1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m
            && maze[nx][ny] == 0 && !visited[nx][ny]) {  //检查相邻节点是否超出边界和是否是障碍
            visited[nx][ny] = true;  // 标记相邻节点为已访问
            q.push(Point(nx, ny));  // 将相邻节点加入队列
            parent[nx][ny] = cur;  // 记录相邻节点的父节点为当前节点
        }
    }
}
  • 以上代码可能较为难懂，部分读者可能产生“为什么能确定搜索出的路径为最短路径”的疑问，我们结合下图来看：

出入队

图中用颜色的深浅代表哪些结点是被同时访问的，以及相应的步数。颜色相同的结点代表同时被访问，深色的结点比浅色的结点先被访问，灰色的结点表示在终点被访问之前未被访问。

  • 我们用“层”来描述结点被访问的顺序，起点 A 自然是第一层被访问的。

  • 在 A 出队后，与A相邻的 B 、 E 入队，他们是第二层被访问的。

  • 在 B 出队后， B 的相邻结点 F 入队， F 因为第二层的 B 被访问后访问，所以他是第三层被访问的。但此时，程序并没有开始第四层访问，因为队列中还包含第二层的元素 E 。E 出队后，与 E 相邻的结点只有 F ，而 F 已经被访问过，所以不再入队。

  • 此时程序才开始第四层的访问，访问了与第三层结点 F 相邻的结点 G ，以此类推……
    访问层数

  • 直到我们访问到第七层，终点 P 被搜索到，这也就意味着最短路径为7步。

终点处理（ 路径回溯 ）

  • 在搜索到终点后，我们要如何获得从起点到终点的路径？
  • 我们可以通过回溯的方法，由终点根据结点的父结点倒推出路径。根据BFS算法不走回头路的特点，每个结点只有唯一的一个父结点，我们可以利用这个特性，从终点逆推出走向起点的路径：

回溯路径

  • 从终点 P 开始出发，P 的父结点为 O ，O 的父结点为 K ，以此类推，E 的父结点为起点 A 。因此，我们在每次逆推时都将结点的坐标或代号记录下来，即可获得获得一条完整的从终点走向起点的路径。我们再将其反转，即可得到由起点走向终点的最短路径：
if (cur.x == endPoint.x && cur.y == endPoint.y) {  //如果当前点的坐标与终点坐标相同
    vector<Point> path;  //创建一个顺序表 path，用于存放路径。
    Point p = cur;  //创建一个结点 p，存放当前结点（即终点） 
    while (p.x != start.x || p.y != start.y) {  //如果p不是起始点，则继续循环
        path.push_back(p);  //将节点 p 添加到路径 path 中
        p = parent[p.x][p.y];  //更新节点 p 为其父节点
    }
    path.push_back(start);  //循环结束后，将起始点 start 添加到路径中
    reverse(path.begin(), path.end());  //最后，反转路径 path 的顺序，以得到从起始点到终点的正序路径
    return path;
}

打印路径

  • 在上文的代码中，由于返回的是一条包含先后顺序的路径，所以用 vector顺序表 作为返回类型是最合适的。
  • 同时，如果队列全部排空后我们仍然未找到终点，则说明从起点无法到达终点：
vector<Point> BFS() {
    while (!q.empty()) {  //如果队列中还有元素则继续循环
        //此处放置上文讲的BFS算法
    }
    return vector<Point>();  // 如果无法到达终点，返回空路径
}
  • 我们将打印路径的过程写在主函数中。接下来，只需要用 for 循环搭配 vector 的 empty() 方法即可遍历顺序表，将路径打印出来。其中包含顺序表的知识点，本文将不再赘述：
int main() {
    vector<Point> path = BFS();
    if (path.empty()) {
        cout << "无法到达终点" << endl;
    }
    else {
        cout << "最短路径长度为：" << path.size() - 1 << endl << endl;
        cout << "路径详细走法：" << endl;
        for (int i = 0; i < path.size() - 1; i++) {  //最后一个单独打印，防止结尾打印箭头
            cout << "( " << path[i].x << " , " << path[i].y << " )" << "  ->  ";
            if (i % 5 == 0 )
                cout << endl;  //每打印5个就换一行，方便观察
        }
        cout << "( " << n - 1 <<" , "<< m - 1 << " )" << endl << endl;  //最后一个单独打印，防止结尾打印箭头
    }
    system("pause");
    return 0;
}
至此，BFS算法的具体实现讲解完毕（=

完整项目代码

题目：使用代码走出一个规格为（ n × m ）的迷宫，并返回最短路径和其步数。
ps.本文用规格为（ 10 × 10 ）的迷宫举例，需要其他规格只需修改代码内相应变量即可。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 定义坐标类，x和y分别代表行和列
struct Point {
    int x, y;
    Point(int i = 0, int j = 0) : x(i), y(j) { }  //构造函数
};

// 迷宫大小为 n 行 m 列
const int n = 10;
const int m = 10;

// 迷宫的状态信息，0 表示空白，1 表示障碍，(行，列)
int maze[n][m] = {
    {0, 0, 0, 0, 1, 0, 1, 0, 1, 0},  // 0
    {0, 1, 0, 0, 0, 1, 0, 0, 0, 0},  // 1
    {0, 0, 0, 1, 0, 0, 1, 1, 0, 0},  // 2
    {0, 1, 0, 0, 0, 1, 0, 0, 0, 0},  // 3
    {0, 1, 0, 1, 0, 0, 0, 1, 0, 0},  // 4
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},  // 5
    {1, 1, 1, 1, 1, 1, 1, 1, 0, 1},  // 6
    {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},  // 7
    {1, 1, 1, 1, 0, 0, 0, 1, 1, 1},  // 8
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}   // 9
  // 0  1  2  3  4  5  6  7  8  9
};

// 定义起点和终点
Point start(0, 0);
Point endPoint(n - 1, m - 1);

// 定义已访问标记数组
bool visited[n][m];

// 定义四个方向
int direction[4][2] = {
    {-1, 0}, {1, 0}, {0, -1}, {0, 1}
};

// 定义父节点数组
Point parent[n][m];

// BFS函数实现
vector<Point> BFS() {
    queue<Point> q;  //定义队列 q
    q.push(start);  //将起始点放入队列
    visited[start.x][start.y] = true;  //将起始点标记为已经访问

    while (!q.empty()) {  //如果队列中还有元素则继续循环
        Point cur = q.front();  //将队列的头值传入 cur 并弹出
        q.pop();

        //如果 cur 是终点，则回溯路径
        if (cur.x == endPoint.x && cur.y == endPoint.y) {  
            vector<Point> path;  //创建一个空的路径 path，用于存储最终的路径。
            Point p = cur;  //创建一个临时变量 p，初始化为当前节点 cur
            while (p.x != start.x || p.y != start.y) {  //如果p不是起始点，则继续循环
                path.push_back(p);  //将节点 p 添加到路径 path 中
                p = parent[p.x][p.y];  //更新节点 p 为其父节点，可以通过父节点数组 parent 来获取父节点的位置
            }
            path.push_back(start);  //循环结束后，由于起始点 start 还未添加到路径中，将其添加到路径 path 的末尾
            reverse(path.begin(), path.end());  //最后，反转路径 path 的顺序，以得到从起始点到终点的正序路径
            return path;
        }

        //如果cur不是终点，则遍历当前节点 cur 的相邻节点，并将未访问过的相邻节点加入队列
        for (int i = 0; i < 4; i++) {  //遍历四个方向的相邻节点
            int nx = cur.x + direction[i][0];  //根据当前节点 cur 的位置以及方向数组 direction[i] 的值，计算相邻节点的位置
            int ny = cur.y + direction[i][1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && maze[nx][ny] == 0 && !visited[nx][ny]) {  //检查相邻节点是否超出边界和是否是障碍
                visited[nx][ny] = true;  // 标记相邻节点为已访问
                q.push(Point(nx, ny));  // 将相邻节点加入队列
                parent[nx][ny] = cur;  // 记录相邻节点的父节点为当前节点
            }
        }
    }
    return vector<Point>();  // 如果无法到达终点，返回空路径
}

int main() {
    vector<Point> path = BFS();
    if (path.empty()) {
        cout << "无法到达终点" << endl;
    }
    else {
        cout << "最短路径长度为：" << path.size() - 1 << endl << endl;
        cout << "路径详细走法：" << endl;
        for (int i = 0; i < path.size() - 1; i++) {  //最后一个单独打印，防止结尾打印箭头
            cout << "( " << path[i].x << " , " << path[i].y << " )" << "  ->  ";
            if (i % 5 == 0 )
                cout << endl;  //每打印5个就换一行，方便观察
        }
    cout << "( " << n - 1 <<" , "<< m - 1 << " )" << endl << endl;  //最后一个单独打印，防止结尾打印箭头
    }
    system("pause");
    return 0;
}
# 算法 # c++ # 数据结构 # 广度优先 # 图搜索算法
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

avatar 开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

avatar 开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

avatar 开放原子开发者工作坊