图搜索 · Graph Search

一句话骨架：① 网格题 → 「四方向 DFS / BFS + visited」；② 依赖题 → 「Kahn 拓扑排序」；③ 连通分量题 → 「并查集」。识别出题型，模板套上去就能 80% 解决。

三个最常用骨架

python

# 1. 网格 BFS（多源也是同一个写法）
from collections import deque
q = deque([起点])
while q:
    x, y = q.popleft()
    for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        nx, ny = x+dx, y+dy
        if 合法 and 未访问:
            visited[nx][ny] = True
            q.append((nx, ny))

# 2. Kahn 拓扑排序
indeg = [0]*n
g = [[] for _ in range(n)]
for u, v in edges: g[u].append(v); indeg[v] += 1
q = deque([i for i in range(n) if indeg[i]==0])
order = []
while q:
    u = q.popleft(); order.append(u)
    for v in g[u]:
        indeg[v] -= 1
        if indeg[v] == 0: q.append(v)
return len(order) == n   # 是否无环

# 3. 网格 DFS「沉岛」
def dfs(i, j):
    if i<0 or i>=m or j<0 or j>=n or grid[i][j]!='1': return
    grid[i][j] = '0'        # 沉岛 = 标记 visited
    for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
        dfs(i+di, j+dj)

关卡 1 · 课程表

学习目标

把「能否完成所有课程」翻译成「图是否无环」，掌握 Kahn BFS 模板。

#207课程表中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程 ai 则必须先学习课程 bi。

请你判断是否可能完成所有课程的学习？如果可以，返回 true；否则，返回 false。

示例 1

输入numCourses = 2, prerequisites = [[1,0]]

输出true

💡 先修 0 再学 1，无环

示例 2

输入numCourses = 2, prerequisites = [[1,0],[0,1]]

输出false

💡 0 和 1 互为先修——成环，不可能完成

约束

1 ≤ numCourses ≤ 2000
0 ≤ prerequisites.length ≤ 5000
prerequisites[i].length == 2
0 ≤ ai, bi < numCourses
ai != bi
所有 [ai, bi] 互不相同

💡 思路：把题目翻译成图：边 b → a 代表「a 依赖 b」。问题等价于「这张有向图是否无环」。Kahn BFS 拓扑排序：把所有入度为 0 的点入队（无依赖的课）；每次取一个点 u，对它指向的 v 入度 -1，如果 v 入度变 0 就入队。最终若所有点都被处理过则无环。

✅ 完整解法

时间 O(V+E) · 空间 O(V+E)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1from collections import deque 2  3def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool: 4    g = [[] for _ in range(numCourses)] 5    indeg = [0] * numCourses 6    for a, b in prerequisites: 7        # b -> a：要学 a 必须先学 b 8        g[b].append(a) 9        indeg[a] += 110 11    q = deque(i for i in range(numCourses) if indeg[i] == 0)12    finished = 013    while q:14        u = q.popleft()15        finished += 116        for v in g[u]:17            indeg[v] -= 118            if indeg[v] == 0:19                q.append(v)20    return finished == numCourses

🐞 单步可视化

示例：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

代码L4

 1from collections import deque 2  3def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool: 4    g = [[] for _ in range(numCourses)] 5    indeg = [0] * numCourses 6    for a, b in prerequisites: 7        # b -> a：要学 a 必须先学 b 8        g[b].append(a) 9        indeg[a] += 110 11    q = deque(i for i in range(numCourses) if indeg[i] == 0)12    finished = 013    while q:14        u = q.popleft()15        finished += 116        for v in g[u]:17            indeg[v] -= 118            if indeg[v] == 0:19                q.append(v)20    return finished == numCourses

数据流

numCourses4finished0queue[]

课程编号

课0

课1

课2

课3

indeg（入度数组）

邻接表 g（课程 → 下游课程列表）

0→[]

1→[]

2→[]

3→[]

1 / 33初始化邻接表 g = [[],[],[],[]]，入度数组 indeg = [0,0,0,0]

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

本题最自然的算法骨架是？

