field noteENTRY / 009

Personal Field Archive / Received 2026.09.26

图与 BFS｜LeetCode 第一轮复盘

把网格、房间与边统一建模为图，并根据可达性、连通分量和无权最短路径选择 DFS 或 BFS。

Logged: 2026.09.26
Filed under: 算法 / LeetCode / 图 / BFS / DFS / Python
Reading time: 12 min read
Series: Algorithm Field Notes / 06

章节状态：第 6 组已完成并复盘。当前已完成并复盘 LC 733、1971、841、200、994、1091。当前主要训练目标不是记住 DFS / BFS 的固定模板，而是把题目中的 grid、rooms、keys、edges 转换成 Graph 的 node / edge / neighbor / reachable / connected component 模型，并根据问题是在问“可达性”“连通分量”还是“无权图最短路径”，选择 DFS 或 BFS。

一、第 6 组题目清单

顺序	LeetCode	难度	题目	核心训练	当前状态
30	733	简单	Flood Fill	Grid DFS、connected component、in-place visited marking	已复盘
31	1971	简单	Find if Path Exists in Graph	Edge List → Adjacency List、visited、reachability	已复盘
32	841	中等	Keys and Rooms	Directed Graph、可达性、遍历全部 reachable nodes	已复盘
33	200	中等	Number of Islands	Connected Components、多次启动 DFS、in-place marking	已复盘
34	994	中等	Rotting Oranges	Multi-source BFS、层数	已复盘
35	1091	中等	Shortest Path in Binary Matrix	BFS、FIFO、unweighted shortest path、distance	已复盘

二、图的基础心智模型

这一组最重要的变化，是不能只看题目的表面对象。

题目可能写的是：

cell
room
key
edge
island

但算法层面应该继续追问：

什么是 node？
什么关系代表 edge？
从当前 node 可以到哪些 neighbors？
题目最终问的是 reachable、connected component，还是 shortest path？

1. Grid 也可以看成 Graph

例如 Flood Fill：

1 1 0
1 1 0
0 0 1

每一个 cell 都可以看成一个 node。

如果题目规定只能上下左右移动，那么：

当前 cell
→ 上、下、左、右四个 neighbors

就是它的 edges。

如果题目允许八个方向，例如 LC 1091，则一个 cell 最多有 8 个 neighbors。

因此 Grid DFS / BFS 本质上仍然是 Graph Traversal，只是 adjacency relation 不需要显式存成 graph[node]，而是通过坐标计算出来。

2. Adjacency List 回答的是“当前 node 有哪些 neighbors”

LC 1971 给出的是：

edges = [[0, 1], [0, 2], [1, 3]]

这种 Edge List 不方便在 DFS 中反复回答：

node 0 有哪些 neighbors？
node 1 有哪些 neighbors？

因此需要转换成 Adjacency List：

{
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
}

于是：

graph[node]

可以直接得到当前 node 的 neighbors。

3. 有些输入本身已经是 Adjacency List

LC 841：

rooms = [[1], [2], [3], []]

可以直接理解为：

0 → 1
1 → 2
2 → 3
3 → none

其中：

rooms[room]

就是当前 room 能到达的 neighbors。

因此不需要再额外构造 graph。

4. `visited` 的本质是防止重复处理

Graph 中经常存在：

0 ↔ 1

如果：

dfs(0)
→ dfs(1)
→ dfs(0)
→ dfs(1)
→ ...

就会无限循环。

所以必须建立：

这个 node 是否已经处理过？

最直接的方法是：

visited = set()

但在 Grid 中，如果允许修改输入，也可以直接修改 grid，把原数据本身作为 visited 状态。

三、DFS 的统一结构

经过 LC 733、1971、841、200 后，DFS 可以抽象成：

dfs(node)

1. Validate
   当前 node 是否合法 / 是否值得继续处理？

2. Visit
   标记当前 node 已经处理

3. Explore
   对所有 neighbors 继续 dfs(neighbor)

也就是：

Validate → Visit → Explore Neighbors

DFS 最重要的结构变化

在 LC 733 的第一次实现中，曾经写成：

dfs(start)
dfs(start_neighbor_1)
dfs(start_neighbor_2)
...

这只是在外层手动处理一层 neighbors，并不是完整 DFS。

真正的 DFS 是：

def dfs(node):
    ...
    for neighbor in neighbors:
        dfs(neighbor)

dfs(start)

外层只负责提供起点。

递归函数自己负责：

当前 node
→ neighbors
→ neighbors 的 neighbors
→ ...

这才形成 traversal。

四、LC 733. Flood Fill

