深度搜尋算法（Depth-First-Search，簡稱DFS）是一種用於遍歷或搜尋樹或圖的算法，其核心思想是遞歸和回溯。該算法沿著樹的深度遍歷樹的節點，儘可能深的搜尋樹的分支，當節點v的所在邊都己被探尋過或者在搜尋時結點不滿足條件，搜尋將回溯到發現節點v的那條邊的起始節點，這一過程一直進行到已發現從源節點可達的所有節點為止，如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個進程反覆進行直到所有節點都被訪問為止。
深度搜尋算法的特點包括：
遞歸或棧實現：深度優先搜尋可以通過遞歸或棧來實現，遞歸實現代碼量較少，但對於規模較大的圖或樹可能會導致棧溢出。
廣泛的套用：該算法常用於解決圖的遍歷問題，如迷宮問題、求解最短距離等。
回溯法的主要方法：深度搜尋是回溯法的主要方法，沿著一條路一直走，走不通再回溯到上一節點，選擇其他路徑。
深度搜尋的實現方式包括：
遞歸實現：從根節點開始遍歷，深入到樹或圖的最深層，然後回溯並搜尋其他分支。
棧實現：使用一個棧來存儲未訪問的節點，訪問每個節點時將其彈出並將其相鄰節點推入棧中。
深度搜尋的時間複雜度為O(n)，其中n為圖中節點的數量，最糟糕的情況算法時間複雜度為O(n!)。