制作迷宮地圖和行走路線（6）

說在前面

在繪制迷宮地圖時，除了深度優(yōu)先搜索算法，我們還可以使用廣度優(yōu)先搜索算法。因為地圖信息是由二維數(shù)組maze來決定的，所以無論是采用哪種算法，最終畫出來的圖形是一樣的，區(qū)別在于繪制的過程不同。

廣度優(yōu)先搜索算法通過設置隊列數(shù)據(jù)結構，采用先進先出的順序，依次繪制每個通道節(jié)點的相鄰位置，直至繪制出整個地圖。今天我們就來研究使用廣度優(yōu)先搜索算法繪制地圖、采用廣度優(yōu)先搜索算法尋找并繪制最短路徑路線圖的方法。

第5節(jié)?使用廣度優(yōu)先搜索算法繪制二維迷宮

因為本節(jié)課是建立在上一節(jié)課內(nèi)容的基礎上，二維數(shù)組maxe和book的含義均保持不變，只有少量函數(shù)調用發(fā)生了變化，所以我們只分析變化部分的代碼。

首先是主函數(shù)部分，把調用函數(shù)dfs()使用深度優(yōu)先搜索算法繪制迷宮，改成調用函數(shù)bfs()使用廣度優(yōu)先搜索算法繪制迷宮。參考代碼如下：

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) # 使用廣度優(yōu)先搜索繪制二維迷宮

自定義函數(shù)bfs()有兩個參數(shù)r和c，分別表示當前格子在二維數(shù)組maze中的行、列下標。若當前位置(r, c)為未訪問過的通道，則先設置book[r][c]=1標記位置(r, c)來過了。然后將位置(r, c)加入到隊列q中。之后就是出隊、入隊等常用隊列操作手法了。

先將隊首元素出隊，調用函數(shù)draw_rectangle()在該處繪制白色矩形。然后依次將(r, c)周圍的通道位置加入到隊列中，并依次處理隊列元素，直至隊列為空，就把與(r, c)連通的所有位置都繪制成白色矩形了。

自定義函數(shù)及函數(shù)頭說明如下：

'''函數(shù)功能：使用廣度優(yōu)先搜索來生成迷宮 函數(shù)名：dfs(r, c)參數(shù)表：r,c -- 表示當前格子在二維數(shù)組maze中的行列下標。返回值：把二維數(shù)組book當做全局變量，直接使用畫筆繪制迷宮通道，不需要返回值。'''def bfs(r, c):    from queue import Queue  #引入queue模塊FIFO隊列Queue    q = Queue()    # 標記(r, c)來過    book[r][c] = 1    q.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] = 1                q.put((i, j))

2.使用廣度優(yōu)先搜索算法尋找并繪制最短路徑：

繪制好迷宮地圖以后，就可以輸入起點和終點坐標，尋找連接二者的路徑了。因為在繪制地圖過程中，二維數(shù)組book的值發(fā)生了變化，所以需要先將book歸零，以便重新遍歷地圖。

與深度優(yōu)先搜索算法不同的是，使用廣度優(yōu)先搜索算法搜索路徑時，需要定義一個字典path來記錄每個節(jié)點的入隊介紹人（即前驅節(jié)點），起點的前驅為其本身。有了字典path，我們就可以通過從終點開始，遍歷路徑上各節(jié)點的前驅節(jié)點，從而實現(xiàn)逆序繪制路徑功能。

我們從起點(r1, c1)開始，調用函數(shù)bfs_ans()，使用廣度優(yōu)先搜索來尋找路徑，并返回存儲了各節(jié)點的前驅節(jié)點信息的字典path。最后調用函數(shù)print_path()逆序繪制路徑。

主函數(shù)中調用函數(shù)的代碼如下：

# 使用廣度優(yōu)先搜索來尋找路徑book = [[0] * w for i in range(h)] # 將book歸零，重新遍歷地圖book[r1][c1] = 1 # 標記起點已經(jīng)去過了path = bfs_ans(r1, c1)  # 使用廣度優(yōu)先搜索來尋找路徑print_path()     # 輸出使用廣度優(yōu)先搜索獲得的路徑