最初暴露的问题

最初的结构大致是：

def dfs(r, c):
    ...
    image[r][c] = color

dfs(sr, sc)
dfs(sr + 1, sc)
dfs(sr - 1, sc)
dfs(sr, sc + 1)
dfs(sr, sc - 1)

这里的问题是 recursive calls 不在 dfs() 内部，因此只能处理起点附近的一层，无法向整个 connected component 传播。

正确的 DFS 语义

应该先定义：

dfs(r, c)
=
如果 (r,c) 属于起点所在的 connected component，
处理这个 cell，并继续处理它的四个 neighbors。

因此：

def dfs(r, c):
    if not (0 <= r < rows) or not (0 <= c < cols):
        return

    if image[r][c] != original_color:
        return

    image[r][c] = color

    dfs(r + 1, c)
    dfs(r - 1, c)
    dfs(r, c + 1)
    dfs(r, c - 1)

为什么判断 `original_color`，而不是只判断 `color`

最初曾考虑：

if image[r][c] == color:
    return

但 Flood Fill 真正要回答的是：

这个 cell 是否属于起点所在的原始颜色区域？

例如：

1 1 3

如果目标颜色是 2，3 != 2 并不能说明 3 可以被访问。

真正的边界是：

image[r][c] != original_color

Boundary Check 必须发生在访问 grid 之前

不能：

if image[r][c] == ...:
    ...

if r 越界:
    ...

因为在确认 (r,c) 合法之前访问：

image[r][c]

可能直接产生 IndexError。

顺序应该是：

先判断坐标是否合法
→ 再读取 grid
→ 再判断内容是否合法

In-place marking

当：

image[r][c] = color

且：

color != original_color

时，修改颜色本身就承担了：

process current node
+
mark visited

例如：

A(1) ↔ B(1)

访问 A 后：

A(2) ↔ B(1)

B 再尝试回到 A：

image[A] != original_color

于是立即 return。

`original_color == color` 的特殊情况

如果：

original_color = 1
color = 1

那么：

image[r][c] = color

不会改变任何状态。

因此：

A → B → A → B → ...

可能无限递归。

所以需要：

if original_color == color:
    return image

这不是单纯的优化，而是在保证 implicit visited marking 成立。

复杂度

假设 grid 为 m × n。

每个 cell 最多被真正处理一次；每个被处理的 cell 最多检查四个 neighbors。

因此：

时间：O(mn)

虽然代码中每个 node 有 4 个 recursive calls，但常数 4 不会使复杂度变成 O(4^(mn))。

Graph Traversal 更一般的复杂度表达是：

O(V + E)

Grid 中：

V = mn
E = O(mn)

所以仍然是：

O(mn)

本题真正训练的模式

Grid
→ Graph

相同 original_color 且 reachable
→ 一个 connected component

修改 cell
→ implicit visited marking

五、LC 1971. Find if Path Exists in Graph

最初思路

最初已经能够描述：

source = 0

在 edges 中找到与 0 相连的 node
→ 再找那个 node 的下一个 node
→ 一直走
→ 看能不能找到 destination

这个思路本质上已经是 Graph Traversal。

真正的困难是：

如何高效地在 edges 中找到当前 node 的所有 neighbors？

Edge List → Adjacency List

对于：

edges = [[0,1], [0,2], [1,3]]

构造：

graph = {}

for a, b in edges:
    if a not in graph:
        graph[a] = []

    if b not in graph:
        graph[b] = []

    graph[a].append(b)
    graph[b].append(a)

由于 LC 1971 是 undirected graph：

a — b

意味着：

a → b
b → a

所以必须双向加入。

也可以使用：

from collections import defaultdict

graph = defaultdict(list)

然后：

graph[a].append(b)
graph[b].append(a)

为什么需要 `visited`

因为 undirected graph 天然会出现：

0 ↔ 1

没有 visited 时：

dfs(0)
→ dfs(1)
→ dfs(0)
→ ...

所以：

visited = set()

Base Case

曾经提出：

if destination in graph[node]:
    return True

这在本题中可以作为提前判断，但更统一的 Base Case 是：

if node == destination:
    return True

因为：

dfs(node)
=
从 node 出发是否能到 destination？

那么：

node == destination

就是“我已经到达目标”。

它也自然处理：

source == destination

的情况。

DFS return value 如何向上传递

核心结构：

