演算法小課堂：走迷宮之DFS vs BFS_其它 - 程式人生

DFS可以尋找最短路徑，其實BFS也可以，它們兩者最大的區別在於搜尋方式的不同。

BFS即廣度優先搜尋，以走迷宮為例形象的說就是當你在一個節點時，不是一條 ... 程式人生>實用技巧>其它>演算法小課堂：走迷宮之DFSvsBFS 演算法小課堂：走迷宮之DFSvsBFS 阿新•來源：網路•發佈：2021-01-30 技術標籤：演算法小課堂演算法pythondfsbfsalgorithm 演算法小課堂：走迷宮之DFSvsBFS 前言DFS走迷宮演算法思路程式碼實現細節樣例測試 BFS走迷宮演算法原理程式碼實現細節樣例測試 兩種方法的對比總結Reference 前言   上期我們說到DFS的經典入門題目——Fibonaci數列的第n項，這次我們來說下DFS或者BFS較為經典的走迷宮題目解法，很多關於迷宮類題目的母題都是這個了，而且也很容易理解，沖沖衝！   我們約定迷宮裡出口用S表示，出口用T表示，可以通行（不是一方通行）的格子用點表示，障礙物（即不能通行）的格子用*表示。

  類似如下的輸入形式： ....s* .***** ....*. ***..* .T....   今天我們利用兩種思路，分別是DFS和BFS來解決這個問題。

CSDN(゜-゜)つロ乾杯 DFS走迷宮 演算法思路   DFS方法來解決的思路類似於我們上次說的老鼠走迷宮，真就無限套娃唄……從一條路一直走到底A，如果碰到障礙物，就退回一步到B，在B處嘗試完所有的可能方向，如果還不行，繼續回退到C，迴圈往復，直到找到可行的通路。

如果沒有，則表示沒有通路。

  這裡有幾個點需要注意： 怎麼表示走的過程，實際上就是你在二維陣列操作的過程走的過程中座標移動時不應該超過地圖範圍迷宮可能有多條通路，應該選擇最近的一條回退過程中怎麼標記已經檢視過的節點避免迴圈bug最後一個是我們整體的邏輯思路：即上面一段話的程式實現   因為是開始講解DFS的演算法題解，我會盡量詳細，讓大家沒有太多理解負擔，本身也是為了通俗易懂的講解演算法知識。

程式碼實現細節   首先我們來讀取迷宮資料並標記入口和出口，以及各種障礙物 #讀取maze資料的行列數 row,col=list(map(int,input().split())) #儲存maze資料的二維陣列 maze_data=[] foriinrange(row): #maze_data.append([sforsininput()]) In=input() maze_data.append([sforsinIn]) #startingpoint s=(0,0) forrinmaze_data: if's'inr: #獲取起點的行列座標，從0開始計數 s=(maze_data.index(r),r.index('s'))   接下來我們定義走的方向，由於我們只是上下左右移動（四連通），其實就是行列座標的加一減一： #行走方向，四連通方式 direction=[[-1,0],[0,-1],[1,0],[0,1]]   還有走的時候不應該超過maze的範圍，即超過範圍的行列座標pass #checkvalidcoordinates defcheck(x,y): nonlocalrow,col return0<=x>>dfs_maze() 56 ....s* .***.* ...... ***..* .T.*.* NoSolution Usingtime:0.00400s >>>dfs_maze() 56 ....s* .***** ....*. ***..* .T.... Get2practicalpaths Shortestdistance:13 Usingtime:0.00700s   如果你在dfs的過程中加入路徑記錄的操作就可以顯示最短的路徑啦，這裡我直接給出最短路徑的標識（用m標記）： mmmmS* m***** mmmm*. ***m.* .Tmm.. BFS走迷宮 演算法原理   DFS可以尋找最短路徑，其實BFS也可以，它們兩者最大的區別在於搜尋方式的不同。

BFS即廣度優先搜尋，以走迷宮為例形象的說就是當你在一個節點時，不是一條路走到底，而是先上下左右的格子都走一遍，在其中把可行的子節點加到佇列裡，慢慢地擴大你的搜尋半徑。

就好像把水倒在棋盤格慢慢地從中心格點浸沒到周圍的點。

  注意BFS常用的資料結構就是佇列，先進先出FIFO。

（關於佇列的知識小夥伴自行百度學習喔~）   BFS自帶最短特性，在起始點已知的情況下，每一步都是以起始點為中心向外半徑不斷增大輻射的，所以一旦找到可行的通路，就是最短的路徑，是不是很nice！ 程式碼實現細節   maze的讀入和一些常用變數和方向的定義跟DFS其實是一樣，這裡我們在BFS中加入儲存最短路徑的操作。

