BFS / DFS 模板

──────────────────────────────────────────────────────────────────────

圖的題目第一步永遠是翻譯：節點是什麼、邊是什麼。翻譯完之後，選 BFS 還是 DFS 只看一件事 — 要不要最短。

BFS：逐層擴散，第一次到達就是最短

from collections import deque

def bfs(start):
    q = deque([start])
    seen = {start}               # 進佇列時就標記，不是出佇列時
    steps = 0
    while q:
        for _ in range(len(q)):  # 一次處理一整層
            node = q.popleft()
            if node == target:
                return steps
            for nxt in neighbors(node):
                if nxt not in seen:
                    seen.add(nxt)
                    q.append(nxt)
        steps += 1
    return -1

進佇列時就標記已訪問是最常見的 bug 來源 — 出佇列才標記的話，同一個節點會被重複塞進佇列。

例題：1091. Shortest Path in Binary Matrix、127. Word Ladder

多源 BFS

「所有起點同時開始擴散」時，把全部起點一次放進初始佇列就好，其他完全一樣：

    q = deque(所有起點)
    seen = set(所有起點)

例題：994. Rotting Oranges

DFS：走到底再回頭，適合連通性與計數

def dfs(r, c):
    if not (0 <= r < m and 0 <= c < n) or grid[r][c] != '1':
        return
    grid[r][c] = '0'                 # 標記已訪問（就地改，省一個 visited）
    for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
        dfs(r + dr, c + dc)

網格題把「越界」和「不該走」合併成一個 guard 寫在函式開頭，比在呼叫前判斷乾淨得多。遞迴深度可能到 $O(mn)$，面試時可以主動提「資料再大我會改成顯式的 stack」。

例題：200. Number of Islands、79. Word Search、547. Number of Provinces

拓撲排序：有依賴關係就是它

「先修課程」「建置順序」這類題目，本質是問有向圖有沒有環：

from collections import deque

indegree = [0] * n
graph = [[] for _ in range(n)]
for a, b in edges:               # b -> a（先做 b 才能做 a）
    graph[b].append(a)
    indegree[a] += 1

q = deque([i for i in range(n) if indegree[i] == 0])
order = []
while q:
    node = q.popleft()
    order.append(node)
    for nxt in graph[node]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:   # 所有前置都完成了才入列
            q.append(nxt)

return order if len(order) == n else []   # 長度不足代表有環

最後那行的長度檢查就是判環，別忘了。

例題：207. Course Schedule、210. Course Schedule II

需要複製結構時：用 map 記錄「舊 → 新」

Clone 類題目的關鍵是先建節點、放進 map，再遞迴處理鄰居，否則有環時會無限遞迴：

def clone(node):
    if node in old_to_new:
        return old_to_new[node]
    copy = Node(node.val)
    old_to_new[node] = copy          # 必須在遞迴之前放進去
    copy.neighbors = [clone(n) for n in node.neighbors]
    return copy

例題：133. Clone Graph

面試時的講法

先講圖怎麼建（鄰接表？就地用網格？），再講選 BFS 或 DFS 的理由 — 「要最短所以 BFS」「只問連不連通所以 DFS 比較省」。複雜度是 $O(V+E)$，網格題就是 $O(mn)$，講出來代表你知道每個節點只會被訪問一次。

更多題目 → #Graph