def dfs(node):
    if node == destination:
        return True

    visited.add(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            if dfs(neighbor):
                return True

    return False

其中：

if dfs(neighbor):
    return True

意味着：

如果 neighbor 能到 destination
→ 当前 node 也能到 destination

True 会沿 recursion stack：

destination
→ parent
→ parent's parent
→ ...
→ source

逐层返回。

为什么 `return False` 必须放在 for-loop 之后

不能：

for neighbor in graph[node]:
    if dfs(neighbor):
        return True
    else:
        return False

因为：

第一个 neighbor 找不到
≠
所有 neighbors 都找不到

必须把所有可能 branch 都尝试完，才能确认 False。

本题真正训练的模式

Edge List
→ Adjacency List

Undirected Graph
→ 双向 neighbors

Cycle
→ explicit visited

Reachability
→ DFS / BFS 都可以

六、LC 841. Keys and Rooms

题意转换

Room 不需要按照编号顺序访问。

初始时：

Room 0 默认 unlocked

所以可以直接进入 Room 0。

例如：

rooms = [[1], [2], [3], []]

表示：

Room 0 中有 key 1
Room 1 中有 key 2
Room 2 中有 key 3
Room 3 中没有 key

因此：

0 → 1 → 2 → 3

只是这个 Example 恰好按编号递增，不是题目要求。

Rooms 本身就是 Adjacency List

rooms[room]

表示：

从当前 room 可以到达哪些 rooms

所以：

room = node
key = directed edge

可以直接进行 Graph Traversal。

真正判断的是 Reachability，不是 `graph` 中有没有这个 key

关键不是：

room_number in graph

而是：

room_number in visited

因为题目问：

从 Room 0 出发，是否能够到达所有 rooms？

所以 DFS 的职责只是：

把所有 reachable rooms 加入 visited

最后：

return len(visited) == len(rooms)

DFS 不一定要返回 bool

这里和 LC 1971 有一个重要区别。

LC 1971：

dfs(node) → bool

从 node 能不能到 destination？

因此需要把 True / False 沿 recursion stack 返回。

LC 841：

dfs(room) → None

从 room 出发，把所有 reachable rooms 标记 visited

答案最后统一由：

len(visited) == len(rooms)

决定。

正确结构

def dfs(room):
    visited.add(room)

    for key in rooms[room]:
        if key not in visited:
            dfs(key)

dfs(0)

return len(visited) == len(rooms)

本题真正训练的模式

题目表面：
rooms + keys

算法模型：
directed graph + reachability

DFS 的任务：
遍历，而不是一定返回答案

七、LC 200. Number of Islands

核心思路

这道题和 LC 733 的区别是：

733：
题目已经给一个起点
→ 找这个起点所在的 connected component

200：
没有给起点
→ 自己扫描整个 grid
→ 数一共有多少 connected components

因此 Number of Islands 本质上就是：

Number of Connected Components

“遇到一个 1”不等于“发现一个岛”

准确的说法是：

遇到一个还没有被之前 DFS 访问过的 "1"
=
发现一个新的 island

例如：

1 1 0
1 1 0
0 0 1

第一次遇到左上角 1：

count += 1
dfs(r, c)

DFS 会把左上方四个 connected 1 全部处理掉。

之后扫描到这些位置时，不会再次计数。

直到遇到最后一个仍然存在的 1，才说明发现了第二个 connected component。

使用 in-place marking

可以直接：

grid[r][c] = "0"

把已经访问过的 land “淹没”。

于是 DFS：

def dfs(r, c):
    if not (0 <= r < rows) or not (0 <= c < cols):
        return

    if grid[r][c] != "1":
        return

    grid[r][c] = "0"

    dfs(r + 1, c)
    dfs(r - 1, c)
    dfs(r, c + 1)
    dfs(r, c - 1)

外层：

count = 0

for r in range(rows):
    for c in range(cols):
        if grid[r][c] == "1":
            count += 1
            dfs(r, c)

为什么每次剩余的 `"1"` 都代表新岛

因为前面的每一次 DFS 都已经消除了整个 connected component。

所以如果外层扫描还能看到：

grid[r][c] == "1"

那么它不可能与之前任何 island connected。

否则它早就应该被之前的 DFS 访问并改成 "0"。

这形成了一个重要 invariant：

扫描到剩余的 "1"
→ 它没有被任何之前的 DFS 覆盖
→ 它属于新的 connected component
→ count += 1
→ DFS 消除整个 component

本题真正训练的模式

单次 DFS
→ 找一个 connected component

外层完整扫描 + 多次启动 DFS
→ 数 connected components

八、LC 994. Rotting Oranges

最初思路与正确抽象

最初已经抓到了题目的传播过程：

找到所有初始 2
→ rotten oranges 向上下左右传播
→ 每传播一层，时间增加 1
→ 最后如果还有 1，则 return -1

这里真正的 Graph 模型是：

cell = node
上下左右 = edges
初始 rotten oranges = 多个 sources
fresh orange = 尚未被传播到的 target node

因此这不是多次 BFS，而是 Multi-source BFS：把所有 initial sources 同时放入一个 queue，然后只运行一次 BFS。

为什么不能继续使用 DFS `rot()`

最初尝试：

def rot(r, c):
    if not (0 <= r < m) or not (0 <= c < n):
        return
    if grid[r][c] != 1:
        return

    grid[r][c] = 2

    for dr, dc in directions:
        rot(r + dr, c + dc)

DFS 可以判断哪些 fresh oranges 最终 reachable，但不能自然保留“第几分钟腐烂”的 layer 信息。

例如：

2 1 1 1

minute 0: 2 1 1 1
minute 1: 2 2 1 1
minute 2: 2 2 2 1
minute 3: 2 2 2 2

DFS 会沿一个 branch 一直深入；题目需要的却是“同一分钟能够腐烂的 oranges 一起处理”。因此需要 level-order BFS。

Multi-source initialization

LC 1091 是 single-source：

queue = [source]

LC 994 则是：

queue = [source1, source2, source3, ...]

所有初始 2 都属于 minute = 0，所以必须先完整扫描 grid：

fresh = 0

for r in range(m):
    for c in range(n):
        if grid[r][c] == 2:
            queue.append((r, c))
        elif grid[r][c] == 1:
            fresh += 1

本轮曾把 while queue 缩进到 grid 扫描过程中，这会导致只扫描了一部分 grid 就提前传播，破坏“所有 initial rotten oranges 同时开始”的含义。

正确阶段是：

Phase 1: 扫描完整 grid，收集所有 sources + 统计 fresh
Phase 2: 所有 sources 一起开始 BFS
Phase 3: 检查是否仍有 unreachable fresh oranges

一个 BFS Layer = 一分钟

不能每 popleft() 一个 orange 就：

step += 1

因为同一分钟可能有多个 rotten oranges 同时传播。

正确结构：

while queue and fresh > 0:
    for _ in range(len(queue)):
        r, c = queue.popleft()
        # 处理当前 minute 的传播

    step += 1

进入这一层时的 len(queue) 固定了当前 minute 需要处理的 nodes。当前层新发现并 enqueue 的 oranges 属于下一分钟。

所以：

处理一个 node ≠ 一分钟
处理完整个 BFS layer = 一分钟

本轮最明显的迷惑：`return` vs `continue`

曾写：

if not (0 <= nr < m) or not (0 <= nc < n):
    return

if grid[nr][nc] != 1:
    return

这是把 Grid DFS 的 Base Case 直接迁移到了 BFS neighbor loop。

DFS 中：

def dfs(r, c):
    if 当前 node 不合法:
        return

return 表示结束当前 recursive call。

但 BFS 中：

for dr, dc in directions:

只是在逐个检查 neighbors。某一个 neighbor 无效，只应该：

continue

也就是：

整个 function
│
│ return → 整个问题结束
│
└── while queue
      │ 一轮 = 一个 BFS layer
      │
      └── for neighbor
            │ continue → 跳过当前 neighbor
            │
            └── valid neighbor → mark + enqueue

因此需要建立：

Invalid neighbor
→ skip it
→ not stop the search

`mark` 与 `enqueue` 是两个不同职责

本轮一度写出了：

grid[nr][nc] = 2
fresh -= 1

但遗漏：

queue.append((nr, nc))

这说明需要进一步区分：

grid[nr][nc] = 2
→ 当前 node 已经 rotten / discovered
→ 防止重复处理

fresh -= 1
→ 更新剩余 fresh 数量

queue.append((nr, nc))
→ 这个新 rotten node 下一分钟还要继续向外传播

因此标准 BFS discovery transition 是：

discover
→ mark
→ update bookkeeping
→ enqueue

这和 LC 1091 中：

grid[nr][nc] = 1
queue.append((nr, nc, distance + 1))

本质相同。

`fresh` counter

每发现一个 fresh orange：

fresh += 1

每成功腐烂一个：

fresh -= 1

最终：

fresh == 0
→ 所有 fresh oranges 都被传播到

fresh > 0
→ 存在从所有 initial sources 都 unreachable 的 fresh orange
→ return -1

这样不需要 BFS 后重新扫描整个 grid。

最终实现

from collections import deque

class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        queue = deque()
        fresh = 0
        step = 0

        directions = [
            (-1, 0), (0, -1), (0, 1), (1, 0)
        ]

        for r in range(m):
            for c in range(n):
                if grid[r][c] == 2:
                    queue.append((r, c))
                elif grid[r][c] == 1:
                    fresh += 1

        while queue and fresh > 0:
            for _ in range(len(queue)):
                r, c = queue.popleft()

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if not (0 <= nr < m) or not (0 <= nc < n):
                        continue

                    if grid[nr][nc] != 1:
                        continue

                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))

            step += 1

        if fresh > 0:
            return -1

        return step