fromqueueimportQueue #儲存最短路徑上每個節點的上一個節點位置 Parent=[[0for_inrange(max_r_c)]for_inrange(max_r_c)] #列印最短路徑 defprint_result_path(x,y,flag='m'): """ printmazedatawithshortestpathway Args: x(int):rowindexstartfrom0 y(int):colindexstartfrom0 flag(str,optional):shortestpathwaymarker.Defaultsto'm'. """ nonlocalParent,maze_data,row whileParent[x][y]: maze_data[x][y]=flag #freshcoordinates x,y=Parent[x][y] #showmaze foriinrange(row): print(''.join(str(s)forsinmaze_data[i]))   其中，Parent是儲存最短路徑上每一個節點父節點位置的一個數組，通過它我們可以標記出整條道路。

  我們來看看BFS的核心邏輯： #initialQueue Q=Queue() #addstartingpoint Q.put((s[0],s[1],0)) #currentstepinitial step=0 #whenqueueisnotempty whileQ.qsize()!=0: #getnextnode x,y,step=Q.get() #endpointcheck ifmaze_data[x][y]=='T': print("Shortestdistance:{}".format(step)) print_result_path(x,y) return #marknode vis[x][y]=1 fordindirection: nx,ny=x+d[0],y+d[1] ifcheck(nx,ny)andmaze_data[nx][ny]!='*'andnotvis[nx][ny]: #addnextpossiblenodeinqueue Q.put((nx,ny,step+1)) #recordparentnodecoordinates Parent[nx][ny]=[x,y]   其中，Python裡隊Queue的用法請自行百度，code裡也只是展示了最基本的用法~   由於BFS的自帶最短特性，所以我們只需要進入節點時標記，而不需要去掉標記的步驟，因為不存在回溯的過程，一旦找到出口那就是最短路徑啦~ 樣例測試   我們來看看測試結果： >>>bfs_maze() 56 ....s* .***.* ...... ***..* .T.*.* NoSolution Usingtime:0.00300s >>>bfs_maze() 56 ....s* .***** ....*. ***..* .T.... Shortestdistance:13 mmmms* m***** mmmm*. ***m.* .mmm.. Usingtime:0.02200s 兩種方法的對比   這裡BFS的執行時間是0.02s左右，而DFS是0.007s左右，小夥子你有問題不講code德。

原理上BFS是最短特性搜尋，應該比DFS全域性搜尋更快。

  其實BFS相比DFS在結構上由於使用了佇列，在開闢記憶體塊和存取上操作更多，問題規模數不大的情況下自然也就相對來說耗費了更多的時間。

簡單問題上不能顯示出BFS的優勢，我們這裡來測試一個複雜一些的maze。

  如以下的一個maze： ********************** *...*...**.**.....*..T *.*...*.......***.*.** *.*.*..**..****...*.** ***.******....***.*..* *..........**..**....* *****.******...*****.* *.....*...*******..*.* *.*******......S.*...* *................*.*** ******************.***   來看看各自的測試結果（省略輸入的列印）： >>>dfs_maze() …… Get768practicalpaths Shortestdistance:51 Usingtime:0.10801s >>>bfs_maze() …… Shortestdistance:51 ********************** *...*...**.**mmmmm*mmT *.*...*...mmmm***m*m** *.*.*..**.m****..m*m** ***.******m...***m*m.* *....mmmmmm**..**mmm.* *****m******...*****.* *mmmmm*...*******..*.* *m*******......S.*...* *mmmmmmmmmmmmmmm.*.*** ******************.*** Usingtime:0.04600s   可以看到BFS的優勢已經顯示出來，DFS找到了所有的可能通路，一共768條，然後選出最少的一條。

在只需要得到最短路徑及其長度的情況下，顯然BFS的方法更優 總結   相信通過本次的DFS和BFS迷宮經典問題講解，大家可以對利用DFS來解決問題有一個更好的理解，關於DFS和BFS的相愛相殺我們後續還會繼續嗑瓜~ 快來跟小刀一起頭禿~ Reference   [1]演算法小課堂：走迷宮之DFSvsBFS algorithmbfsdfs演算法演算法小課堂 使用rust開發stm32 «上一篇 杭電oj2034 下一篇» 相關推薦 EF模型驗證CodeforcesRound#756(Div.3)E2.EscapeTheMaze(hardversion)排程器25—程序凍結JDK的下載與安裝PATA1030TravelPlan(30分)Spark實驗1_Linux系統的安裝和常用命令洛谷p5490線段樹掃描線+離散化【金字塔原理】 搜尋 熱門文章 EF模型驗證 2022-01-10 CodeforcesRound#756(Div.3)E2.EscapeTheMaze(hardversion) 2022-01-10 排程器25—程序凍結 2022-01-10 ADS 基礎教學 Mysql入門 Sql入門 Android入門 Docker入門 Go語言入門 Ruby程式入門 Python入門 Python進階 Django入門 Python爬蟲入門 ADS 人氣文章 EF模型驗證 2022-01-10 CodeforcesRound#756(Div.3)E2.EscapeTheMaze(hardversion) 2022-01-10 排程器25—程序凍結 2022-01-10 JDK的下載與安裝 2022-01-10 PATA1030TravelPlan(30分) 2022-01-10 Spark實驗1_Linux系統的安裝和常用命令 2022-01-10 洛谷p5490線段樹掃描線+離散化 2022-01-10 【金字塔原理】 2022-01-10 SpringBoot基礎 2022-01-10 RPM包的構建說明 2022-01-10 熱門標籤 Java基礎資料結構與演算法經驗分享劍指offer其他題解圖論程式人生每日一題安卓微控制器PAT演算法&資料結構PTAPython學習leetcode刷題java學習筆記演算法與資料結構reactjspython基礎 ADS