# 《深度優先遍歷》專題 # 深度優先遍歷 深度優先搜索算法（英語：Depth-First-Search，DFS）是一種用于遍歷或搜索樹或圖的算法。沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點 v 的所在邊都己被探尋過，搜索將回溯到發現節點 v 的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點并重復以上過程，整個進程反復進行直到所有節點都被訪問為止。屬于盲目搜索。 深度優先搜索是圖論中的經典算法，利用深度優先搜索算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。 因發明「深度優先搜索算法」，約翰 · 霍普克洛夫特與羅伯特 · 塔揚在 1986 年共同獲得計算機領域的最高獎：圖靈獎。 截止目前（2020-02-21），深度優先遍歷在 LeetCode 中的題目是 129 道。在 LeetCode 中的題型絕對是超級大戶了。而對于樹的題目，我們基本上都可以使用 DFS 來解決，甚至我們可以基于 DFS 來做廣度優先遍歷。并不一定說 DFS 不可以做 BFS（廣度優先遍歷）的事情。而且由于 DFS 通常我們可以基于遞歸去做，因此算法會更簡潔。 在對性能有很高邀請的場合，我建議你使用迭代，否則盡量使用遞歸，不僅寫起來簡單快速，還不容易出錯。 另外深度優先遍歷可以結合回溯專題來聯系，建議將這兩個專題放到一起來學習。 ## 題目 這是我近期總結的幾個 DFS 題目，后續會持續更新～ - [200. 島嶼數量](https://leetcode-cn.com/problems/number-of-islands/solution/mo-ban-ti-dao-yu-dfspython3-by-fe-lucifer-2/) 中等 - [695. 島嶼的最大面積](https://leetcode-cn.com/problems/max-area-of-island/solution/mo-ban-ti-dao-yu-dfspython3-by-fe-lucifer/) 中等 - [979. 在二叉樹中分配硬幣](https://leetcode-cn.com/problems/distribute-coins-in-binary-tree/solution/tu-jie-dfspython3-by-fe-lucifer/) 中等