复杂度

Grid 为 m × n 时，初始化扫描是 O(mn)；BFS 中每个 cell 最多被有效处理一次，每次只检查 4 个方向，因此：

Time:  O(mn)
Space: O(mn)

本题暴露出的主要问题

这道题暴露的不是“不会 BFS”，而是 BFS 内部不同控制流层级和状态职责还没有完全分开：

1. DFS Base Case 的 return
   ≠ BFS neighbor filtering 的 continue

2. mark node
   ≠ enqueue node

3. Multi-source BFS
   = 所有 initial sources 先同时进入同一个 queue
   ≠ 对每个 source 分别运行 BFS

4. 一个 node
   ≠ 一分钟

   一个完整 BFS layer
   = 一分钟

最需要巩固的两个 invariant：

Invalid neighbor
→ continue

Discovered valid node
→ mark + update state + enqueue

本题真正训练的模式

Grid
→ Graph

多个 initial sources
→ Multi-source BFS

同一 BFS layer
→ 同一分钟

fresh neighbor
→ mark rotten
→ fresh -= 1
→ enqueue

BFS 结束仍有 fresh
→ unreachable
→ return -1

九、LC 1091. Shortest Path in Binary Matrix

为什么从 DFS 转向 BFS

前面的题主要问：

能不能到？
哪些 nodes reachable？
有多少 connected components？