prerequisites = [[a, b]] 应该建哪个方向的边？

 1from collections import deque 2  3def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool: 4    g = [[] for _ in range(numCourses)] 5    indeg = [0] * numCourses 6    for a, b in prerequisites: 7        # b -> a：要学 a 必须先学 b 8        g[b].append(a) 9        indeg[a] += 110 11    q = deque(i for i in range(numCourses) if indeg[i] == 0)12    finished = 013    while q:14        u = q.popleft()15        finished += 116        for v in g[u]:17            indeg[v] -= 118            if indeg[v] == 0:19                q.append(v)20    return finished == numCourses

入度数组 indeg[a] += 1 表达的语义是？

 1from collections import deque 2  3def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool: 4    g = [[] for _ in range(numCourses)] 5    indeg = [0] * numCourses 6    for a, b in prerequisites: 7        # b -> a：要学 a 必须先学 b 8        g[b].append(a) 9        indeg[a] += 110 11    q = deque(i for i in range(numCourses) if indeg[i] == 0)12    finished = 013    while q:14        u = q.popleft()15        finished += 116        for v in g[u]:17            indeg[v] -= 118            if indeg[v] == 0:19                q.append(v)20    return finished == numCourses

初始队列为什么是「所有入度为 0 的点」？

 1from collections import deque 2  3def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool: 4    g = [[] for _ in range(numCourses)] 5    indeg = [0] * numCourses 6    for a, b in prerequisites: 7        # b -> a：要学 a 必须先学 b 8        g[b].append(a) 9        indeg[a] += 110 11    q = deque(i for i in range(numCourses) if indeg[i] == 0)12    finished = 013    while q:14        u = q.popleft()15        finished += 116        for v in g[u]:17            indeg[v] -= 118            if indeg[v] == 0:19                q.append(v)20    return finished == numCourses

当我们处理完节点 u，对它的下游 v 做什么？

 1from collections import deque 2  3def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool: 4    g = [[] for _ in range(numCourses)] 5    indeg = [0] * numCourses 6    for a, b in prerequisites: 7        # b -> a：要学 a 必须先学 b 8        g[b].append(a) 9        indeg[a] += 110 11    q = deque(i for i in range(numCourses) if indeg[i] == 0)12    finished = 013    while q:14        u = q.popleft()15        finished += 116        for v in g[u]:17            indeg[v] -= 118            if indeg[v] == 0:19                q.append(v)20    return finished == numCourses

为什么用 deque 而不是 list？

 1from collections import deque 2  3def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool: 4    g = [[] for _ in range(numCourses)] 5    indeg = [0] * numCourses 6    for a, b in prerequisites: 7        # b -> a：要学 a 必须先学 b 8        g[b].append(a) 9        indeg[a] += 110 11    q = deque(i for i in range(numCourses) if indeg[i] == 0)12    finished = 013    while q:14        u = q.popleft()15        finished += 116        for v in g[u]:17            indeg[v] -= 118            if indeg[v] == 0:19                q.append(v)20    return finished == numCourses

若 finished < numCourses，意味着？

 1from collections import deque 2  3def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool: 4    g = [[] for _ in range(numCourses)] 5    indeg = [0] * numCourses 6    for a, b in prerequisites: 7        # b -> a：要学 a 必须先学 b 8        g[b].append(a) 9        indeg[a] += 110 11    q = deque(i for i in range(numCourses) if indeg[i] == 0)12    finished = 013    while q:14        u = q.popleft()15        finished += 116        for v in g[u]:17            indeg[v] -= 118            if indeg[v] == 0:19                q.append(v)20    return finished == numCourses

DFS 三色标记法判环的「三色」分别是？

Kahn BFS 与 DFS 三色法在功能上的区别？

本题时间复杂度是？

空间复杂度是？

若题目改为「LC210 返回拓扑序本身」，需要怎么改？

关卡 2 · 岛屿数量

学习目标

学会「扫到 1 就 cnt++ 然后 DFS 沉岛」的连通分量计数模板；体会 grid 自身充当 visited 的省空间技巧。

#200岛屿数量中等

♥♥♥♥♥+0 XP🔥 0

0 / 11

📝 题目

给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1

输入

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

