引言 (Introduction)
图（Graph）是计算机科学中最通用的数据结构——网络拓扑、社交关系、地图导航、任务依赖，一切「节点 + 边」的系统都可以建模为图。图论的算法体系庞大，但万变不离其宗：先学会表示和遍历，其余所有算法（最短路径、生成树、拓扑排序）都以此为基础。
本文是本系列第一篇，聚焦于图的两种存储方式以及 BFS/DFS 两种遍历范式。我们将从显式图过渡到隐式图（网格），通过三道 LeetCode 题目建立从「读题」到「建图」再到「遍历」的完整流程。
1. 图的两种存储方式
1.1 邻接表
每个节点维护一个邻居列表，是表示稀疏图的最常用方式。
from typing import Dict, List, Set, Tuple
# 无向图
graph: Dict[int, List[int]] = {
0: [1, 2],
1: [0, 2, 3],
2: [0, 1],
3: [1]
}
# 带权有向图：每个邻居附带权重
weighted_graph: Dict[int, List[Tuple[int, int]]] = {
0: [(1, 5), (2, 3)], # 0→1 权重 5, 0→2 权重 3
1: [(3, 2)],
2: [(1, 1), (3, 6)],
3: []
}
空间复杂度：$O(V + E)$，每条边被存储两次（无向图）或一次（有向图）。
1.2 邻接矩阵
$V \times V$ 的二维数组，matrix[i][j] 表示 $i$ 到 $j$ 的边权（0 或 INF 表示无边）。
from typing import List
INF = float('inf')
# 权重图
matrix: List[List[float]] = [
[0, 5, 3, INF],
[INF, 0, INF, 2 ],
[INF, 1, 0, 6 ],
[INF, INF, INF, 0 ]
]
空间复杂度：$O(V^2)$。仅适用于稠密图（$E \approx V^2$）或需要 $O(1)$ 查询边权时。
1.3 选择法则
| 条件 | 选择 |
|---|---|
| $V$ 很大，$E$ 很少（稀疏） | 邻接表 |
| $E \approx V^2$（稠密） | 邻接矩阵 |
| 需要频繁查询「$i$ 到 $j$ 是否有边/权重多少」 | 邻接矩阵 |
| 需要遍历某节点的所有邻居 | 邻接表（$O(deg)$ vs $O(V)$） |
LeetCode 上的图题目绝大多数是稀疏图，默认使用邻接表。
1.4 建图模板
from typing import List, Dict
from collections import defaultdict
def build_graph(n: int, edges: List[List[int]], directed: bool = False) -> Dict[int, List[int]]:
"""将边列表转换为邻接表"""
graph: Dict[int, List[int]] = defaultdict(list)
for u, v in edges:
graph[u].append(v)
if not directed:
graph[v].append(u)
return dict(graph)
2. BFS：队列驱动与「最短路径」语义
2.1 BFS 的通用模板
BFS 的核心数据结构是队列（FIFO）。它按层遍历，天然保证「首次访问一个节点时所走的路径是从起点到该节点的最短路径」（边权全为 1 时）。
from typing import List, Dict
from collections import deque
def bfs(graph: Dict[int, List[int]], start: int) -> List[int]:
"""BFS 遍历图，返回访问顺序"""
visited: set[int] = {start}
queue: deque[int] = deque([start])
order: List[int] = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph.get(u, []):
if v not in visited:
visited.add(v)
queue.append(v)
return order
关键性质：
visited在入队时标记，而非出队时。如果在出队时才标记，同一节点可能被重复入队（如从多条路径到达同一节点的情况）。- 队列保证层序：所有距离为 $d$ 的节点在距离为 $d+1$ 的节点之前被处理。
2.2 BFS 求最短距离
在边权为 1 的图上，BFS 天然求出起点到所有节点的最短距离：
from typing import Dict, List
from collections import deque
def bfs_shortest_path(graph: Dict[int, List[int]], start: int) -> Dict[int, int]:
"""BFS 求起点到所有节点的最短距离（边权为 1）"""
dist: Dict[int, int] = {start: 0}
queue: deque[int] = deque([start])
while queue:
u = queue.popleft()
for v in graph.get(u, []):
if v not in dist: # 首次访问 = 最短距离
dist[v] = dist[u] + 1
queue.append(v)
return dist
当图不连通时，未被访问到的节点距离为 INF。
3. DFS：递归与「连通性」语义
3.1 DFS 的两种实现
递归版（最常用）：
from typing import List, Dict
def dfs_recursive(graph: Dict[int, List[int]]) -> List[int]:
"""递归 DFS"""
visited: set[int] = set()
order: List[int] = []
def dfs(u: int) -> None:
visited.add(u)
order.append(u)
for v in graph.get(u, []):
if v not in visited:
dfs(v)
for node in graph: # 处理非连通图
if node not in visited:
dfs(node)
return order
迭代版（手动维护栈，需要时可避免递归栈溢出）：
from typing import List, Dict
def dfs_iterative(graph: Dict[int, List[int]], start: int) -> List[int]:
"""迭代 DFS"""
visited: set[int] = set()
stack: List[int] = [start]
order: List[int] = []
while stack:
u = stack.pop()
if u not in visited:
visited.add(u)
order.append(u)
# 逆序入栈以保持与递归一致的访问顺序（可选）
for v in reversed(graph.get(u, [])):
if v not in visited:
stack.append(v)
return order
3.2 DFS 的核心语义
| 场景 | DFS 的用途 |
|---|---|
| 连通分量计数 | 每启动一次 DFS，就是一个新的连通分量 |
| 环检测 | 维护递归栈中节点，遇到回边即为环 |
| 拓扑排序 | 后序遍历的反向序列（第四篇详述） |
| 桥与割点 | Tarjan 算法（第五篇详述） |
4. 网格作为隐式图
4.1 核心思想
二维网格是图的一种特殊表示——每个格子 $(i, j)$ 是一个节点，四个方向（上下左右）是边。不需要显式建邻接表，直接用方向向量 + 坐标遍历邻居。
from typing import List, Tuple
# 四个方向的移动
DIRECTIONS: List[Tuple[int, int]] = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def get_neighbors(grid: List[List[int]], i: int, j: int) -> List[Tuple[int, int]]:
"""返回 (i, j) 的所有合法邻居"""
m, n = len(grid), len(grid[0])
neighbors: List[Tuple[int, int]] = []
for di, dj in DIRECTIONS:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n:
neighbors.append((ni, nj))
return neighbors
4.2 网格 BFS/DFS 模板
from typing import List, Tuple
from collections import deque
def grid_bfs(grid: List[List[int]], start_i: int, start_j: int) -> int:
"""网格 BFS，常用于统计连通区域面积"""
m, n = len(grid), len(grid[0])
queue: deque[Tuple[int, int]] = deque([(start_i, start_j)])
grid[start_i][start_j] = 0 # 原地标记已访问（沉岛法）
area = 1
while queue:
i, j = queue.popleft()
for di, dj in DIRECTIONS:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
grid[ni][nj] = 0 # 入队即标记
queue.append((ni, nj))
area += 1
return area
沉岛法：将已访问的 '1' 直接改为 '0'，省去 visited 数组的空间。回溯场景需要恢复原值。
5. LeetCode 200：岛屿数量
题目：'1' 为陆地，'0' 为水域。计算网格中岛屿的数量（陆地四向相连）。
这是连通分量计数的标准题。遍历每个格子，遇到 '1' 则 DFS/BFS 沉没整个岛屿，计数 +1。
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
count = 0
def dfs(i: int, j: int) -> None:
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0':
return
grid[i][j] = '0' # 沉岛
for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
dfs(i + di, j + dj)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
dfs(i, j)
return count
复杂度：时间 $O(mn)$（每个格子访问一次），空间 $O(mn)$（递归栈最坏全为陆地）。
6. LeetCode 695：岛屿的最大面积
题目：求网格中最大的岛屿面积。
与 200 完全相同的框架，只需在 DFS/BFS 时统计面积。
from typing import List
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
max_area = 0
def dfs(i: int, j: int) -> int:
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
return 0
grid[i][j] = 0
return 1 + 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:
max_area = max(max_area, dfs(i, j))
return max_area
复杂度：时间 $O(mn)$，空间 $O(mn)$。
7. LeetCode 994：腐烂的橘子
题目：网格中 2 表示腐烂橘子，1 表示新鲜橘子，0 表示空格。每分钟腐烂橘子会使四邻的新鲜橘子腐烂。求所有橘子腐烂所需的最少分钟数，若无法全腐则返回 -1。
这是多源 BFS 的标准题——将初始所有腐烂橘子同时入队，BFS 层数即为时间。
from typing import List
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
queue: deque = deque()
fresh = 0
# 多源初始化：所有腐烂橘子入队
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append((i, j, 0)) # (行, 列, 分钟数)
elif grid[i][j] == 1:
fresh += 1
if fresh == 0:
return 0
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
minutes = 0
while queue:
i, j, t = queue.popleft()
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
grid[ni][nj] = 2
fresh -= 1
queue.append((ni, nj, t + 1))
minutes = max(minutes, t + 1)
return minutes if fresh == 0 else -1
复杂度：时间 $O(mn)$，空间 $O(mn)$。
多源 BFS 的关键：不是从每个源分别 BFS，而是将所有源同时入队、统一 BFS。队列中的层序天然模拟了「同时扩散」的时间推进。
8. BFS vs DFS 的选择指南
| 需求 | 选择 | 原因 |
|---|---|---|
| 最短路径（无权图） | BFS | 按层访问，首次相遇即最短 |
| 连通分量/区域填充 | DFS 或 BFS | 两者均可，DFS 更短 |
| 检测环路 | DFS（维护递归栈） | 递归栈天然表示当前路径 |
| 层序遍历/层级统计 | BFS | 队列的 FIFO 保证层序 |
| 图可能很深（防栈溢出） | BFS | 无递归 |
| 需要回溯路径 | DFS | 递归展开时路径在栈上 |
默认选择：无权最短路径用 BFS，其余遍历场景用 DFS（代码更短）。不确定时优先选 BFS（无栈溢出风险）。
结论 (Conclusion)
本文建立了图论的基础设施：邻接表存储、BFS 与 DFS 的模板、以及网格作为隐式图的建模范式。三道题目（200、695、994）覆盖了连通分量、面积统计、多源 BFS 三个核心基础模式。
下一篇预览：最短路径算法三部曲——Dijkstra（非负权）、Bellman-Ford（可负权）、Floyd-Warshall（全源），以及如何在不同图条件下选择最合适的最短路算法（LeetCode 743、787、1334）。