DFS / BFS 都可以完成 reachability。

LC 1091 开始问：

最短路径是多少？

而且每一次从一个 cell 移动到相邻 cell 的 cost 都相同。

因此这是：

Shortest Path in Unweighted Graph

标准选择：

BFS

BFS 为什么保证 shortest path

BFS 使用 FIFO queue：

queue.popleft()

因此会按照距离 source 从小到大处理 nodes：

distance = 1
→ distance = 2 的所有 nodes
→ distance = 3 的所有 nodes
→ ...

所以第一次到达 destination 时：

所有更短 distance 的可能性已经被处理

因此：

第一次到达 destination
=
shortest path

为什么 DFS 第一次到达终点不能保证 shortest

DFS 的策略是：

选择一个 branch
→ 一直深入

例如：

DFS 如果先走左边，第一次找到：

S → A → C → D → T

但右边其实存在：

S → B → T

所以：

DFS 第一次找到 destination
≠
shortest path

8 个方向

LC 1091 允许：

↖ ↑ ↗
← X →
↙ ↓ ↘

因此：

directions = [
    (-1, -1), (-1, 0), (-1, 1),
    (0, -1),            (0, 1),
    (1, -1),  (1, 0),   (1, 1)
]

Queue 保存 distance

一种直观写法：

queue = deque([(0, 0, 1)])

其中：

(row, col, path_length)

起点 path length 为 1，因为题目把起点 cell 也计入 path。

核心结构：

while queue:
    r, c, distance = queue.popleft()

    if r == n - 1 and c == n - 1:
        return distance

    for dr, dc in directions:
        nr = r + dr
        nc = c + dc

        if (
            0 <= nr < n
            and 0 <= nc < n
            and grid[nr][nc] == 0
        ):
            grid[nr][nc] = 1
            queue.append((nr, nc, distance + 1))

为什么 enqueue 时就 mark visited

正确顺序：

grid[nr][nc] = 1
queue.append((nr, nc, distance + 1))

而不是等 node 出队以后才标记。

原因是一个 cell 可能同时被多个当前 layer 的 nodes 发现：

A → C
B → C

如果 A 把 C enqueue 后还没有标记 visited，那么 B 仍然可能再次 enqueue C。

所以 BFS 中一个非常重要的 invariant 是：

进入 queue
=
已经 discovered
=
立即 mark visited

本题真正训练的模式

Reachability
→ DFS / BFS

Unweighted Shortest Path
→ BFS

FIFO
→ layer by layer
→ first arrival is shortest

十、DFS 与 BFS 的统一比较

问题 DFS BFS