输出1

示例 2

输入

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

输出3

约束

m == grid.length, n == grid[i].length
1 ≤ m, n ≤ 300
grid[i][j] 为 "0" 或 "1"

💡 思路：扫一遍每个格子。遇到 "1" 就 cnt++ 并启动一次 DFS 把整片相连的 "1" 全部「沉岛」（改成 "0"），保证它们不再被外层循环计数。BFS 同样可行——把递归换成 deque。也可以用并查集（更适合「动态加入岛」的变体）。

✅ 完整解法

时间 O(m·n) — 每个格子最多被访问一次 · 空间 O(m·n) 最坏递归栈深度（整张图都是岛）

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def numIslands(grid: list[list[str]]) -> int: 2    if not grid or not grid[0]: 3        return 0 4    m, n = len(grid), len(grid[0]) 5  6    def dfs(i: int, j: int) -> None: 7        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1': 8            return 9        grid[i][j] = '0'                 # 「沉岛」——把当前陆地变成水，避免重复访问10        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):11            dfs(i + di, j + dj)12 13    cnt = 014    for i in range(m):15        for j in range(n):16            if grid[i][j] == '1':17                cnt += 118                dfs(i, j)19    return cnt

🐞 单步可视化

示例：4×5 grid（应返回 3 个岛）

代码L13

 1def numIslands(grid: list[list[str]]) -> int: 2    if not grid or not grid[0]: 3        return 0 4    m, n = len(grid), len(grid[0]) 5  6    def dfs(i: int, j: int) -> None: 7        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1': 8            return 9        grid[i][j] = '0'                 # 「沉岛」——把当前陆地变成水，避免重复访问10        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):11            dfs(i + di, j + dj)12 13    cnt = 014    for i in range(m):15        for j in range(n):16            if grid[i][j] == '1':17                cnt += 118                dfs(i, j)19    return cnt

数据流

cnt0

🟩

🟦

🟩

🟦

🟩

🟦

🟩

1 / 87初始化 cnt = 0；从 (0,0) 开始扫描

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

本题「数岛屿」的关键技巧是？

grid[i][j] = "0" 这一步在做什么？

 1def numIslands(grid: list[list[str]]) -> int: 2    if not grid or not grid[0]: 3        return 0 4    m, n = len(grid), len(grid[0]) 5  6    def dfs(i: int, j: int) -> None: 7        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1': 8            return 9        grid[i][j] = '0'                 # 「沉岛」——把当前陆地变成水，避免重复访问10        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):11            dfs(i + di, j + dj)12 13    cnt = 014    for i in range(m):15        for j in range(n):16            if grid[i][j] == '1':17                cnt += 118                dfs(i, j)19    return cnt

为什么我们不需要在 dfs 出口处「还原」grid？

for di, dj in ((1,0),(-1,0),(0,1),(0,-1)) 的作用？

 1def numIslands(grid: list[list[str]]) -> int: 2    if not grid or not grid[0]: 3        return 0 4    m, n = len(grid), len(grid[0]) 5  6    def dfs(i: int, j: int) -> None: 7        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1': 8            return 9        grid[i][j] = '0'                 # 「沉岛」——把当前陆地变成水，避免重复访问10        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):11            dfs(i + di, j + dj)12 13    cnt = 014    for i in range(m):15        for j in range(n):16            if grid[i][j] == '1':17                cnt += 118                dfs(i, j)19    return cnt

dfs 入口的越界 + 类型检查 i<0 or i>=m or j<0 or j>=n or grid[i][j] != "1" 这一行可以拆成两行写吗？

 1def numIslands(grid: list[list[str]]) -> int: 2    if not grid or not grid[0]: 3        return 0 4    m, n = len(grid), len(grid[0]) 5  6    def dfs(i: int, j: int) -> None: 7        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1': 8            return 9        grid[i][j] = '0'                 # 「沉岛」——把当前陆地变成水，避免重复访问10        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):11            dfs(i + di, j + dj)12 13    cnt = 014    for i in range(m):15        for j in range(n):16            if grid[i][j] == '1':17                cnt += 118                dfs(i, j)19    return cnt

