制作迷宫地图和行走路线（4）

说在前面

前3节课我们分别构造了不含环和含环两种迷宫，然后使用深度优先搜索算法寻找路径，并绘制了路线图。不含环迷宫中任意两个点之间的连通路径都是唯一的，含环迷宫则可能存在多条不同路径。采用深度优先搜索算法时，若随机设置每次前进的方向，则每次寻找的路径都可能不一样。

在搜索迷宫路径时，除了深度优先搜索算法，我们还可以使用广度优先搜索算法。它采用队列数据结构，依次处理相邻格子，可以寻找到最短路径。今天我们就来研究广度优先搜索算法寻路，并绘制最短路径路线图。

第4节 使用广度优先搜索算法寻找路径

自定义函数bfs_ans()使用广度优先搜索算法寻找路径。它采用队列数据结构来存储各个格子的行列下标。先将起点坐标加入队列，然后依次处理队列中的元素，直至队列为空或找到终点为止。

参考代码如下：

'''函数功能：使用广度优先搜索来寻找路径函数名：bfs_ans(r1, c1)参数表：r1,c1 -- 表示起点在二维数组maze中的行列下标。返回值：把列表maze当做全局变量，返回存储了各格子前驱位置的字典path。''' def bfs_ans(r1, c1):    from queue import Queue  # 引入queue模块FIFO队列Queue    q = Queue()    path = {(r1, c1): (r1, c1)} #用字典记录其前驱位置，起点的前驱为其本身    # 标记(r1, c1)来过    maze[r1][c1] = 1    q.put((r1, c1))    while not q.empty():        r, c = q.get()        if r==r2 and c==c2: #遇到终点，跳出循环            break        for (i, j) in route[r][c]:             if maze[i][j] == 0: #将满足条件的相邻格子加入队列                maze[i][j] = 1                q.put((i, j))                path[(i, j)] = (r, c) #记录(i, j)的前驱位置(r, c)    return path

代码说明：

循环体内的操作步骤如下：首先将队头元素出队，把它作为当前格子(r, c)来处理，然后判断(r, c)是否为终点，若是直接跳出循环；否则遍历当前格子的相邻格子，将满足条件的相邻格子加入队列。同时，为了记录路径，还需要把每个格子的前驱位置存储到字典path中。

path中键值对的形式为(i, j):(r, c)，键和值都是记录格子位置的元组，表示(r, c)是(i,j)的前驱位置。我们设置起点的前驱位置为它本身，即设置path的初值为path = {(r1, c1): (r1, c1)}。之后在处理当前格子(r, c)时，每添加一个相邻格子(i,j)到队列中，就记录path[(i, j)] = (r, c)，表示(r, c)是(i, j)的前驱位置。

最后返回字典path，以便后续绘制路线图。

2.逆序绘制使用广度优先搜索获得的路径：

有了字典path，我们就可以绘制路线图了。因为字典path存储的是每个格子的前驱位置，所以只能从终点开始逆序绘制路线。

自定义函数print_path()根据path的值，逆序绘制使用广度优先搜索获得的路径。

它先将画笔放到终点位置，然后根据前驱位置信息，逆序遍历路径。利用起点的前驱为其本身可以结束循环。最后绘制起点位置。参考代码如下：

'''函数功能：根据path的值，逆序绘制使用广度优先搜索获得的路径函数名：print_path()参数表：直接使用字典path的元素值，不需要任何参数。返回值：直接利用画笔绘制路线，不需要返回值。''' def print_path():      tt.speed(1)    # 路线粗细    tt.pensize(size*0.3)    tt.color("green")    tt.penup()    tt.goto(start_x+c2*size, start_y-r2*size)    tt.pendown()    pos = path[(r2, c2)]    # 根据前驱结点信息，逆序遍历路径，起点的前驱为其本身    while path[pos] != pos:        tt.goto(start_x+pos[1]*size, start_y-pos[0]*size)        pos = path[pos]    tt.goto(start_x+pos[1]*size, start_y-pos[0]*size)

3.主函数部分增加代码：

我们可以在上一节内容的基础上增加广度优先搜索并绘制路径的功能。只需在主函数部分增加如下代码即可：

# 使用广度优先搜索来寻找路径maze =[[0] * w for i in range(h)] # 将maze归零，重新遍历地图maze[r1][c1]= 1  # 标记起点已经去过了path =bfs_ans(r1, c1)  # 使用广度优先搜索来寻找路径print_path()     # 输出使用广度优先搜索获得的路径

代码说明：

前面我们已经绘制了迷宫，并使用深度优先搜索算法绘制了路径。因为前面搜索路径时修改了数组maze的值，为了重新遍历地图，我们需要将maze归零。先标记起点(r1, c1)已经去过了，然后调用函数bfs_ans(r1, c1)，并返回path，最后调用函数print_path()绘制路径。

这样深度优先搜索和广度优先搜索获得的路径就能够同时呈现在地图上。

课后练习

本例中我们使用字典path记录了各位置的前驱位置，故而可以遍历字典path，从终点到起点逆序输出路径。但通常我们更习惯顺序输出路径。你能否想办法对字典path中的元素加以处理，使得能够实现从起点到终点顺序绘制路径的功能呢？

需要本文PPT、源代码和课后练习答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

我们专注Python算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类