Reachability 可以可以 Connected Component 可以可以 Number of Connected Components 可以可以 Unweighted Shortest Path 第一次到达不保证最短适合主要数据结构 recursion stack / explicit stack FIFO queue 搜索方式一个 branch 深入到底按 distance / layer 扩展 visited 通常需要通常需要 Grid 计算 neighbors 计算 neighbors Adjacency List graph[node] graph[node]

这一组不应该形成：

Grid → DFS
Graph → BFS

这种错误分类。

真正应该根据问题问什么来选择：

只是遍历 / reachability / component
→ DFS 或 BFS 都可以

无权图 shortest path
→ 优先 BFS

十一、当前形成的统一 Graph Traversal 思维

1. 先识别 node 和 edge

不要先想代码。

先问：

node 是什么？
edge 是什么？
neighbor 怎么得到？

例如：

733 / 200 / 1091：
node = cell
edge = 允许移动的方向

1971：
node = vertex
edge = edges 中给出的连接

841：
node = room
edge = 当前 room 中拥有的 key

2. 再判断题目到底在问什么

目前遇到的问题可以分成：

733：
找到一个 connected component

1971：
一个 destination 是否 reachable

841：
所有 nodes 是否 reachable

200：
有多少 connected components

994：
多个 sources 同时传播，需要多少 BFS layers / minutes

1091：
到 destination 的 shortest path

问题类型不同，遍历后的“答案形式”也不同。

3. DFS 函数必须先有明确语义

例如：

733:
dfs(r,c)
= 处理从这个 cell 可以扩散到的同色区域

1971:
dfs(node)
= 从 node 出发是否能到 destination

841:
dfs(room)
= 把从 room 出发 reachable 的所有 rooms 标记 visited

200:
dfs(r,c)
= 消除当前 cell 所属的整个 island

如果不能用一句话定义 dfs(...) 的职责，代码通常容易混乱。

4. `visited` 不只是为了性能，也是为了正确性

在有 cycle 的 Graph 中，没有 visited 可能：

A → B → A → B → ...

无限循环。

visited 可以是：

visited = set()

也可以利用输入本身：

733：original_color → new color
200："1" → "0"
994：1 → 2
1091：0 → 1

这就是 in-place marking。

5. Mark visited 的时机很重要

DFS：

进入 node
→ 立即 mark
→ 再 explore neighbors

BFS：

neighbor 被 discovered
→ enqueue 时立即 mark

而不是等 dequeue 后才 mark。

6. Graph Traversal 的复杂度看 nodes / edges，不看代码表面的分支数量

标准：

O(V + E)

Grid 中：

V = rows × cols

每个 cell 的 neighbor 数量是常数：

4 directions
或
8 directions

因此通常：

O(rows × cols)

十二、当前暴露出的共性问题

1. 最初容易把 recursive calls 放在 DFS 外层

LC 733 最初只从外层手动调用起点和四个 neighbors。

这说明当时对 DFS 的理解更接近：

我来决定下一步访问谁

而真正应该形成：

外层只给 start
DFS 自己递归传播

现在在 LC 841、200 中已经能够自然把 recursive calls 放在 traversal 函数内部，这一点已经明显改善。

2. 需要先定义“什么 node 可以访问”

LC 733 最初使用：

image[r][c] == color

判断是否停止，但真正的 traversal boundary 是：

image[r][c] != original_color

以后写 DFS / BFS 时，应先明确：

什么状态才属于当前搜索空间？

而不是先写 recursive call。

3. Boundary Check 的顺序需要保持严谨

必须：

先验证 index
→ 再访问 grid[index]

不能在越界检查之前读取 cell。

4. 需要区分“输入结构”和“遍历需要的结构”

LC 1971 的 edges 是 Edge List。

DFS 真正想要的是：

node → neighbors

因此需要构造 Adjacency List。

而 LC 841 的 rooms 本身已经是 Adjacency List，不需要重复转换。

以后应先问：

当前输入能否 O(1) / O(degree) 得到一个 node 的 neighbors？

如果不能，可能需要 preprocessing。

5. 需要继续巩固 DFS return value 与 traversal side effect 的区别

LC 1971：

dfs(node) → bool

需要递归结果向上传播。

LC 841 / 200：

dfs(...) → None

DFS 主要通过修改：

visited
或
grid

记录遍历结果。

因此：

DFS 不一定必须 return 某个答案。

6. “孤立”与“新的 connected component”需要区分

LC 200 中曾把剩余的 "1" 描述为“孤立的 1”。

更准确的是：

它可能与很多其他 1 connected，
只是它所在的整个 component 尚未被访问。

算法语言应该逐渐从：

