07 · 图论
来源： labuladong BFS/DFS 框架 + 代码随想录图论专题
核心价值： 网格是图的特例，图的遍历是 DFS/BFS 的终极应用
题量： 4 题
一、本质理解
图的本质是 节点的集合 + 节点之间的连接关系。
labuladong 将图归为”链表的延伸”——树的每个节点有多个子节点（多叉树），而图就是多叉树的进一步泛化（可以有环）。
核心关系：
链表 → 二叉树 → 多叉树 → 图
（线性） （二叉）（多叉） （有环）
二、图的表示
邻接表（最常用）
# 有向图
graph = {
0: [1, 2],
1: [3],
2: [3],
3: []
}
# 无向图（双向记录）
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2]
}网格（隐式图）
网格可以看作一个特殊的图，每个格子有 4 个邻居（上下左右）。
三、核心模板
模板 1：图 DFS
def dfs_graph(graph):
visited = set()
def dfs(node):
if node in visited:
return
visited.add(node)
# 处理节点
for neighbor in graph[node]:
dfs(neighbor)
# 遍历所有节点（处理非连通图）
for node in graph:
if node not in visited:
dfs(node)模板 2：图 BFS（求最短路径/最少步数）
from collections import deque
def bfs_graph(start, target, graph):
q = deque([start])
visited = {start}
step = 0
while q:
size = len(q)
for _ in range(size):
node = q.popleft()
if node == target:
return step
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
q.append(neighbor)
step += 1
return -1模板 3：网格 DFS（岛屿问题）
def num_islands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
count = 0
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' # 标记为已访问（沉岛）
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
dfs(i, j)
return count模板 4：多源 BFS（腐烂的橘子）
from collections import deque
def oranges_rotting(grid):
m, n = len(grid), len(grid[0])
q = deque()
fresh = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
q.append((i, j))
elif grid[i][j] == 1:
fresh += 1
if fresh == 0:
return 0
minutes = 0
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while q and fresh > 0:
minutes += 1
for _ in range(len(q)):
i, j = q.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
fresh -= 1
grid[ni][nj] = 2
q.append((ni, nj))
return minutes if fresh == 0 else -1模板 5：拓扑排序（Kahn 算法 / BFS 版）
from collections import deque
def can_finish(num_courses, prerequisites):
# 建图 + 计算入度
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, pre in prerequisites:
graph[pre].append(course)
indegree[course] += 1
# 入度为 0 的节点入队
q = deque([i for i in range(num_courses) if indegree[i] == 0])
count = 0
while q:
node = q.popleft()
count += 1
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
q.append(neighbor)
return count == num_courses # 无环则能完成四、Trie（前缀树）
class Trie:
def __init__(self):
self.children = {}
self.is_end = False
def insert(self, word):
node = self
for ch in word:
if ch not in node.children:
node.children[ch] = Trie()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self._find(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._find(prefix) is not None
def _find(self, word):
node = self
for ch in word:
if ch not in node.children:
return None
node = node.children[ch]
return node五、Hot 100 图论题目清单
| 题号 | 题目 | 难度 | 核心技巧 | 建议用时 |
|---|---|---|---|---|
| 200 | 岛屿数量 | Medium | 网格 DFS/BFS，沉岛法 | 30 min |
| 994 | 腐烂的橘子 | Medium | 多源 BFS，层数统计 | 30 min |
| 207 | 课程表 | Medium | 拓扑排序（Kahn 算法） | 35 min |
| 208 | 实现 Trie | Medium | 嵌套字典建树 | 30 min |
六、易错点与技巧
- DFS vs BFS 选择：求最短路径/最少步数用 BFS，求连通性/路径用 DFS
- visited 的两种方式：额外 visited 集合（通用）vs 原地修改（网格题”沉岛”）
- 多源 BFS：腐烂橘子是典型，多个起点同时入队，逐层扩散
- 拓扑排序的两种实现：BFS（Kahn）和 DFS（检测后序遍历的逆序），Kahn 更直观
- Trie 的内存：每个字符一个节点，字符串量大时内存消耗大
七、复杂度总结
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 图 DFS/BFS | O(V + E) | O(V) |
| 网格 DFS | O(m × n) | O(m × n) |
| 拓扑排序 | O(V + E) | O(V + E) |
| Trie 操作 | O(len(word)) | O(总字符数) |
八、参考与延伸
- 05-二叉树（树的遍历是图遍历的基础）
- 08-回溯算法（回溯 = DFS + 撤销操作）
- labuladong BFS/DFS 框架：https://labuladong.online/algo/
- 代码随想录图论：https://programmercarl.com/