自定義函數(shù)bfs_ans()有兩個參數(shù)r1和c1，表示起點在二維數(shù)組maze中的行、列下標。

函數(shù)bfs_ans()與bfs()的算法結構相似，都是先將起點坐標入隊，再按照隊列基本操作處理。區(qū)別僅在于循環(huán)體中。因為bfs()函數(shù)需要繪制出所有可通行的位置，故循環(huán)條件為隊列不為空；但是bfs_ans()函數(shù)是找到終點就可以跳出循環(huán)了。此外，在bfs_ans()函數(shù)中，我們每讓一個新位置(i, j)加入隊列，就要執(zhí)行語句path[(i, j)] = (r, c)，將其入隊介紹人（前驅節(jié)點）添加到字典path中，以便今后繪制路徑。

自定義函數(shù)及函數(shù)頭說明如下：

'''函數(shù)功能：使用廣度優(yōu)先搜索來尋找路徑函數(shù)名：bfs_ans(r1, c1)參數(shù)表：r1,c1 -- 表示起點在二維數(shù)組maze中的行列下標。返回值：把列表book當做全局變量，返回存儲了各格子前驅位置的字典path。''' def bfs_ans(r1, c1):    from queue import Queue  # 引入queue模塊FIFO隊列Queue    q = Queue()    path = {(r1, c1): (r1, c1)} #用字典記錄其前驅位置，起點的前驅為其本身    # 標記(r1, c1)來過    book[r1][c1] = 1    q.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] = 1                q.put((i, j))                path[(i, j)] = (r, c)    return path

這里順便給出一個思考題：如果你想要順序繪制路徑，該怎么處理呢？

答案就是先將字典path中鍵和值的位置互換，使得字典元素以前驅節(jié)點的坐標為鍵、后繼節(jié)點的坐標為值，終點的后繼為其本身。這樣就可以從起點開始繪制路徑了。

自定義函數(shù)及函數(shù)頭說明如下：

'''函數(shù)功能：根據(jù)path的值，逆序繪制使用廣度優(yōu)先搜索獲得的路徑函數(shù)名：print_path()參數(shù)表：直接使用字典path的元素值，不需要任何參數(shù)。返回值：直接利用畫筆繪制路線，不需要返回值。''' 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)]    # 根據(jù)前驅結點信息，逆序遍歷路徑，起點的前驅為其本身    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)

到此，關于制作迷宮地圖和行走路線的系列文章就告一段落了。根據(jù)文章的介紹，我們知道了，在已有二維數(shù)組maze的基礎上，可以使用深度優(yōu)先或廣度優(yōu)先搜索算法來繪制地圖，雖然繪制過程不同，但最終形成的圖像是一樣的。

在使用深度優(yōu)先搜索算法尋找路徑時，如果我們隨機打亂周圍位置的訪問順序，就能夠獲得一條隨機搜索路線；使用廣度優(yōu)先搜索算法獲得的是最短路徑，我們可以通過設置字典鍵值對的方式，在前驅節(jié)點和后繼節(jié)點之間建立聯(lián)系，從而繪制出路線圖。

課后練習

迷宮問題是學習二維數(shù)組、棧和隊列的經(jīng)典案例。在本專題的系列文章中，我們使用隊列來實現(xiàn)廣度優(yōu)先搜索算法，使用遞歸函數(shù)來實現(xiàn)深度優(yōu)先搜索算法，并沒有使用到棧結構。但是在浙教版選考信息技術教材中，對遞歸函數(shù)的掌握要求較低，而對棧的掌握要求較高，所以更多的題目中是要求用棧來模擬遞歸過程，實現(xiàn)非遞歸算法。

現(xiàn)在請你使用棧來模擬遞歸過程，使用深度優(yōu)先搜索算法尋找路徑，并用綠色畫筆把路徑繪制出來。

需要本文PPT、源代碼和課后練習答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專注Python算法，感興趣就一起來！

相關優(yōu)秀文章：

閱讀代碼和寫更好的代碼

最有效的學習方式

Python算法之旅文章分類