孤立的点

转向：

unvisited node belonging to a new connected component

7. BFS shortest path 的原因需要绑定到 FIFO + layer

不能只记：

shortest path → BFS

真正原因是：

FIFO
→ nodes 按 distance 从小到大处理
→ 第一次到达 destination 时，不可能还有更短 layer 未处理

这才是能够迁移到其他题目的 reasoning。

十三、图与 BFS 统一检查清单

题目中的 node 是什么？
什么关系构成 edge？
当前 node 的 neighbors 如何得到？
输入是 Edge List、Adjacency List，还是隐式 Grid Graph？
如果是 Edge List，是否需要先构造 Adjacency List？
Graph 是 directed 还是 undirected？构图时是否需要双向加入？
题目问的是 reachability、connected component、component count，还是 shortest path？
dfs(node) / BFS state 的准确语义是什么？
什么情况下当前 node / cell 应该停止处理？
Boundary Check 是否发生在读取 grid 之前？
是否存在 cycle？如何避免重复访问？
使用 explicit visited，还是可以通过修改输入做 in-place marking？
如果修改输入作为 visited，修改后的状态是否一定与未访问状态不同？
DFS 是否把 recursive calls 放在 traversal 函数内部？
如果 DFS 返回 bool，递归结果是否正确向上传递？
return False 是否错误地放在某个 neighbor 尝试之后，而不是所有 neighbors 失败之后？
如果只是记录 reachable nodes，DFS 是否其实不需要 return value？
BFS 是否使用 FIFO queue？
BFS 是否在 enqueue / discovered 时立即 mark visited？
如果题目问 shortest path，每条 edge 的 cost 是否相同？
为什么第一次到达 destination 能代表 shortest，而不是只记结论？
Grid 是 4-direction 还是 8-direction？directions 是否完整、无重复、无遗漏？
复杂度是否按 O(V + E) 分析，而不是看到多个 recursive calls 就指数化？
Grid 中为什么 4/8 个 neighbors 仍然通常得到 O(rows × cols)？
Multi-source BFS 是否先收集所有 initial sources，再统一开始 traversal？
当前 BFS 的一个 layer 代表 distance、minute，还是其他状态？
Neighbor 无效时为什么应该 continue，而不是整个 function return？
新 node 被 discovered 后，是否完成了 mark + state update + enqueue？
为什么 mark 与 enqueue 是两个不同职责？
step += 1 是按 node 增加，还是按完整 BFS layer 增加？

十四、这一组最重要的模式归纳

目前可以把这几道题压缩成四个核心模式。

Pattern A：从一个起点遍历一个 Connected Component

代表：

733 Flood Fill

结构：

给定 start
→ DFS/BFS
→ 遍历所有 reachable + valid neighbors

Pattern B：Reachability

代表：

1971 Find if Path Exists in Graph
841 Keys and Rooms

结构：

start
→ Graph Traversal
→ destination / all nodes 是否 reachable

区别在于：

1971：找一个特定 destination
841：要求所有 rooms reachable

Pattern C：Count Connected Components

代表：

200 Number of Islands

结构：

扫描所有 nodes

遇到 unvisited valid node：
    count += 1
    traversal 整个 component

Pattern D：Multi-source BFS / Simultaneous Propagation

代表：

994 Rotting Oranges

结构：

扫描完整输入
→ 收集所有 initial sources
→ 全部进入同一个 queue
→ level-order BFS
→ 每完整处理一层，time += 1
→ 最后检查是否还有 unreachable target

关键：

多个 sources
≠ 多次 BFS

多个 sources
= 一次 BFS 的多个初始起点

Pattern E：Unweighted Shortest Path

代表：

1091 Shortest Path in Binary Matrix

结构：

start
→ BFS
→ FIFO layer expansion
→ 第一次到 destination
→ shortest distance

十五、延迟重做安排

建议在 3～7 天后从空白重做：

733、1971、841、200、994、1091

完成标准不只是通过测试，还应能够说明：

