演算法筆記dfs,bfs - w3c學習教程

演算法筆記dfs,bfs,深度優先和廣度優先dfs bfs 是最常用的兩種搜尋方法，在各類演算法競賽中也是頻頻出現， 可參見2017藍橋杯的前4題均是搜尋題，所以. 演算法筆記dfs,bfs 2021-10-0302:38:58字數2212閱讀2132 深度優先和廣度優先‘(dfs、bfs)是最常用的兩種搜尋方法，在各類演算法競賽中也是頻頻出現，（可參見2017藍橋杯的前4題均是搜尋題），所以掌握兩種搜尋的適用場合和使用方法是很有必要的。

適用場合： bfs：常用在搜尋最短路徑的情景，一旦搜尋到可以結束，因為其深度一定是最短的。

dfs也可以但是就必須全部搜尋完才能判定最短的路徑。

dfs：所需要維護的空間少，這個跟其每次只需要維護一個方向的記錄有關。

使用方法： （即使用的資料結構和儲存方式） bfs：佇列 dfs：棧 具體見題目： 圍棋遊戲：對於給定的二維陣列，其中只有’x’和’o’，現在需要將其中被包圍的’o’替換成’x’。

（在邊緣的不算被包圍） 所以我們要找到矩陣邊緣的’o’，並以此為根找到與之相通的’o’，這些是不被包圍的，那麼剩下的就需要進行替換。

思路一：bfs publicclasspos }publicvoidsolve(charboard)}} for(inti=0;i=0 &&board[current.i][current.j-1]=='o') //右 if(current.j+1<=board[0].length-1 &&board[current.i][current.j+1]=='o') }}因為是廣度優先遍歷，每次都將能延伸的點探索完，所以要彈出隊首（queue.poll()），並將這個點符合要求的一層搜尋都加入隊尾。

這樣可以保證搜尋是一層一層的。

思路二：dfs classsolution }publicvoidsolve(charboard)}} for(inti=0;i=0 &&board[current.i][current.j-1]=='o') //右 if(current.j+1<=board[0].length-1 &&board[current.i][current.j+1]=='o') //如果上下左右都搜尋不到,本次搜尋結束，彈出stack stack.pop();}} }使用棧思路會很清晰：只要有一個符合要求的探索就continue，符合深度優先的定義。

彈出的時機：如果上下左右都搜尋不到,本次搜尋結束，彈出stack。

與bfs不同，bfs是每次都會彈出隊首，因為以後不會用到這個點了。

最後，還有一種遞迴的方法，其實也是dfs的一種，但是用的是遞迴函式。

publicvoidsolve(charboard)}} for(inti=0;i