BFS 版与 DFS 版的核心差别？

并查集（Union-Find）解法的思路是？

本题为何不需要单独的 visited 数组（即使不允许污染输入）？

时间复杂度?

空间复杂度?

若题目改为「数岛屿面积之和的最大值」（LC695），最小改动？

关卡 3 · 腐烂的橘子

学习目标

掌握多源 BFS——所有腐烂橘子作为「第 0 层」一次性入队，按层扩张计时间。

#994腐烂的橘子中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

- 0 代表空单元格；
- 1 代表新鲜橘子；
- 2 代表腐烂的橘子。

每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

示例 1

输入grid = [[2,1,1],[1,1,0],[0,1,1]]

输出4

示例 2

输入grid = [[2,1,1],[0,1,1],[1,0,1]]

输出-1

💡 左下角的 1 永远无法被腐烂——它没有任何相邻的腐烂橘子

示例 3

输入grid = [[0,2]]

输出0

💡 一开始就没有新鲜橘子

约束

m == grid.length, n == grid[i].length
1 ≤ m, n ≤ 10
grid[i][j] 仅为 0、1、2

💡 思路：「最少分钟数」= BFS 的层数。把所有初始腐烂橘子一次性入队作为「第 0 层」，每层让相邻新鲜橘子腐烂并入队，扩展一层 minutes++。最终若 fresh > 0 表示有橘子永远到不了 → -1。这是**多源 BFS** 的经典应用。

✅ 完整解法

时间 O(m·n) — 每个格子最多入队/出队一次 · 空间 O(m·n) — 队列最坏装下整张图

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1from collections import deque 2  3def orangesRotting(grid: list[list[int]]) -> int: 4    m, n = len(grid), len(grid[0]) 5    q = deque() 6    fresh = 0 7    # 1. 收集所有「初始就腐烂」的橘子作为多源 BFS 起点；同时统计新鲜橘子数 8    for i in range(m): 9        for j in range(n):10            if grid[i][j] == 2:11                q.append((i, j))12            elif grid[i][j] == 1:13                fresh += 114 15    minutes = 016    dirs = ((1,0),(-1,0),(0,1),(0,-1))17    # 2. 一层一层扩展，每扩张一层 minutes += 118    while q and fresh > 0:19        for _ in range(len(q)):              # 把当前层一次性吐完20            i, j = q.popleft()21            for di, dj in dirs:22                ni, nj = i + di, j + dj23                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:24                    grid[ni][nj] = 225                    fresh -= 126                    q.append((ni, nj))27        minutes += 128 29    return minutes if fresh == 0 else -1

🐞 单步可视化

示例：grid = [[2,1,1],[1,1,0],[0,1,1]]（应返回 4）

代码L4

 1from collections import deque 2  3def orangesRotting(grid: list[list[int]]) -> int: 4    m, n = len(grid), len(grid[0]) 5    q = deque() 6    fresh = 0 7    # 1. 收集所有「初始就腐烂」的橘子作为多源 BFS 起点；同时统计新鲜橘子数 8    for i in range(m): 9        for j in range(n):10            if grid[i][j] == 2:11                q.append((i, j))12            elif grid[i][j] == 1:13                fresh += 114 15    minutes = 016    dirs = ((1,0),(-1,0),(0,1),(0,-1))17    # 2. 一层一层扩展，每扩张一层 minutes += 118    while q and fresh > 0:19        for _ in range(len(q)):              # 把当前层一次性吐完20            i, j = q.popleft()21            for di, dj in dirs:22                ni, nj = i + di, j + dj23                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:24                    grid[ni][nj] = 225                    fresh -= 126                    q.append((ni, nj))27        minutes += 128 29    return minutes if fresh == 0 else -1

数据流

minutes0fresh0queue.size0

💀

🍊

队列

空

1 / 52初始化 m=3, n=3, q = deque(), fresh = 0

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

本题最自然的算法是？