题目如何转换成 Graph；
node、edge、neighbor 分别是什么；
输入是否已经是 Adjacency List；
为什么需要或不需要 visited；
为什么某些 Grid 可以直接修改输入作为 visited；
DFS 函数的准确语义是什么；
为什么 recursive calls 必须位于 DFS 内部；
1971 中 bool 如何沿 recursion stack 返回；
841 为什么 DFS 不需要返回 bool；
200 为什么每发现一个剩余 "1" 就代表新的 connected component；
994 为什么是 Multi-source BFS，以及为什么所有初始 2 必须同时进入初始 queue；
994 中为什么一个完整 BFS layer 才代表一分钟；
994 中为什么 invalid neighbor 应该 continue 而不是 return；
994 中为什么新腐烂的 orange 必须 mark、更新 fresh 并 enqueue；
1091 为什么使用 BFS，而不是因为“BFS 是最短路径模板”，而是因为 FIFO 保证按 distance layer 搜索；
为什么 BFS 要在 enqueue 时 mark visited；
能够独立写出 4-direction / 8-direction neighbor traversal；
能够用 O(V + E) 分析 Graph Traversal，并将 Grid 化简为 O(rows × cols)。

如果能够在不参考答案的情况下重做这些题，并能从：

Connected Component
Reachability
Component Counting
Multi-source Propagation
Unweighted Shortest Path

五种问题类型出发独立选择 traversal strategy，可以将第 6 组“图与 BFS / DFS 基础”标记为稳定掌握。

一、第 6 组题目清单

二、图的基础心智模型

1. Grid 也可以看成 Graph

2. Adjacency List 回答的是“当前 node 有哪些 neighbors”

3. 有些输入本身已经是 Adjacency List

4. visited 的本质是防止重复处理

三、DFS 的统一结构

DFS 最重要的结构变化

四、LC 733. Flood Fill

最初暴露的问题

正确的 DFS 语义

为什么判断 original_color，而不是只判断 color

Boundary Check 必须发生在访问 grid 之前

In-place marking

original_color == color 的特殊情况

复杂度

本题真正训练的模式

五、LC 1971. Find if Path Exists in Graph

最初思路

Edge List → Adjacency List

为什么需要 visited

Base Case

DFS return value 如何向上传递

为什么 return False 必须放在 for-loop 之后

本题真正训练的模式

六、LC 841. Keys and Rooms

题意转换

Rooms 本身就是 Adjacency List

真正判断的是 Reachability，不是 graph 中有没有这个 key

DFS 不一定要返回 bool

正确结构

本题真正训练的模式

七、LC 200. Number of Islands

核心思路

“遇到一个 1”不等于“发现一个岛”

使用 in-place marking

为什么每次剩余的 "1" 都代表新岛

本题真正训练的模式

八、LC 994. Rotting Oranges

最初思路与正确抽象

为什么不能继续使用 DFS rot()

Multi-source initialization

一个 BFS Layer = 一分钟

本轮最明显的迷惑：return vs continue

mark 与 enqueue 是两个不同职责

fresh counter

最终实现

复杂度

本题暴露出的主要问题

本题真正训练的模式

九、LC 1091. Shortest Path in Binary Matrix

为什么从 DFS 转向 BFS

BFS 为什么保证 shortest path

为什么 DFS 第一次到达终点不能保证 shortest

8 个方向

Queue 保存 distance

为什么 enqueue 时就 mark visited

本题真正训练的模式

十、DFS 与 BFS 的统一比较

十一、当前形成的统一 Graph Traversal 思维

1. 先识别 node 和 edge

2. 再判断题目到底在问什么

3. DFS 函数必须先有明确语义

4. visited 不只是为了性能，也是为了正确性

5. Mark visited 的时机很重要

6. Graph Traversal 的复杂度看 nodes / edges，不看代码表面的分支数量

十二、当前暴露出的共性问题

1. 最初容易把 recursive calls 放在 DFS 外层

2. 需要先定义“什么 node 可以访问”

3. Boundary Check 的顺序需要保持严谨

4. 需要区分“输入结构”和“遍历需要的结构”

5. 需要继续巩固 DFS return value 与 traversal side effect 的区别

6. “孤立”与“新的 connected component”需要区分

7. BFS shortest path 的原因需要绑定到 FIFO + layer

十三、图与 BFS 统一检查清单

十四、这一组最重要的模式归纳

Pattern A：从一个起点遍历一个 Connected Component

Pattern B：Reachability

Pattern C：Count Connected Components

Pattern D：Multi-source BFS / Simultaneous Propagation

4. `visited` 的本质是防止重复处理

为什么判断 `original_color`，而不是只判断 `color`

`original_color == color` 的特殊情况

为什么需要 `visited`

为什么 `return False` 必须放在 for-loop 之后

真正判断的是 Reachability，不是 `graph` 中有没有这个 key

为什么每次剩余的 `"1"` 都代表新岛

为什么不能继续使用 DFS `rot()`

本轮最明显的迷惑：`return` vs `continue`

`mark` 与 `enqueue` 是两个不同职责

`fresh` counter

4. `visited` 不只是为了性能，也是为了正确性