LeetCode 刷題日記
EP.13

EP.13 — Graph 入門：
DFS 在圖上長什麼樣子

#200 Number of Islands · #133 Clone Graph
— Grid DFS、visited 集合、adjacency list 三個核心概念

Joseph Chen

2024
5 min read
1.2k views

Tree 章節我們學了 DFS 和 BFS。Graph 是 Tree 的廣義版本：Tree 的每個節點只有一個父節點，而 Graph 的節點可以有任意多個鄰居，甚至形成環。

也因為 Graph 可能有環，DFS 在 Graph 上有一個 Tree 上不需要的額外步驟：visited 集合，防止無限遞迴。

這篇從最常見的兩種 Graph 題型入手：Grid（二維矩陣）和 Adjacency List（鄰接表）。

Graph 的兩種表示法

Grid（矩陣）

二維陣列，每個格子是一個節點。鄰居是上下左右四個方向。Number of Islands 就是這種形式。

grid = [ ["1","1","0"], ["1","0","0"], ["0","0","1"] ]

Adjacency List（鄰接表）

每個節點存一個鄰居列表。Clone Graph 就是這種形式。

# Node(val=1, neighbors=[2,4]) # Node(val=2, neighbors=[1,3]) # Node(val=3, neighbors=[2,4]) # Node(val=4, neighbors=[1,3])
🏝️

Part 1 — Number of Islands

#200 · Medium · Grid DFS

題目

給一個二維字元矩陣，"1" 代表陸地，"0" 代表水。 上下左右相連的陸地算一座島嶼，回傳島嶼總數。

思路：把「找到一塊陸地」變成「淹沒整座島」

遍歷整個 Grid。每次遇到 "1"，就進行一次 DFS，把這座島上所有相連的 "1" 都標記成已訪問（直接改成 "0"），然後 count +1。

這樣每座島只會被計算一次，因為 DFS 會把整座島「淹掉」，之後不會再碰到它的任何格子。

可視化

步驟展示

初始 Grid（3×4，含 3 座島）

1
1
0
0
1
0
0
1
0
0
1
1
DFS 起點（遇到 "1" 觸發）
已淹沒（改為 "0"）
待淹沒陸地

遍歷流程

(0,0) → DFS → 淹 (0,0),(1,0) → count=1

(1,3) → DFS → 淹 (1,3),(2,3),(2,2) → count=2

找不到更多 → count=2... 等等！

（此 Grid 結果為 2，非 3）

number_of_islands.py
def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        # 邊界或水域，直接返回
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # 標記為已訪問（淹掉）
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1  # 每次觸發 DFS = 找到一座新島

    return count
⏱ Time: O(m × n)💾 Space: O(m × n)

空間複雜度來自 DFS 遞迴的 call stack 深度，最壞情況是整個 Grid 都是陸地。

為什麼直接改 grid 而不用 visited set？

把 "1" 改成 "0" 就相當於標記已訪問，省下了額外的 set 空間。 不過這會修改原始輸入。如果題目要求不能修改，就改用 visited = set() 另外記錄 (r, c)。

BFS 版本也完全可以

DFS 用遞迴，BFS 用 deque。Grid DFS/BFS 都是 O(m×n)，選哪個都行。 面試中 DFS 寫起來更短，BFS 在超大 Grid 時不會有 stack overflow 風險。

🔗

Part 2 — Clone Graph

#133 · Medium · Graph BFS + HashMap

題目

給一個無向圖的起始節點（每個節點有 val 和 neighbors 列表）， 深度複製整個圖並返回新圖的起始節點。

注意：Graph 可能有環（節點之間互相指向），所以不能無腦遞迴。

關鍵挑戰：有環怎麼辦？

如果節點 1 和節點 2 互相是鄰居（構成環），DFS 會： 進入 1 → 進入 2 → 再次嘗試進入 1 → 無限循環。

解法：用一個 old_to_new HashMap，記錄「原節點 → 新節點」的對應。每次要複製節點前，先查這個 map，如果已經複製過就直接回傳，不再重複處理。

圖結構可視化（4個節點的環形圖）

1
2
3
4

1↔2, 2↔3, 3↔4, 4↔1（每個節點連兩個鄰居）

DFS 解法

clone_graph_dfs.py
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors else []

def cloneGraph(node: Node) -> Node:
    if not node:
        return None

    old_to_new = {}  # 原節點 → 新節點的對應表

    def dfs(node):
        if node in old_to_new:      # 已複製過，直接回傳（避免無限遞迴）
            return old_to_new[node]

        clone = Node(node.val)      # 建立新節點（先不處理 neighbors）
        old_to_new[node] = clone    # 先放進 map，防止後續環形遞迴

        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))  # 遞迴複製每個鄰居

        return clone

    return dfs(node)
⏱ Time: O(V + E)💾 Space: O(V)

V = 節點數，E = 邊數。每個節點和每條邊只處理一次。

關鍵順序：先放進 map，再處理 neighbors

注意程式碼中 old_to_new[node] = clone 必須在遞迴處理 neighbors 之前執行。 如果先處理 neighbors 才放進 map，遇到環就還是會無限遞迴。 這和 Tree 的 Clone 不同，是 Graph 特有的防環邏輯。

BFS 版本

clone_graph_bfs.py
from collections import deque

def cloneGraph(node: Node) -> Node:
    if not node:
        return None

    old_to_new = {node: Node(node.val)}
    queue = deque([node])

    while queue:
        curr = queue.popleft()
        for neighbor in curr.neighbors:
            if neighbor not in old_to_new:
                old_to_new[neighbor] = Node(neighbor.val)
                queue.append(neighbor)
            old_to_new[curr].neighbors.append(old_to_new[neighbor])

    return old_to_new[node]

Graph DFS 通用模板

不管是 Grid 還是 Adjacency List，Graph DFS 的框架都一樣：

graph_dfs_template.py
# Grid 版本
def dfs_grid(grid, r, c, visited):
    if (r, c) in visited or 越界 or 無效格子:
        return
    visited.add((r, c))
    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
        dfs_grid(grid, r + dr, c + dc, visited)

# Adjacency List 版本
def dfs_graph(node, visited):
    if node in visited:
        return
    visited.add(node)
    for neighbor in node.neighbors:
        dfs_graph(neighbor, visited)

三個必做的事

1

檢查是否已訪問

避免無限遞迴，這是 Graph DFS 和 Tree DFS 最大的差異

2

標記為已訪問

在遞迴鄰居之前就要標記，防止環形回訪

3

遍歷所有鄰居

Grid 用四個方向，Adjacency List 用 neighbors 列表

這兩題學到什麼

🏝️Number of Islands：Grid DFS 模板，遇到 "1" 就淹整座島，count++ 計算觸發次數
🔗Clone Graph：防環關鍵在 old_to_new HashMap，先把新節點放進去再處理 neighbors
🔄Graph DFS 三步驟：檢查 visited → 加入 visited → 遍歷鄰居
📍visited 的存法：Grid 可以直接改值（改為 "0"），Adjacency List 用 set 或 dict

上一篇

EP.12 — DP 進階

Coin Change、LIS、Word Break

下一篇

EP.14 — Graph 進階

Course Schedule、拓撲排序、Cycle Detection

LeetCode
Graph
DFS
BFS
Grid
Python
EP.13