为什么必须先把所有腐烂橘子一次性入队？

 1from collections import deque 2  3def orangesRotting(grid: list[list[int]]) -> int: 4    m, n = len(grid), len(grid[0]) 5    q = deque() 6    fresh = 0 7    # 1. 收集所有「初始就腐烂」的橘子作为多源 BFS 起点；同时统计新鲜橘子数 8    for i in range(m): 9        for j in range(n):10            if grid[i][j] == 2:11                q.append((i, j))12            elif grid[i][j] == 1:13                fresh += 114 15    minutes = 016    dirs = ((1,0),(-1,0),(0,1),(0,-1))17    # 2. 一层一层扩展，每扩张一层 minutes += 118    while q and fresh > 0:19        for _ in range(len(q)):              # 把当前层一次性吐完20            i, j = q.popleft()21            for di, dj in dirs:22                ni, nj = i + di, j + dj23                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:24                    grid[ni][nj] = 225                    fresh -= 126                    q.append((ni, nj))27        minutes += 128 29    return minutes if fresh == 0 else -1

「按层扩张」的写法核心是？

 1from collections import deque 2  3def orangesRotting(grid: list[list[int]]) -> int: 4    m, n = len(grid), len(grid[0]) 5    q = deque() 6    fresh = 0 7    # 1. 收集所有「初始就腐烂」的橘子作为多源 BFS 起点；同时统计新鲜橘子数 8    for i in range(m): 9        for j in range(n):10            if grid[i][j] == 2:11                q.append((i, j))12            elif grid[i][j] == 1:13                fresh += 114 15    minutes = 016    dirs = ((1,0),(-1,0),(0,1),(0,-1))17    # 2. 一层一层扩展，每扩张一层 minutes += 118    while q and fresh > 0:19        for _ in range(len(q)):              # 把当前层一次性吐完20            i, j = q.popleft()21            for di, dj in dirs:22                ni, nj = i + di, j + dj23                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:24                    grid[ni][nj] = 225                    fresh -= 126                    q.append((ni, nj))27        minutes += 128 29    return minutes if fresh == 0 else -1

fresh 计数器有两个作用，是哪两个？

 1from collections import deque 2  3def orangesRotting(grid: list[list[int]]) -> int: 4    m, n = len(grid), len(grid[0]) 5    q = deque() 6    fresh = 0 7    # 1. 收集所有「初始就腐烂」的橘子作为多源 BFS 起点；同时统计新鲜橘子数 8    for i in range(m): 9        for j in range(n):10            if grid[i][j] == 2:11                q.append((i, j))12            elif grid[i][j] == 1:13                fresh += 114 15    minutes = 016    dirs = ((1,0),(-1,0),(0,1),(0,-1))17    # 2. 一层一层扩展，每扩张一层 minutes += 118    while q and fresh > 0:19        for _ in range(len(q)):              # 把当前层一次性吐完20            i, j = q.popleft()21            for di, dj in dirs:22                ni, nj = i + di, j + dj23                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:24                    grid[ni][nj] = 225                    fresh -= 126                    q.append((ni, nj))27        minutes += 128 29    return minutes if fresh == 0 else -1

while q and fresh > 0 中 fresh > 0 这个条件的意义？

 1from collections import deque 2  3def orangesRotting(grid: list[list[int]]) -> int: 4    m, n = len(grid), len(grid[0]) 5    q = deque() 6    fresh = 0 7    # 1. 收集所有「初始就腐烂」的橘子作为多源 BFS 起点；同时统计新鲜橘子数 8    for i in range(m): 9        for j in range(n):10            if grid[i][j] == 2:11                q.append((i, j))12            elif grid[i][j] == 1:13                fresh += 114 15    minutes = 016    dirs = ((1,0),(-1,0),(0,1),(0,-1))17    # 2. 一层一层扩展，每扩张一层 minutes += 118    while q and fresh > 0:19        for _ in range(len(q)):              # 把当前层一次性吐完20            i, j = q.popleft()21            for di, dj in dirs:22                ni, nj = i + di, j + dj23                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:24                    grid[ni][nj] = 225                    fresh -= 126                    q.append((ni, nj))27        minutes += 128 29    return minutes if fresh == 0 else -1

