第 16 章
图的表示与遍历
第十六章：图的表示与遍历
在前面的章节中，我们学习了各种线性和层次结构——数组、链表、树。这些结构有一个共同特点：它们的连接关系是"规则的"。数组中每个元素有前驱和后继，树中每个节点有一个父节点和若干子节点。但现实世界中，许多关系远比这些复杂——社交网络中的好友关系是多对多的、城市之间的道路网络是纵横交错的、互联网的网页通过超链接彼此指向。
图（Graph） 是描述这些复杂关系的终极数据结构。它由顶点（Vertex/Node） 和边（Edge） 组成，可以表达任意两个实体之间的关系。图论不仅是计算机科学的基础，更是离散数学中最富有成果的分支之一。
本章我们将解决三个核心问题：(1) 如何在计算机中高效地表示一个图？(2) 如何系统地访问图中的每一个顶点？(3) 遍历的过程能告诉我们关于图的哪些结构信息？
Level 1 · 你需要知道的
16.1 图的基本概念
定义：图 G = (V, E)，其中 V 是顶点集合，E 是边集合。每条边连接两个顶点。
根据边是否有方向，图分为两大类：
- 无向图（Undirected Graph）：边没有方向，(u, v) 和 (v, u) 是同一条边。例如：微信好友关系（互为好友）。
- 有向图（Directed Graph / Digraph）：边有方向，从 u 到 v 的边记作 (u, v)，u→v 和 v→u 是不同的边。例如：微博关注关系（A 关注 B，B 不一定关注 A）。
其他重要术语：
| 术语 | 含义 |
|---|---|
| 度（Degree） | 与某顶点相连的边数。有向图中分入度和出度 |
| 路径（Path） | 从顶点 u 到顶点 v 经过的顶点序列 |
| 环/回路（Cycle） | 起点和终点相同的路径 |
| 连通（Connected） | 无向图中任意两个顶点之间都有路径 |
| 强连通（Strongly Connected） | 有向图中任意两个顶点之间都有有向路径 |
| 权重（Weight） | 边上的数值，表示距离、代价等 |
无向图示例（社交网络）： 有向图示例（网页链接）：
A --- B A → B
| / | ↑ ↓
| / | D ← C
C --- D
无向图：边没有箭头 有向图：边有方向
A-B 表示 A和B互为好友 A→B 表示 A链接到B
16.2 图的两种存储方式
计算机中存储图，主要有两种经典方式：邻接矩阵和邻接表。
16.2.1 邻接矩阵（Adjacency Matrix）
用一个 |V|×|V| 的二维数组 matrix 表示图。matrix[i][j] = 1（或权重值）表示从顶点 i 到顶点 j 有一条边；matrix[i][j] = 0 表示无边。
class GraphMatrix:
"""基于邻接矩阵的图表示"""
def __init__(self, num_vertices: int, directed: bool = False):
self.n = num_vertices
self.directed = directed
# 创建 n×n 的零矩阵
self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, u: int, v: int, weight: int = 1):
"""添加边 u → v"""
self.matrix[u][v] = weight
if not self.directed:
self.matrix[v][u] = weight # 无向图：双向
def has_edge(self, u: int, v: int) -> bool:
"""查询边是否存在 —— O(1)"""
return self.matrix[u][v] != 0
def get_neighbors(self, u: int) -> list:
"""获取所有邻居 —— O(V)"""
neighbors = []
for v in range(self.n):
if self.matrix[u][v] != 0:
neighbors.append(v)
return neighbors
def degree(self, u: int) -> int:
"""顶点的度"""
return sum(1 for v in range(self.n) if self.matrix[u][v] != 0)
# 示例：创建一个无向图
# 0 --- 1
# | / |
# | / |
# 2 --- 3
g = GraphMatrix(4, directed=False)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
print(g.has_edge(0, 1)) # True
print(g.has_edge(0, 3)) # False
print(g.get_neighbors(1)) # [0, 2, 3]
邻接矩阵的特点：
| 操作 | 时间复杂度 |
|---|---|
| 查询边 (u, v) 是否存在 | O(1) |
| 获取所有邻居 | O(V) |
| 添加边 | O(1) |
| 空间复杂度 | O(V²) |
优点：查询边的存在性极快（O(1)随机访问）；实现简单。
缺点：空间 O(V²)，对稀疏图（边远少于 V²）非常浪费。
16.2.2 邻接表（Adjacency List）
对每个顶点，维护一个列表，记录所有与之相邻的顶点。这是实际工程中最常用的表示。
from collections import defaultdict
class GraphList:
"""基于邻接表的图表示"""
def __init__(self, directed: bool = False):
self.directed = directed
self.adj = defaultdict(list) # 邻接表
def add_edge(self, u, v, weight=1):
"""添加边 u → v"""
self.adj[u].append((v, weight))
if not self.directed:
self.adj[v].append((u, weight)) # 无向图：双向
def has_edge(self, u, v) -> bool:
"""查询边是否存在 —— O(degree(u))"""
return any(neighbor == v for neighbor, _ in self.adj[u])
def get_neighbors(self, u) -> list:
"""获取所有邻居 —— O(degree(u))"""
return [v for v, _ in self.adj[u]]
def degree(self, u) -> int:
"""顶点的度"""
return len(self.adj[u])
def vertices(self) -> set:
"""所有顶点"""
return set(self.adj.keys())
# 示例：同样的图用邻接表表示
g = GraphList(directed=False)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
print(g.get_neighbors(1)) # [0, 2, 3]（含权重版本会是元组列表）
print(g.degree(1)) # 3
邻接表的特点：
| 操作 | 时间复杂度 |
|---|---|
| 查询边 (u, v) 是否存在 | O(degree(u)) |
| 获取所有邻居 | O(degree(u)) |
| 添加边 | O(1) |
| 空间复杂度 | O(V + E) |
优点：空间高效（只存实际存在的边）；遍历邻居快。
缺点：查询特定边不如邻接矩阵快。
16.2.3 如何选择？
| 条件 | 推荐表示 |
|---|---|
| 稠密图（E ≈ V²） | 邻接矩阵 |
| 稀疏图（E << V²） | 邻接表 |
| 需要频繁查询特定边 | 邻接矩阵 |
| 需要遍历所有邻居 | 邻接表 |
| 顶点数极大（如百万级） | 邻接表（矩阵放不下） |
关键直觉：现实世界的大多数图都是稀疏的。社交网络有数十亿用户，但每人平均只有几百个好友；互联网有数十亿网页，但每个网页只链接到有限的其他页面。因此，邻接表是工程中的默认选择。
16.3 广度优先搜索（BFS）
BFS 从一个起始顶点出发，先访问所有距离为 1 的顶点，再访问所有距离为 2 的顶点……像水波一样一层层向外扩散。
核心思想：使用队列（FIFO），每次从队列中取出一个顶点，将其所有未访问的邻居加入队列。
from collections import deque
def bfs(graph: GraphList, start) -> list:
"""
广度优先搜索
返回 BFS 访问顺序
"""
visited = set()
order = []
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get_neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
# 示例
g = GraphList()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)
print(bfs(g, 0)) # [0, 1, 2, 3, 4]
BFS 的关键性质：
- 层序遍历：BFS 按距离起点的层数逐层访问。
- 最短路径（无权图）：BFS 首次到达某顶点时，经过的边数就是从起点到该顶点的最短路径长度。
- 时间复杂度：O(V + E)——每个顶点入队出队一次，每条边被检查一次。
- 空间复杂度：O(V)——visited 集合和队列最多存 V 个顶点。
BFS 求最短路径（无权图）：
def bfs_shortest_path(graph: GraphList, start, end) -> list:
"""
BFS 找从 start 到 end 的最短路径（无权图）
返回路径顶点列表，或空列表（不可达）
"""
if start == end:
return [start]
visited = {start}
queue = deque([(start, [start])]) # (当前节点, 从起点到此的路径)
while queue:
node, path = queue.popleft()
for neighbor in graph.get_neighbors(node):
if neighbor not in visited:
new_path = path + [neighbor]
if neighbor == end:
return new_path
visited.add(neighbor)
queue.append((neighbor, new_path))
return [] # 不可达
# 更高效的版本：只记录 parent，最后回溯路径
def bfs_shortest_path_v2(graph: GraphList, start, end) -> list:
"""高效版本：用 parent 字典回溯路径"""
if start == end:
return [start]
visited = {start}
parent = {start: None}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph.get_neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = node
if neighbor == end:
# 回溯路径
path = []
cur = end
while cur is not None:
path.append(cur)
cur = parent[cur]
return path[::-1]
queue.append(neighbor)
return []
16.4 深度优先搜索（DFS）
DFS 从起始顶点出发，沿着一条路径尽可能深地探索，直到无法继续，然后回溯，尝试其他路径。
核心思想：使用栈（隐式的递归调用栈或显式栈），每次深入一个未访问的邻居。
def dfs_recursive(graph: GraphList, start) -> list:
"""
深度优先搜索 —— 递归版本
"""
visited = set()
order = []
def _dfs(node):
visited.add(node)
order.append(node)
for neighbor in graph.get_neighbors(node):
if neighbor not in visited:
_dfs(neighbor)
_dfs(start)
return order
def dfs_iterative(graph: GraphList, start) -> list:
"""
深度优先搜索 —— 迭代版本（显式栈）
"""
visited = set()
order = []
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
# 逆序压栈，保证按邻居顺序访问
for neighbor in reversed(graph.get_neighbors(node)):
if neighbor not in visited:
stack.append(neighbor)
return order
# 示例
g = GraphList()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)
print(dfs_recursive(g, 0)) # [0, 1, 3, 2, 4] 或其他 DFS 序
print(dfs_iterative(g, 0)) # [0, 1, 3, 2, 4] 或其他 DFS 序
DFS 的关键性质：
- 深入优先：尽可能沿着一个方向深入，然后回溯。
- 时间复杂度：O(V + E)——和 BFS 相同。
- 空间复杂度：O(V)——递归调用栈深度最坏为 V（链状图）。
- 用途广泛：检测环、拓扑排序、求连通分量、二分图判定等。
BFS vs DFS 对比：
| 特性 | BFS | DFS |
|---|---|---|
| 数据结构 | 队列 | 栈 |
| 遍历顺序 | 按层（由近及远） | 按深度（一路到底） |
| 最短路径 | 可求（无权图） | 不保证 |
| 空间 | O(宽度) | O(深度) |
| 适用场景 | 最短路径、层序遍历 | 环检测、拓扑排序、连通性 |
16.5 连通分量
对于无向图，如果图不连通（不是所有顶点都能互达），那么图由若干连通分量（Connected Component） 组成。每个连通分量是一个最大连通子图。
def find_connected_components(graph: GraphList) -> list:
"""
找出无向图的所有连通分量
返回：列表的列表，每个子列表是一个连通分量中的顶点
"""
visited = set()
components = []
for vertex in graph.vertices():
if vertex not in visited:
# 从这个顶点开始 BFS/DFS，找到整个连通分量
component = []
queue = deque([vertex])
visited.add(vertex)
while queue:
node = queue.popleft()
component.append(node)
for neighbor in graph.get_neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
components.append(component)
return components
# 示例：两个不连通的子图
g = GraphList()
g.add_edge(0, 1)
g.add_edge(1, 2) # 连通分量1: {0, 1, 2}
g.add_edge(3, 4) # 连通分量2: {3, 4}
print(find_connected_components(g)) # [[0, 1, 2], [3, 4]]
核心思路：遍历所有顶点；对于每个未访问的顶点，启动一次 BFS/DFS，能到达的所有顶点构成一个连通分量。
时间复杂度：O(V + E)——虽然有外层循环，但每个顶点/边只被访问一次。
16.6 二分图判定
二分图（Bipartite Graph）：如果图的顶点可以分成两组 A 和 B，使得所有的边都连接 A 中的顶点和 B 中的顶点（即同组内没有边），则图是二分图。
判定方法：尝试用两种颜色给图着色。如果可以让相邻顶点颜色不同，则是二分图；否则不是。
def is_bipartite(graph: GraphList) -> bool:
"""
判断无向图是否是二分图
使用 BFS 染色法
"""
color = {} # 顶点 → 颜色(0 或 1)
for start in graph.vertices():
if start in color:
continue
# BFS 染色
queue = deque([start])
color[start] = 0
while queue:
node = queue.popleft()
for neighbor in graph.get_neighbors(node):
if neighbor not in color:
# 邻居染相反颜色
color[neighbor] = 1 - color[node]
queue.append(neighbor)
elif color[neighbor] == color[node]:
# 邻居颜色相同 → 不是二分图
return False
return True
# 示例1：二分图
# 0 --- 1
# | |
# 3 --- 2
# 可以将 {0,2} 染红，{1,3} 染蓝
g1 = GraphList()
g1.add_edge(0, 1)
g1.add_edge(1, 2)
g1.add_edge(2, 3)
g1.add_edge(3, 0)
print(is_bipartite(g1)) # True
# 示例2：非二分图（有奇数环）
# 0 --- 1
# \ /
# 2
g2 = GraphList()
g2.add_edge(0, 1)
g2.add_edge(1, 2)
g2.add_edge(2, 0)
print(is_bipartite(g2)) # False（三角形有奇数环）
定理：一个图是二分图，当且仅当它不包含奇数长度的环（König, 1916）。
直觉：如果有一个奇数环，从某顶点出发沿环走一圈回来，颜色必然冲突。
16.7 常见错误
错误1：忘记标记已访问
# 错误：没有 visited 集合，会陷入无限循环
def bfs_wrong(graph, start):
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph.get_neighbors(node):
queue.append(neighbor) # 无限循环！
错误2：DFS 递归深度超限
# Python 默认递归深度限制是 1000
# 对于大图（如 10000 个节点的链），递归 DFS 会栈溢出
import sys
sys.setrecursionlimit(100000) # 临时解决方案
# 更好的方案：使用迭代 DFS
错误3：有向图中混淆连通性
# 有向图中 A→B 不代表 B→A
# "A 能到 B" ≠ "B 能到 A"
# 无向图的"连通"在有向图中对应"强连通"
Level 2 · 它是怎么运行的
16.8 图的存储优化：稀疏 vs 稠密
让我们量化分析两种表示在不同密度图上的表现。
图的密度定义：密度 d = |E| / (|V|² / 2)（无向图），其中 |V|²/2 是最大可能边数。当 d 接近 1 时为稠密图，接近 0 时为稀疏图。
现实中各类图的密度对比：
| 图类型 | 典型规模 | 典型密度 | 推荐表示 |
|---|---|---|---|
| 社交网络 | V=10⁹, E=10¹¹ | ~10⁻⁷ | 邻接表 |
| 道路网络 | V=10⁷, E=3×10⁷ | ~10⁻⁶ | 邻接表 |
| 全连接神经网络层 | V=10³, E≈V² | ~1 | 邻接矩阵（即权重矩阵） |
| 分子结构图 | V=10¹~10², E≈3V | ~0.06 | 邻接表 |
内存对比实验：
import sys
def memory_comparison(V: int, E: int):
"""对比两种表示的内存使用"""
# 邻接矩阵：V×V 个整数
# 每个 Python int 约 28 字节，但 numpy 可以用 1 字节
matrix_memory_naive = V * V * 28 # Python list
matrix_memory_numpy = V * V * 1 # numpy bool array
# 邻接表：每条边存两次（无向图）
# 每个列表项约 8 字节（指针）+ 28 字节（int对象）
adjlist_memory = E * 2 * 36 # 无向图每条边存两次
print(f"图规模: V={V}, E={E}, 密度={2*E/(V*V):.6f}")
print(f"邻接矩阵 (numpy): {matrix_memory_numpy / 1024 / 1024:.1f} MB")
print(f"邻接表: {adjlist_memory / 1024 / 1024:.1f} MB")
print(f"比值: {matrix_memory_numpy / max(adjlist_memory, 1):.2f}")
print()
# 稀疏图：10000 节点，30000 条边
memory_comparison(10000, 30000)
# 邻接矩阵: 95.4 MB vs 邻接表: 2.1 MB → 邻接表胜
# 稠密图：1000 节点，400000 条边
memory_comparison(1000, 400000)
# 邻接矩阵: 1.0 MB vs 邻接表: 27.5 MB → 矩阵胜
工程中的优化策略：
- 压缩稀疏行（CSR）格式：用于超大规模稀疏图。用三个数组表示：
values[]：所有边的权重col_indices[]：每条边指向的目标顶点row_offsets[]：每个顶点的邻居在col_indices中的起始位置
class GraphCSR:
"""压缩稀疏行格式 —— 适合大规模只读图"""
def __init__(self, num_vertices, edges):
"""
edges: List of (u, v, weight) 元组，已排序
"""
self.n = num_vertices
# 按源顶点排序
edges.sort(key=lambda e: e[0])
self.col_indices = [e[1] for e in edges]
self.weights = [e[2] for e in edges]
# 计算每行的起始偏移
self.row_offsets = [0] * (num_vertices + 1)
for u, v, w in edges:
self.row_offsets[u + 1] += 1
for i in range(1, num_vertices + 1):
self.row_offsets[i] += self.row_offsets[i - 1]
def get_neighbors(self, u):
"""O(degree(u)) 获取邻居"""
start = self.row_offsets[u]
end = self.row_offsets[u + 1]
return list(zip(self.col_indices[start:end], self.weights[start:end]))
- 邻接集合（Adjacency Set）：如果需要频繁查询边是否存在，可以把邻接表中的 list 换成 set，将查询降为摊还 O(1)：
class GraphSet:
"""邻接集合：兼顾空间效率和快速边查询"""
def __init__(self, directed=False):
self.directed = directed
self.adj = defaultdict(set)
def add_edge(self, u, v):
self.adj[u].add(v)
if not self.directed:
self.adj[v].add(u)
def has_edge(self, u, v) -> bool:
return v in self.adj[u] # 平均 O(1)
16.9 BFS 与无权图最短路径
BFS 最重要的理论性质是它能在无权图中找到最短路径。这个结论虽然直观，但需要严格证明。
定理：在无权图 G = (V, E) 中，BFS 从源点 s 出发时，对于每个顶点 v，BFS 发现 v 时经过的边数 d(s,v) 等于 s 到 v 的最短路径长度。
证明思路：
设 δ(s,v) 为 s 到 v 的真实最短距离（最少边数），d(s,v) 为 BFS 发现 v 时的层数。
- d(s,v) ≥ δ(s,v)：BFS 发现 v 经过的路径是一条合法路径，不可能短于最短路径。
- d(s,v) ≤ δ(s,v)：用归纳法。假设对所有距离 < k 的顶点成立。对于 δ(s,v) = k 的顶点 v，必有某邻居 u 满足 δ(s,u) = k-1。由归纳假设，BFS 在第 k-1 层发现了 u，然后在处理 u 的邻居时会发现 v（如果 v 尚未被发现），此时 v 的层数为 k。
因此 d(s,v) = δ(s,v)。□
BFS 带层次信息的完整实现：
def bfs_with_levels(graph: GraphList, start):
"""
BFS 同时记录每个节点的距离和前驱
返回 (distance, parent) 字典
"""
dist = {start: 0}
parent = {start: None}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph.get_neighbors(node):
if neighbor not in dist:
dist[neighbor] = dist[node] + 1
parent[neighbor] = node
queue.append(neighbor)
return dist, parent
def reconstruct_path(parent: dict, start, end) -> list:
"""从 parent 字典回溯最短路径"""
if end not in parent:
return [] # 不可达
path = []
cur = end
while cur is not None:
path.append(cur)
cur = parent[cur]
return path[::-1]
# 示例：六度分隔理论
# 在社交网络图中，BFS 可以找到两个人之间的最短关系链
g = GraphList()
edges = [(0,1),(0,2),(1,3),(2,4),(3,5),(4,5),(5,6)]
for u, v in edges:
g.add_edge(u, v)
dist, parent = bfs_with_levels(g, 0)
print(f"从 0 到 6 的最短距离: {dist[6]}") # 3
print(f"最短路径: {reconstruct_path(parent, 0, 6)}") # [0, 1, 3, 5, 6]
多源 BFS：
有时需要同时从多个源点出发做 BFS。例如，"找到每个空地到最近的建筑物的距离"。技巧是将所有源点同时放入初始队列：
def multi_source_bfs(graph: GraphList, sources: list) -> dict:
"""
多源 BFS：同时从多个源点出发
返回每个顶点到最近源点的距离
"""
dist = {}
queue = deque()
for s in sources:
dist[s] = 0
queue.append(s)
while queue:
node = queue.popleft()
for neighbor in graph.get_neighbors(node):
if neighbor not in dist:
dist[neighbor] = dist[node] + 1
queue.append(neighbor)
return dist
16.10 DFS 的时间戳与边的分类
DFS 有一个极其强大的工具：时间戳（Timestamp）。在 DFS 过程中，为每个顶点记录两个时间：
- 发现时间（discovery time） d[v]：首次访问顶点 v 的时刻
- 完成时间（finish time） f[v]：v 的所有后代都已探索完毕的时刻
class DFSWithTimestamp:
"""带时间戳的 DFS"""
def __init__(self, graph: GraphList):
self.graph = graph
self.discovery = {} # 发现时间
self.finish = {} # 完成时间
self.parent = {} # DFS 树中的父节点
self.time = 0 # 全局时钟
self.edge_type = {} # 边的分类
def dfs(self):
"""对整个图执行 DFS"""
for v in self.graph.vertices():
self.parent[v] = None
for v in self.graph.vertices():
if v not in self.discovery:
self._dfs_visit(v)
def _dfs_visit(self, u):
"""访问顶点 u"""
self.time += 1
self.discovery[u] = self.time
for v in self.graph.get_neighbors(u):
if v not in self.discovery:
# v 未被发现 → 树边
self.edge_type[(u, v)] = "tree"
self.parent[v] = u
self._dfs_visit(v)
elif v not in self.finish:
# v 已发现但未完成 → 回边（检测到环！）
self.edge_type[(u, v)] = "back"
elif self.discovery[u] < self.discovery[v]:
# v 已完成，且 v 在 u 之后被发现 → 前向边
self.edge_type[(u, v)] = "forward"
else:
# v 已完成，且 v 在 u 之前被发现 → 交叉边
self.edge_type[(u, v)] = "cross"
self.time += 1
self.finish[u] = self.time
# 示例：有向图
g = GraphList(directed=True)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(3, 0) # 回边：形成环 0→1→3→0
g.add_edge(2, 3)
dfs = DFSWithTimestamp(g)
dfs.dfs()
print("发现/完成时间:")
for v in sorted(dfs.discovery.keys()):
print(f" 顶点 {v}: d={dfs.discovery[v]}, f={dfs.finish[v]}")
print("\n边的分类:")
for edge, etype in dfs.edge_type.items():
print(f" {edge[0]} → {edge[1]}: {etype}")
四种边的含义：
| 边类型 | 定义 | 意义 |
|---|---|---|
| 树边（Tree Edge） | 通向未发现顶点 | DFS 树的边 |
| 回边（Back Edge） | 通向祖先（已发现但未完成） | 存在回边 ⟺ 图有环 |
| 前向边（Forward Edge） | 通向后代（已完成，发现时间更晚） | 只在有向图中 |
| 交叉边（Cross Edge） | 通向非祖先非后代的已完成顶点 | 只在有向图中 |
括号定理（Parenthesis Theorem）：
对于任意两个顶点 u 和 v，以下三种情况恰好有一种成立：
- 区间 [d[u], f[u]] 和 [d[v], f[v]] 完全不相交 → u 和 v 在 DFS 树中无祖先后代关系
- [d[u], f[u]] 完全包含 [d[v], f[v]] → v 是 u 的后代
- [d[v], f[v]] 完全包含 [d[u], f[u]] → u 是 v 的后代
这就像括号的嵌套关系——发现时间是"左括号"，完成时间是"右括号"，括号要么嵌套要么不相交，不会交叉。
白色路径定理（White Path Theorem）：
在 DFS 中，v 是 u 的后代，当且仅当在发现 u 的时刻，存在一条从 u 到 v 的路径，路径上所有顶点都是白色的（未被发现）。
这两个定理是 DFS 众多应用（拓扑排序、强连通分量、割点/桥）的理论基础。
16.11 利用 DFS 检测环
无向图的环检测：
在无向图中，如果 DFS 遇到一个已访问且不是当前节点父节点的邻居，则存在环。
def has_cycle_undirected(graph: GraphList) -> bool:
"""无向图环检测"""
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph.get_neighbors(node):
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
# 遇到已访问的非父节点 → 有环
return True
return False
for v in graph.vertices():
if v not in visited:
if dfs(v, -1):
return True
return False
有向图的环检测：
有向图中，环的存在等价于 DFS 发现回边。
def has_cycle_directed(graph: GraphList) -> bool:
"""有向图环检测：三色标记法"""
# WHITE=未访问, GRAY=正在访问(在递归栈中), BLACK=已完成
WHITE, GRAY, BLACK = 0, 1, 2
color = {v: WHITE for v in graph.vertices()}
def dfs(node):
color[node] = GRAY
for neighbor in graph.get_neighbors(node):
if color[neighbor] == GRAY:
return True # 回边 → 有环
if color[neighbor] == WHITE:
if dfs(neighbor):
return True
color[node] = BLACK
return False
for v in graph.vertices():
if color[v] == WHITE:
if dfs(v):
return True
return False
三色标记法的直觉：
- 白色：尚未探索
- 灰色：正在探索（在当前 DFS 路径上）
- 黑色：探索完毕
如果从灰色节点出发遇到另一个灰色节点，说明我们找到了一条从该灰色节点到自身的路径——即一个环。
16.12 图遍历的应用模式
模式1：网格图（Grid Graph）
许多面试题将二维网格视为图，每个格子是一个顶点，上下左右相邻的格子之间有边。
def grid_bfs(grid: list, start_row: int, start_col: int):
"""二维网格上的 BFS"""
rows, cols = len(grid), len(grid[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 右左下上
visited = set()
visited.add((start_row, start_col))
queue = deque([(start_row, start_col, 0)]) # (行, 列, 距离)
while queue:
r, c, dist = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols and
(nr, nc) not in visited and grid[nr][nc] != '#'):
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
模式2：隐式图（Implicit Graph）
有些问题的图不是显式给出的，而是由状态和转移规则隐式定义的。例如，"从数字 x 出发，每次可以 +1、×2、-1，最少几步到达 y？"——这就是在隐式图上做 BFS。
def min_operations(start: int, target: int) -> int:
"""从 start 到 target，每步可以 +1, -1, ×2"""
if start >= target:
return start - target # 只能 -1
visited = set([start])
queue = deque([(start, 0)])
while queue:
num, steps = queue.popleft()
for next_num in [num + 1, num - 1, num * 2]:
if next_num == target:
return steps + 1
if 0 <= next_num <= 2 * target and next_num not in visited:
visited.add(next_num)
queue.append((next_num, steps + 1))
return -1
Level 3 · 规范怎么定义的
16.13 欧拉与图论的诞生：七桥问题（1736）
图论作为数学分支的诞生，可以精确追溯到一个时刻：1736年，瑞士数学家莱昂哈德·欧拉（Leonhard Euler） 发表了论文《Solutio problematis ad geometriam situs pertinentis》（关于一个与位置几何有关的问题的解），解决了著名的柯尼斯堡七桥问题。
问题背景：18世纪的柯尼斯堡（今俄罗斯加里宁格勒）有一条河（普雷格尔河）穿城而过，河中有两个岛。城市的四块陆地由七座桥相连。居民们提出一个问题：能否找到一条路线，恰好经过每座桥一次，然后回到起点？
柯尼斯堡七桥的抽象图：
A
/ \
/ \
1 2
/ \
B ---3--- C
\ /
4 5
\ /
\ /
D
/ \
6 7
/ \
B C
简化为多重图：
A（度=5）: 连接B×2, C×2, D×1
B（度=3）: 连接A×2, D×1
C（度=3）: 连接A×2, D×1
D（度=3）: 连接A×1, B×1, C×1
（注：这里用 A,B,C,D 代表四块陆地）
实际是 A-B 有2座桥, A-C 有2座桥, A-D 有1座桥, B-D 有1座桥, C-D 有1座桥
→ A 度=5, B 度=3, C 度=3, D 度=3
欧拉的解法：
欧拉做了一个天才的抽象——他不关心陆地的面积、桥的长度、路线的形状，只关心连接关系。他将四块陆地抽象为顶点，七座桥抽象为边，从而将一个地理问题转化为纯粹的数学问题。
这个抽象本身就是图论的诞生时刻。
欧拉定理：一个连通图存在欧拉回路（经过每条边恰好一次并回到起点）的充要条件是：每个顶点的度数都是偶数。存在欧拉路径（经过每条边恰好一次但不要求回到起点）的充要条件是：恰好有 0 个或 2 个奇数度顶点。
证明（必要性）：如果存在欧拉回路，那么每次路径经过一个顶点时，必然"从一条边进入，从另一条边离开"——消耗两条边。对于非起始顶点，所有边都是成对消耗的，所以度数必须是偶数。起始顶点最初"离开"用一条边，最后"回来"用一条边，其余也是成对的，所以度数也是偶数。
应用到七桥问题：四个顶点的度数分别是 5, 3, 3, 3——全是奇数！因此欧拉回路不存在，欧拉路径也不存在（奇数度顶点有4个，不是0或2）。
def has_eulerian_circuit(graph: GraphList) -> bool:
"""判断无向连通图是否有欧拉回路"""
for v in graph.vertices():
if graph.degree(v) % 2 != 0:
return False
return True
def has_eulerian_path(graph: GraphList) -> tuple:
"""
判断无向连通图是否有欧拉路径
返回 (是否存在, 起点)
"""
odd_degree_vertices = [v for v in graph.vertices() if graph.degree(v) % 2 != 0]
if len(odd_degree_vertices) == 0:
# 欧拉回路（也是欧拉路径），任意起点
return True, next(iter(graph.vertices()))
elif len(odd_degree_vertices) == 2:
# 欧拉路径，必须从奇数度顶点出发
return True, odd_degree_vertices[0]
else:
return False, None
历史意义：
欧拉的贡献不仅在于解决了七桥问题，更在于：
- 创立了图论：将具体问题抽象为"顶点+边"的数学结构
- 开创了拓扑学的思想：只关心连接关系，不关心度量（距离、面积）
- 证明了不可能性：不是找到了答案，而是证明了答案不存在——这是数学中极为深刻的思维方式
16.14 图的表示在社交网络与推荐系统中的应用
现代互联网的核心产品——社交网络和推荐系统——本质上是大规模图算法的工程实践。
社交网络：Facebook 的 TAO
Facebook（Meta）的社交图有约 30 亿顶点和数千亿条边。他们的图存储系统 TAO（The Associations and Objects）在 2013 年由 Bronson et al. 发表于 USENIX ATC。
TAO 的核心设计决策：
- 分离对象和关联：顶点（用户、帖子、评论）存为 Object，边（好友关系、点赞、评论）存为 Association。
- 邻接表分片：按源顶点 ID 哈希分片，每个分片存储一部分顶点的邻接表。
- 反向边索引：对于关系查询"谁关注了我"，维护反向邻接表。
- 分层缓存：热门顶点（如名人）的邻接表缓存在内存中。
# TAO 的简化模型
class SocialGraph:
"""社交网络图存储的简化模型"""
def __init__(self):
# 正向邻接表：user_id → set of (friend_id, timestamp, edge_type)
self.forward = defaultdict(set)
# 反向邻接表：user_id → set of (follower_id, timestamp)
self.reverse = defaultdict(set)
def add_follow(self, follower: int, followee: int, timestamp: int):
"""A 关注 B"""
self.forward[follower].add((followee, timestamp, "follow"))
self.reverse[followee].add((follower, timestamp))
def get_following(self, user: int) -> list:
"""获取某人关注的人列表"""
return [(uid, ts) for uid, ts, _ in self.forward[user]]
def get_followers(self, user: int) -> list:
"""获取某人的粉丝列表"""
return list(self.reverse[user])
def mutual_friends(self, u: int, v: int) -> set:
"""共同好友 —— 图的邻居交集"""
friends_u = {uid for uid, _, _ in self.forward[u]}
friends_v = {uid for uid, _, _ in self.forward[v]}
return friends_u & friends_v
推荐系统：基于图的协同过滤
推荐系统的一种经典方法是将用户和物品构建为二分图，然后利用图结构做推荐。
思路：如果用户 A 和用户 B 有很多共同喜欢的物品（在二分图中有很多长度为 2 的路径），那么 A 喜欢而 B 未接触的物品可以推荐给 B。
def recommend_items(user_item_graph: dict, target_user: int, top_k: int = 5) -> list:
"""
基于二分图的简单推荐
user_item_graph: {user_id: set of item_ids}
"""
target_items = user_item_graph[target_user]
# 找到相似用户（有共同喜好的用户）
item_scores = defaultdict(float)
for other_user, other_items in user_item_graph.items():
if other_user == target_user:
continue
# 相似度 = 共同物品数 / 总物品数（Jaccard 系数）
common = target_items & other_items
if not common:
continue
similarity = len(common) / len(target_items | other_items)
# 推荐 other_user 喜欢而 target_user 未接触的物品
for item in other_items - target_items:
item_scores[item] += similarity
# 按分数排序，返回 top_k
recommended = sorted(item_scores.items(), key=lambda x: -x[1])
return [item for item, score in recommended[:top_k]]
图数据库：Neo4j 与属性图模型
图数据库使用属性图模型（Property Graph Model）：顶点和边都可以有类型和属性。这比简单的邻接表丰富得多。
Neo4j 的查询语言 Cypher 示例：
// 找到某用户的二度好友中喜欢 Python 的人
MATCH (me:User {name: "Alice"})-[:FRIEND*2]-(fof:User)
WHERE fof.language = "Python" AND fof <> me
RETURN fof.name
这本质上是在图上做模式匹配——一种比 BFS/DFS 更复杂但表达力更强的图遍历。
Google 的 PageRank：BFS 思想的推广
Larry Page 和 Sergey Brin 在 1998 年提出的 PageRank 算法，本质上是在有向图（网页链接图）上的随机游走（Random Walk）。它可以看作 BFS 的概率版本：
- BFS：从起点出发，确定性地访问所有可达顶点
- PageRank：从任意顶点出发，随机沿着边游走，最终各顶点的"访问频率"就是其重要性
def pagerank(graph: GraphList, damping: float = 0.85, iterations: int = 100):
"""
简化版 PageRank 算法
damping: 阻尼因子（继续沿链接走的概率）
"""
vertices = list(graph.vertices())
n = len(vertices)
rank = {v: 1.0 / n for v in vertices}
for _ in range(iterations):
new_rank = {}
for v in vertices:
# 随机跳转的贡献
new_rank[v] = (1 - damping) / n
# 来自入链的贡献
# 需要知道谁指向 v（反向边）
for u in vertices:
neighbors = graph.get_neighbors(u)
if neighbors:
share = damping * rank[u] / len(neighbors)
for v in neighbors:
new_rank[v] = new_rank.get(v, (1-damping)/n) + share
rank = new_rank
return rank
16.15 图遍历的形式化：来自 Cormen et al. (CLRS) 的定义
《算法导论》（Introduction to Algorithms，Cormen, Leiserson, Rivest, Stein，2009年第三版）第22章给出了 BFS 和 DFS 的标准形式化描述。
BFS 的不变量（Invariant）：
在 BFS 的任何时刻，队列中的顶点按距离排列：如果 u 在 v 前面入队，则 d[u] ≤ d[v]，且队列中相邻元素的距离差最多为 1。
这个不变量的数学表述：设队列为 ⟨v₁, v₂, ..., vₖ⟩，则 d[vₖ] ≤ d[v₁] + 1，且 d[vᵢ] ≤ d[vᵢ₊₁]。
这保证了 BFS 的"一层一层"扩展行为。
DFS 的结构定理：
CLRS 证明了 DFS 产生的时间戳满足：
- 括号定理（如 16.10 节所述）
- 后代定理：在 DFS 森林中，v 是 u 的后代 ⟺ d[u] < d[v] < f[v] < f[u]
- 回边定理：有向图 G 有环 ⟺ G 的 DFS 产生回边
这些定理将 DFS 从"一种搜索算法"提升为"一种分析图结构的通用工具"。
Level 4 · 边界与陷阱
16.16 LeetCode 200：岛屿数量
题目：给定一个 m×n 的二维网格，'1' 表示陆地，'0' 表示水。计算岛屿的数量。岛屿由水平或垂直相邻的陆地连接形成。
分析：这本质上是求网格图中值为 '1' 的连通分量个数。
from collections import deque
def numIslands(grid: list) -> int:
"""
LeetCode 200: Number of Islands
时间 O(m×n)，空间 O(m×n)
"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def bfs(r, c):
"""从 (r,c) 开始 BFS，标记整个岛屿"""
queue = deque([(r, c)])
grid[r][c] = '0' # 标记为已访问
while queue:
row, col = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = row + dr, col + dc
if (0 <= nr < rows and 0 <= nc < cols
and grid[nr][nc] == '1'):
grid[nr][nc] = '0'
queue.append((nr, nc))
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
count += 1
bfs(i, j)
return count
# DFS 版本（更简洁，但大网格可能栈溢出）
def numIslands_dfs(grid: list) -> 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 i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
count += 1
dfs(i, j)
return count
# 测试
grid = [
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
print(numIslands([row[:] for row in grid])) # 3
面试要点：
- 时间复杂度 O(m×n)：每个格子最多访问一次
- 空间复杂度 O(m×n)：最坏情况下整个网格是一个岛屿，BFS 队列/DFS 递归栈可达 m×n
- 直接修改 grid 作为 visited 标记，避免额外空间（但会修改输入）
- 如果不能修改输入，使用独立的 visited 集合
16.17 LeetCode 133：克隆图
题目：给定一个无向连通图中的节点引用，返回该图的深拷贝。每个节点包含一个整数值和一个邻居列表。
分析：这是图遍历 + 哈希映射的经典组合。BFS 或 DFS 遍历原图，对每个节点创建克隆，用字典记录"原节点→克隆节点"的映射。
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def cloneGraph(node: 'Node') -> 'Node':
"""
LeetCode 133: Clone Graph
BFS + HashMap
时间 O(V+E)，空间 O(V)
"""
if not node:
return None
# old_node → new_node 的映射
cloned = {node: Node(node.val)}
queue = deque([node])
while queue:
current = queue.popleft()
for neighbor in current.neighbors:
if neighbor not in cloned:
# 创建克隆节点
cloned[neighbor] = Node(neighbor.val)
queue.append(neighbor)
# 建立克隆节点之间的邻接关系
cloned[current].neighbors.append(cloned[neighbor])
return cloned[node]
# DFS 版本
def cloneGraph_dfs(node: 'Node') -> 'Node':
"""DFS + HashMap"""
if not node:
return None
cloned = {}
def dfs(n):
if n in cloned:
return cloned[n]
clone = Node(n.val)
cloned[n] = clone
for neighbor in n.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)
面试要点：
- 关键是用 HashMap 避免重复克隆和无限循环
- BFS 和 DFS 两种写法都要掌握
- 时间 O(V+E)，空间 O(V)
16.18 LeetCode 207：课程表
题目：有 n 门课程（0 到 n-1），prerequisites[i] = [a, b] 表示学 a 之前必须先学 b。判断是否能完成所有课程（即有向图是否有环）。
分析：将课程建模为有向图的顶点，先修关系为边。问题等价于判断有向图是否有环（有环则无法完成所有课程）。
def canFinish(numCourses: int, prerequisites: list) -> bool:
"""
LeetCode 207: Course Schedule
有向图环检测 —— DFS 三色标记法
时间 O(V+E)，空间 O(V+E)
"""
# 建图
graph = defaultdict(list)
for course, prereq in prerequisites:
graph[prereq].append(course)
# 三色标记
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * numCourses
def has_cycle(node):
color[node] = GRAY
for neighbor in graph[node]:
if color[neighbor] == GRAY:
return True # 发现回边 → 有环
if color[neighbor] == WHITE:
if has_cycle(neighbor):
return True
color[node] = BLACK
return False
for i in range(numCourses):
if color[i] == WHITE:
if has_cycle(i):
return False
return True
# BFS 版本（Kahn 算法 —— 拓扑排序）
def canFinish_bfs(numCourses: int, prerequisites: list) -> bool:
"""BFS 拓扑排序：如果能排完所有节点，则无环"""
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
# 所有入度为 0 的节点入队
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
count = 0
while queue:
node = queue.popleft()
count += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return count == numCourses # 能排完所有课程 → 无环
# 测试
print(canFinish(2, [[1,0]])) # True: 0→1
print(canFinish(2, [[1,0],[0,1]])) # False: 0→1→0 有环
print(canFinish(4, [[1,0],[2,1],[3,2]])) # True: 0→1→2→3
16.19 LeetCode 130：被围绕的区域
题目：给定 m×n 矩阵，包含 'X' 和 'O'。将所有被 'X' 围绕的 'O' 翻转为 'X'。边界上的 'O' 以及与边界 'O' 相连的 'O' 不被翻转。
分析：逆向思维！不是找"被围绕的 O"，而是找"不被围绕的 O"（从边界出发能到达的 O），其余的 O 全部翻转。
def solve(board: list) -> None:
"""
LeetCode 130: Surrounded Regions
从边界 BFS，标记不被围绕的 'O'
时间 O(m×n)，空间 O(m×n)
"""
if not board or not board[0]:
return
rows, cols = len(board), len(board[0])
def bfs(r, c):
"""从边界上的 'O' 开始，标记所有相连的 'O' 为 'S'(safe)"""
queue = deque([(r, c)])
board[r][c] = 'S'
while queue:
row, col = queue.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = row + dr, col + dc
if (0 <= nr < rows and 0 <= nc < cols
and board[nr][nc] == 'O'):
board[nr][nc] = 'S'
queue.append((nr, nc))
# 步骤1：从边界上的 'O' 出发，标记所有安全的 'O'
for i in range(rows):
if board[i][0] == 'O':
bfs(i, 0)
if board[i][cols-1] == 'O':
bfs(i, cols-1)
for j in range(cols):
if board[0][j] == 'O':
bfs(0, j)
if board[rows-1][j] == 'O':
bfs(rows-1, j)
# 步骤2：遍历整个矩阵
# 'O' → 'X' （被围绕的）
# 'S' → 'O' （不被围绕的，恢复）
for i in range(rows):
for j in range(cols):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'S':
board[i][j] = 'O'
# 测试
board = [
['X','X','X','X'],
['X','O','O','X'],
['X','X','O','X'],
['X','O','X','X']
]
solve(board)
for row in board:
print(row)
# ['X','X','X','X']
# ['X','X','X','X']
# ['X','X','X','X']
# ['X','O','X','X'] ← 左下角的 O 与边界相连，不翻转
面试要点：
- 逆向思维是关键：从边界出发找安全区域
- 三步法：标记安全区域 → 翻转不安全的 O → 恢复安全区域
- 时间 O(m×n)，空间 O(m×n)（BFS 队列）
16.20 图遍历面试的通用框架
面试中图的题目变化多端，但底层思路可以归结为以下框架：
步骤1：识别"这是一个图的问题"
信号词：连通、相邻、可达、最短路径、依赖关系、网格、矩阵遍历。
步骤2：建模
- 什么是顶点？什么是边？
- 有向还是无向？有权还是无权？
- 是显式图（给了邻接关系）还是隐式图（需要从规则推导邻居）？
步骤3：选择算法
| 目标 | 算法 |
|---|---|
| 最短路径（无权） | BFS |
| 连通分量/可达性 | BFS 或 DFS |
| 环检测 | DFS（三色标记） |
| 拓扑排序 | DFS 或 BFS（Kahn） |
| 二分图判定 | BFS 染色 |
步骤4：考虑边界情况
- 空图（0 个顶点）
- 断开的图（多个连通分量）
- 自环
- 重边
# 图面试题的通用模板
def graph_problem_template(input_data):
"""
1. 建图
2. 初始化 visited / 其他状态
3. 遍历（可能需要对所有连通分量都遍历）
4. 返回结果
"""
# 建图
graph = defaultdict(list)
# ... 根据输入建图 ...
# BFS/DFS
visited = set()
result = None
for start_node in all_possible_starts:
if start_node not in visited:
# BFS or DFS from start_node
# 更新 result
pass
return result
16.21 本章总结
| 概念 | 核心要点 |
|---|---|
| 邻接矩阵 | O(1) 查边，O(V²) 空间，适合稠密图 |
| 邻接表 | O(V+E) 空间，适合稀疏图，工程默认选择 |
| BFS | 队列，层序遍历，无权图最短路径 |
| DFS | 栈/递归，时间戳，环检测，边分类 |
| 连通分量 | 遍历所有顶点，对未访问顶点启动 BFS/DFS |
| 二分图 | BFS 两色染色，有奇数环则非二分图 |
图是计算机科学中最通用的数据结构——几乎任何关系都可以建模为图。掌握了图的表示和遍历，你就拥有了解决大量实际问题的基础工具。下一章，我们将深入探讨有向图的一个关键应用：拓扑排序。