4.1 图的表示与应用
"数据获取往往比算法本身更重要。" — Skiena War Story
学习目标
- 掌握图的两种基本表示：邻接矩阵与邻接表
- 理解不同表示的时间和空间复杂度
- 选择合适的图表示
- 认识数据获取的挑战
一个关于数据获取的故事
Skiena 讲过一个真实案例：
某公司要分析社交网络。工程师花了两周优化 BFS 算法，把性能提升了 30%。
然后数据团队说："数据源 API 有速率限制，爬取完整数据需要三个月。"
真正的问题是数据获取，不是算法优化。
这个故事告诉我们：在图算法中，获取图本身往往比优化算法更关键。
图的基本概念
图的定义
图 G = (V, E) 由顶点集 V 和边集 E 组成。
- 无向图：边没有方向
- 有向图：边有方向
- 加权图：边有权重
常见图类型
| 类型 | 特性 | 示例 |
|---|---|---|
| 无向图 | 边无方向 | 社交网络（好友关系） |
| 有向图 | 边有方向 | 网页链接、关注关系 |
| 加权图 | 边有权重 | 道路网络、航班网络 |
| 稀疏图 | E << V² | 大多数现实图 |
| 稠密图 | E ≈ V² | 完全图 |
邻接矩阵
定义
用 V × V 矩阵 A 表示图：
- A[i][j] = 1（或权重）表示有边 i → j
- A[i][j] = 0（或 ∞）表示无边
示例
图结构：
0 → 1 → 2
↑ ↓
└───┘
邻接矩阵：
0 1 2
0 [ 0 1 0 ]
1 [ 0 0 1 ]
2 [ 1 0 0 ]复杂度
| 操作 | 复杂度 |
|---|---|
| 空间 | O(V²) |
| 判断边是否存在 | O(1) |
| 遍历邻居 | O(V) |
| 添加边 | O(1) |
适用场景
- 稠密图：E ≈ V²
- 频繁判断边是否存在
- 图规模较小
邻接表
定义
每个顶点维护一个邻居列表。
示例
图结构：
0 → 1 → 2
↑ ↓
└───┘
邻接表：
0: [1]
1: [2, 0]
2: [0]复杂度
| 操作 | 复杂度 |
|---|---|
| 空间 | O(V + E) |
| 判断边是否存在 | O(degree(v)) |
| 遍历邻居 | O(degree(v)) |
| 添加边 | O(1) |
适用场景
- 稀疏图：E << V²
- 频繁遍历邻居
- 大规模图
表示选择
| 因素 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 图密度 | 稠密 | 稀疏 |
| 内存 | O(V²) | O(V+E) |
| 边查询 | O(1) | O(degree) |
| 邻居遍历 | O(V) | O(degree) |
| 实现 | 简单 | 稍复杂 |
经验法则：默认选邻接表，除非明确需要 O(1) 边查询。
Python 实现
邻接矩阵
python
class GraphMatrix:
def __init__(self, n):
self.n = n
self.matrix = [[0] * n for _ in range(n)]
def add_edge(self, u, v, weight=1):
self.matrix[u][v] = weight
def has_edge(self, u, v):
return self.matrix[u][v] != 0
def neighbors(self, u):
return [v for v in range(self.n) if self.matrix[u][v] != 0]邻接表
python
from collections import defaultdict
class GraphList:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v, weight=1):
self.graph[u].append((v, weight))
def neighbors(self, u):
return self.graph[u]
def vertices(self):
return list(self.graph.keys())LLM 融合点
任务：让 LLM 选择表示
给 LLM 一个图应用场景，让它选择表示方法。
场景：分析 Twitter 关注网络
- 用户数：3 亿
- 关注关系：约 100 亿
- 需要频繁查询"A 关注 B 吗"
- 需要遍历用户的关注列表
问题：
1. 选择邻接矩阵还是邻接表？
2. 理由是什么？
3. 如果需要 O(1) 边查询，如何优化？判断 LLM 回答是否正确：
- 是否考虑了稀疏性（3 亿用户，100 亿边 → 稀疏图）
- 是否权衡了边查询 vs 邻居遍历
- 是否提出了解决方案（如布隆过滤器辅助）
小结
两种表示：
- 邻接矩阵：O(V²) 空间，O(1) 边查询
- 邻接表：O(V+E) 空间，O(degree) 邻居遍历
选择原则：
- 稀疏图 → 邻接表
- 稠密图 → 邻接矩阵
- 频繁边查询 → 邻接矩阵或辅助结构
现实挑战：
- 数据获取往往比算法优化更关键
- 图数据可能分散在多个数据源
- API 速率限制是常见瓶颈
参考文献
- Skiena, The Algorithm Design Manual, 3rd ed., Chapter 5
- CLRS, Introduction to Algorithms, 4th ed., Chapter 22