若初始网格中根本没有新鲜橘子（全 0 和 2），应该返回？

 1from collections import deque 2  3def orangesRotting(grid: list[list[int]]) -> int: 4    m, n = len(grid), len(grid[0]) 5    q = deque() 6    fresh = 0 7    # 1. 收集所有「初始就腐烂」的橘子作为多源 BFS 起点；同时统计新鲜橘子数 8    for i in range(m): 9        for j in range(n):10            if grid[i][j] == 2:11                q.append((i, j))12            elif grid[i][j] == 1:13                fresh += 114 15    minutes = 016    dirs = ((1,0),(-1,0),(0,1),(0,-1))17    # 2. 一层一层扩展，每扩张一层 minutes += 118    while q and fresh > 0:19        for _ in range(len(q)):              # 把当前层一次性吐完20            i, j = q.popleft()21            for di, dj in dirs:22                ni, nj = i + di, j + dj23                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:24                    grid[ni][nj] = 225                    fresh -= 126                    q.append((ni, nj))27        minutes += 128 29    return minutes if fresh == 0 else -1

grid[ni][nj] = 2 这一步做什么？

 1from collections import deque 2  3def orangesRotting(grid: list[list[int]]) -> int: 4    m, n = len(grid), len(grid[0]) 5    q = deque() 6    fresh = 0 7    # 1. 收集所有「初始就腐烂」的橘子作为多源 BFS 起点；同时统计新鲜橘子数 8    for i in range(m): 9        for j in range(n):10            if grid[i][j] == 2:11                q.append((i, j))12            elif grid[i][j] == 1:13                fresh += 114 15    minutes = 016    dirs = ((1,0),(-1,0),(0,1),(0,-1))17    # 2. 一层一层扩展，每扩张一层 minutes += 118    while q and fresh > 0:19        for _ in range(len(q)):              # 把当前层一次性吐完20            i, j = q.popleft()21            for di, dj in dirs:22                ni, nj = i + di, j + dj23                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:24                    grid[ni][nj] = 225                    fresh -= 126                    q.append((ni, nj))27        minutes += 128 29    return minutes if fresh == 0 else -1

为什么用 deque 而不用 list 做队列？

若 BFS 结束后还剩 fresh > 0，意味着？

本题时间复杂度?

空间复杂度?

如果题目变体「时间不是 1 分钟而是任意权重」（→ Dijkstra 范畴），骨架要变吗？

同 pattern 索引（hot100 同类题）

题号	题名	难度	关键变形
210	课程表 II	中等	在 Kahn BFS 中按弹出顺序记录 order 即拓扑序
695	岛屿的最大面积	中等	dfs 返回 1 + 四邻 dfs 之和；外层取 max
130	被围绕的区域	中等	从边界出发反向 DFS 标记「不被围绕」的 O，剩下的 O 就翻 X
417	太平洋大西洋水流	中等	从两个海洋逆向 DFS / BFS，求两片可达区域的交集

面试常踩

from collections import deque：BFS 必备。list.pop(0) 是 O(n)，会让算法退化。
dirs 常量：((1,0),(-1,0),(0,1),(0,-1)) 写在循环外、循环里 for di, dj in dirs 可读性最好；想扩 8 方向只要加四角。
越界检查在前：0 <= ni < m and 0 <= nj < n and grid[ni][nj] == ...——靠 Python 的短路求值避免 IndexError。
多源 BFS vs 普通 BFS：从 m 个源同时扩张，等价于一个虚拟超级源——一次性入队全部源点是关键。
拓扑判环 = 看是否所有点都能被弹出：剩下的就是环上节点。

图搜索 · Graph Search ​

三个最常用骨架 ​

关卡 1 · 课程表 ​

📝 题目

✅ 完整解法

🧠 理解检验

关卡 2 · 岛屿数量 ​

📝 题目

✅ 完整解法

🧠 理解检验

关卡 3 · 腐烂的橘子 ​

📝 题目

✅ 完整解法

🧠 理解检验

同 pattern 索引（hot100 同类题） ​

面试常踩 ​

图搜索 · Graph Search

三个最常用骨架

关卡 1 · 课程表

关卡 2 · 岛屿数量

关卡 3 · 腐烂的橘子

同 pattern 索引（hot100 同类题）

面试常踩