@Author：Runsen

編程的本質來源于算法，而算法的本質來源于數學，編程只不過將數學題進行代碼化。 ---- Runsen

深度優先搜索和廣度優先搜索作為應用廣泛的搜索算法，一般是必考算法。

深度優先算法（DFS）

深度優先算法的本質是回溯算法，多數是應用在樹上，一個比較典型的應用就是二叉樹的中序遍歷。

DFS的實現考慮要以下幾個問題即可：

①．邊界范圍：即搜索終止條件，遞歸結束條件。

②．可供選擇的范圍列表：所有可供選擇的范圍列表。

③．已做出的選擇列表：標記當前已經做出的選擇。

深度優先搜索是圖論中的經典算法，利用深度優先搜索算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS算法。

根據深度優先搜索的特點，采用遞歸函數實現比較簡單。

廣度優先算法（BFS）

先訪問完當前頂點的所有鄰接點，然后再訪問下一層的所有節點，該算法適用于解決最短、最小路徑等問題，但是構建廣度優先算法需要維護自己的隊列。

比如，二叉樹的層次遍歷，我們大概會有如下幾個步驟：

• 向Queue中放入root節點。
• 只要這個Queue中有元素就一直遍歷。</

總結

以上是生活随笔為你收集整理的七十九、深度和广度优先搜索算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。