深度優先搜尋（DFS）教學：原理、程式碼與時間複雜度

DFS 解決什麼問題

DFS 用「先把一條分支完全探索完，再試下一條」的方式，回答「從這裡出發能到達哪些地方？」這個問題。當路徑的結構比長度更重要時，這種順序特別有用：找出迷宮的出路、檢查圖中有沒有環、安排彼此相依的任務順序，或列出謎題的所有解。

與廣度優先搜尋不同，DFS 無法找到最短路徑。它的優點是記憶體中只需保留目前這條路徑，並且能自然地記錄每個節點「進入」和「完成」的時間點。

用白話說明原理

1. 把目前的節點標記為已拜訪。
2. 對每個尚未拜訪的鄰居，移動過去，並從那裡重複步驟 1。
3. 當一個節點已沒有未拜訪的鄰居，就算完成：回到你來的那個節點。
4. 回到起點且起點也沒有未拜訪的鄰居時，搜尋就結束了。

回到上一個節點稱為回溯（backtracking）。使用遞迴時，這件事由呼叫堆疊自動幫你完成。

逐步範例

使用與 BFS 文章相同的無向圖：A–B、A–C、B–D、C–D、C–E、D–F。從 A 出發，並依字母順序嘗試鄰居。

拜訪順序是 A、B、D、C、E、F，完成順序是 E、C、F、D、B、A。拓樸排序和強連通元件演算法用的就是完成順序。

Python 實作

遞迴版本最短，也最貼近原理：

def dfs(graph, node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)
    return visited
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(dfs(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

用串列能讓範例比較好讀，但 in 檢查是 O(n)。處理大型圖時，請另外用 set 判斷是否已拜訪。迭代版本使用明確的堆疊，可避開 Python 的遞迴深度限制；鄰居以反向順序推入，這樣彈出時就會維持原本的順序：

def dfs_iterative(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nxt in reversed(graph[node]):
            if nxt not in visited:
                stack.append(nxt)
    return order
print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

請注意與 BFS 的差別：這裡是在節點被彈出時才標記，所以同一個節點可能在堆疊中出現不只一次。這對 DFS 是正確的，也能維持真正的深度優先順序。

偵測有向圖中的環

DFS 的經典應用是為每個節點著色：白色（尚未見過）、灰色（在目前路徑上）、黑色（已完成）。一旦走到灰色節點，就代表有一條邊指回目前的路徑，也就是出現了環。

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    def visit(node):
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                return True              # back edge
            if color[nxt] == WHITE and visit(nxt):
                return True
        color[node] = BLACK
        return False
    return any(color[n] == WHITE and visit(n) for n in graph)
print(has_cycle({"a": ["b"], "b": ["c"], "c": ["a"]}))  # True
print(has_cycle({"a": ["b"], "b": ["c"], "c": []}))     # False

時間與空間複雜度

變化版本與常見錯誤

• 前序與後序：進入節點時記錄（前序），或完成節點時記錄（後序）。有向無環圖的反向後序就是一個拓樸順序。
• 連通元件：從每個仍未拜訪的節點各啟動一次新的 DFS；每次啟動就是一個元件。
• 迭代加深 DFS：以深度限制 0、1、2、… 重複執行 DFS。它像 BFS 一樣能找到最短路徑，又有 DFS 的低記憶體用量。
• 網格上的填色（油漆桶工具）就是對相同顏色的相鄰格子做 DFS 或 BFS。

其他常見錯誤：忘了用已拜訪集合（遇到任何環就會無窮迴圈）、使用可變的預設參數如 visited=[]（會在多次呼叫間共用），以及把無向邊指回父節點誤判為環。

何時使用 DFS 與實際應用

• DFS 適用於可達性判斷、偵測環、拓樸排序、連通元件與強連通元件、橋與關節點，以及搭配回溯法的窮舉搜尋。
• 需要最少步數時請改用 BFS，邊有權重時則用 Dijkstra 或 A*。
• 面試題目：島嶼數量、複製圖、課程表（偵測環）、二元樹的路徑總和、產生排列。
• 實際應用：建置系統與套件管理工具解析相依順序、編譯器分析控制流程、迷宮生成，以及走訪檔案系統或 HTML 文件的樹狀結構。