制作迷宫地图和行走路线（6）
共 1297字，需浏览 3分钟
·
2022-05-22 13:33
说在前面
在绘制迷宫地图时，除了深度优先搜索算法，我们还可以使用广度优先搜索算法。因为地图信息是由二维数组maze来决定的，所以无论是采用哪种算法，最终画出来的图形是一样的，区别在于绘制的过程不同。
广度优先搜索算法通过设置队列数据结构，采用先进先出的顺序，依次绘制每个通道节点的相邻位置，直至绘制出整个地图。今天我们就来研究使用广度优先搜索算法绘制地图、采用广度优先搜索算法寻找并绘制最短路径路线图的方法。
第5节 使用广度优先搜索算法绘制二维迷宫
因为本节课是建立在上一节课内容的基础上，二维数组maxe和book的含义均保持不变，只有少量函数调用发生了变化，所以我们只分析变化部分的代码。
首先是主函数部分，把调用函数dfs()使用深度优先搜索算法绘制迷宫，改成调用函数bfs()使用广度优先搜索算法绘制迷宫。参考代码如下：
for i in range(h):for j in range(w):if maze[i][j] == 1 and book[i][j] == 0:tt.penup()bfs(i, j)
自定义函数bfs()有两个参数r和c，分别表示当前格子在二维数组maze中的行、列下标。若当前位置(r, c)为未访问过的通道，则先设置book[r][c]=1标记位置(r, c)来过了。然后将位置(r, c)加入到队列q中。之后就是出队、入队等常用队列操作手法了。
先将队首元素出队，调用函数draw_rectangle()在该处绘制白色矩形。然后依次将(r, c)周围的通道位置加入到队列中，并依次处理队列元素，直至队列为空，就把与(r, c)连通的所有位置都绘制成白色矩形了。
自定义函数及函数头说明如下：
'''函数功能：使用广度优先搜索来生成迷宫函数名：dfs(r, c)参数表：r,c -- 表示当前格子在二维数组maze中的行列下标。返回值：把二维数组book当做全局变量，直接使用画笔绘制迷宫通道，不需要返回值。'''def bfs(r, c):from queue import Queue #引入queue模块FIFO队列Queueq = Queue()# 标记(r, c)来过book[r][c] = 1q.put((r, c))while not q.empty():r, c = q.get()draw_rectangle(start_x+c*size-size//2, start_y-r*size+size//2, size, size, 'white')# (r, c)的上下左右位置d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]for (i, j) in d:if 0<=iand 0<=jand maze[i][j]==1 and book[i][j]==0: book[i][j] = 1q.put((i, j))
2.使用广度优先搜索算法寻找并绘制最短路径：
绘制好迷宫地图以后，就可以输入起点和终点坐标，寻找连接二者的路径了。因为在绘制地图过程中，二维数组book的值发生了变化，所以需要先将book归零，以便重新遍历地图。
与深度优先搜索算法不同的是，使用广度优先搜索算法搜索路径时，需要定义一个字典path来记录每个节点的入队介绍人（即前驱节点），起点的前驱为其本身。有了字典path，我们就可以通过从终点开始，遍历路径上各节点的前驱节点，从而实现逆序绘制路径功能。
我们从起点(r1, c1)开始，调用函数bfs_ans()，使用广度优先搜索来寻找路径，并返回存储了各节点的前驱节点信息的字典path。最后调用函数print_path()逆序绘制路径。
主函数中调用函数的代码如下：
# 使用广度优先搜索来寻找路径book = [[0] * w for i in range(h)] # 将book归零，重新遍历地图book[r1][c1] = 1 # 标记起点已经去过了path = bfs_ans(r1, c1) # 使用广度优先搜索来寻找路径print_path() # 输出使用广度优先搜索获得的路径
自定义函数bfs_ans()有两个参数r1和c1，表示起点在二维数组maze中的行、列下标。
函数bfs_ans()与bfs()的算法结构相似，都是先将起点坐标入队，再按照队列基本操作处理。区别仅在于循环体中。因为bfs()函数需要绘制出所有可通行的位置，故循环条件为队列不为空；但是bfs_ans()函数是找到终点就可以跳出循环了。此外，在bfs_ans()函数中，我们每让一个新位置(i, j)加入队列，就要执行语句path[(i, j)] = (r, c)，将其入队介绍人（前驱节点）添加到字典path中，以便今后绘制路径。
自定义函数及函数头说明如下：
'''函数功能：使用广度优先搜索来寻找路径函数名：bfs_ans(r1, c1)参数表：r1,c1 -- 表示起点在二维数组maze中的行列下标。返回值：把列表book当做全局变量，返回存储了各格子前驱位置的字典path。'''def bfs_ans(r1, c1):from queue import Queue # 引入queue模块FIFO队列Queueq = Queue()path = {(r1, c1): (r1, c1)} #用字典记录其前驱位置，起点的前驱为其本身# 标记(r1, c1)来过book[r1][c1] = 1q.put((r1, c1))while not q.empty():r, c = q.get()if r==r2 and c==c2:break# (r, c)的上下左右位置d = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]for (i, j) in d:if 0<=iand 0<=jand maze[i][j]==1 and book[i][j]==0: book[i][j] = 1q.put((i, j))path[(i, j)] = (r, c)return 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)
到此，关于制作迷宫地图和行走路线的系列文章就告一段落了。根据文章的介绍，我们知道了，在已有二维数组maze的基础上，可以使用深度优先或广度优先搜索算法来绘制地图，虽然绘制过程不同，但最终形成的图像是一样的。
在使用深度优先搜索算法寻找路径时，如果我们随机打乱周围位置的访问顺序，就能够获得一条随机搜索路线；使用广度优先搜索算法获得的是最短路径，我们可以通过设置字典键值对的方式，在前驱节点和后继节点之间建立联系，从而绘制出路线图。
课后练习
迷宫问题是学习二维数组、栈和队列的经典案例。在本专题的系列文章中，我们使用队列来实现广度优先搜索算法，使用递归函数来实现深度优先搜索算法，并没有使用到栈结构。但是在浙教版选考信息技术教材中，对递归函数的掌握要求较低，而对栈的掌握要求较高，所以更多的题目中是要求用栈来模拟递归过程，实现非递归算法。
现在请你使用栈来模拟递归过程，使用深度优先搜索算法寻找路径，并用绿色画笔把路径绘制出来。
需要本文PPT、源代码和课后练习答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。
我们专注Python算法，感兴趣就一起来！
相关优秀文章：