1 / 4概念
Graph Structures
图结构的核心不是“把边存下来”,而是决定哪种查询便宜:查一条边、遍历邻居、扫全部边、合并连通块,四种需求对应四种表示。判断标准是 V/E 比例、更新频率和缓存局部性,不是“邻接表更常用”。
1 概念
1.1 一句话定义
图是顶点集合 V 与边集合 E 的结构;存储表示决定空间和操作代价。邻接矩阵用 V×V 表存边,邻接表为每个点挂邻居列表,边列表只存边,CSR 用偏移数组压缩邻接表;并查集(DSU)维护不相交集合,支持近似 O(1) 的合并与查询。
1.2 它解决什么问题
- 稀疏图存储:E 远小于 V² 时,矩阵会浪费大量空间,邻接表/CSR 只存实际边。
- 快速邻居遍历:BFS/DFS/最短路都要反复遍历邻居,表示必须让这一步便宜。
- 全边扫描:Kruskal、Bellman-Ford 需要按边遍历/排序,边列表更直接。
- 动态连通性:并查集把“合并两个集合、判断是否同集合”做到近似常数。
- 依赖排序:拓扑排序把 DAG 变成线性执行顺序,发现循环依赖。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| BFS/DFS、Dijkstra、MST、A* | Graph Algorithms |
| 数组、链表、哈希表 | Linear Structures |
| 树、堆、B+ 树 | Trees & Heaps |
| 复杂度分析与摊还 | Complexity Analysis |
| 强连通分量、2-SAT 等进阶图论 | 进阶图论页面(待补) |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 稀疏 / 稠密 | E 接近 V / E 接近 V² | 稠密不绝对等于矩阵 |
| 度 / 入度 / 出度 | 相邻边数 / 指向该点 / 从该点出发 | 无向图只有度 |
| 邻接矩阵 | V×V 的边权表 | 无向图对称,有向图不一定 |
| 邻接表 | 每个点一个邻居容器 | 无向边通常存两份 |
| 边列表 | 只存 (u, v, w) | 不适合查邻居 |
| CSR | 偏移数组 + 邻居数组 | 行压缩,不是列压缩 |
| DSU | 并查集,维护不相交集合 | 不是图的完整表示 |
| 路径压缩 | 查找时把节点直接挂到根 | 不改变集合划分 |
| 按秩/按大小合并 | 矮树挂到高树下 | 与路径压缩配合近似 O(α) |
| 拓扑序 | 所有边从前往后的线性序 | 只对 DAG 存在 |
2 机制
2.1 心智模型
图表示是在四种操作之间做取舍:查边、遍历邻居、扫全部边、合并集合。矩阵把“查边”做到 O(1),代价是 O(V²) 空间;邻接表把“遍历邻居”做到 O(deg),代价是查边要扫;边列表把“扫全部边”做到 O(E),代价是查邻居;CSR 把邻接表压成连续数组,用不可交换缓存;DSU 放弃边,只维护集合关系。
2.2 机制拆解
- 邻接矩阵:
matrix[u][v] = w,无向图对称写两次;不存在的边用INF或单独布尔表,不能用 0 当“无边”(0 权边合法)。 - 邻接表:
adj[u]是动态数组/链表/哈希集合;无向边在两端各存一次;平行边会重复出现,需要去重或计数。 - 边列表:
edges = [(u, v, w)];排序后适合 Kruskal,全部扫描适合 Bellman-Ford。 - CSR:
offset[i]指向第 i 个点的邻居在adj中的起点,offset[i+1]是终点;构建时先数度、再前缀和、再填充。适合静态大图,插入边需要重建。 - 拓扑排序:Kahn 维护入度 0 队列;DFS 用完成时间逆序。仅 DAG;Kahn 结束时若输出少于 V,说明有环。
- 并查集:
parent[x]指向父节点,find带路径压缩,union按秩/大小合并。支持合并与同集合判断,不支持删除、不支持有向可达性。
2.3 完整枚举
| 表示 | 空间 | 查单边 | 遍历邻居 | 加边 | 删边 | 扫全部边 | 缓存 | 适用 |
|---|---|---|---|---|---|---|---|---|
| 邻接矩阵 | O(V²) | O(1) | O(V) | O(1) | O(1) | O(V²) | 好(连续) | 稠密、小图、频繁查边 |
| 邻接表 | O(V + E) | O(deg(u)) | O(deg(u)) | O(1) | O(deg(u)) | O(V + E) | 一般(指针/分配) | 稀疏、动态图 |
| 边列表 | O(E) | O(E) | O(E) | O(1) | O(E) | O(E) | 好 | Kruskal、Bellman-Ford |
| CSR | O(V + E) | O(log deg) 或 O(deg) | O(deg) | 需重建 | 需重建 | O(V + E) | 很好(连续) | 静态大图、重复遍历 |
| DSU | O(V) | 不适用 | 不适用 | 近似 O(α) 合并 | 不支持 | 不适用 | 好 | 连通性、Kruskal、无向环检测 |
| 拓扑排序 | O(V) 额外 | 不适用 | 不适用 | 不适用 | 不适用 | O(V + E) | 好 | DAG 依赖顺序 |
补充:无向图的邻接表/CSR 通常存 2E 条有向边;有向图只存 E 条。带权图在邻居项里加 weight;哈希标签的图需要先做 label → index 映射。
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| 矩阵空间 | V² 个单元 | V=10⁵ 时 10¹⁰ 个单元,不可行 |
| 邻接表空间 | V + 2E(无向) | 指针/对象开销可能数倍于数据 |
| CSR 空间 | (V+1) + E 个整数 | 无向图 2E;权重另存 |
| 并查集 find/union | O(α(V)) | α 增长极慢,实际近常数 |
| 拓扑排序 | O(V + E) | 每个点/边各处理一次 |
| 边列表排序 | O(E log E) | Kruskal 的瓶颈 |
3 实践
3.1 最小示例
# 构建 CSR:无向图把 (u,v) 和 (v,u) 都加入;有向图只加一次。
BUILD_CSR(V, edges):
deg[*] = 0
for (u, v) in edges: deg[u] += 1
offset[0] = 0
for i in 0..V-1: offset[i+1] = offset[i] + deg[i]
cursor = COPY(offset)
adj = ARRAY(size = offset[V])
for (u, v) in edges:
adj[cursor[u]] = v; cursor[u] += 1
return offset, adj
# Kahn 拓扑排序:输出少于 V 说明有环。
TOPOSORT(V, adj):
indeg[*] = 0
for u in 0..V-1:
for v in adj[u]: indeg[v] += 1
q = QUEUE([u for u in 0..V-1 if indeg[u] == 0])
order = []
while q not empty:
u = q.pop_front(); order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0: q.push_back(v)
return order if len(order) == V else CYCLE
# 并查集:路径压缩 + 按秩合并。
FIND(x):
if parent[x] != x: parent[x] = FIND(parent[x])
return parent[x]
UNION(a, b):
ra = FIND(a); rb = FIND(b)
if ra == rb: return false # 已同集合,加边会成环
if rank[ra] < rank[rb]: SWAP(ra, rb)
parent[rb] = ra
if rank[ra] == rank[rb]: rank[ra] += 1
return true
3.2 常用操作与参数
| 操作 | 典型实现 | 说明 |
|---|---|---|
| 建图 | 矩阵 / 邻接表 / CSR | 先看 E 与 V² |
| 查单边 | matrix[u][v] | 邻接表要扫 adj[u] |
| 遍历邻居 | for v in adj[u] | CSR 顺序访问更缓存友好 |
| 全边扫描 | for (u,v,w) in edges | Kruskal/Bellman-Ford |
| 求连通分量 | BFS/DFS 或 DSU | 无向图两者都可 |
| 判断无向环 | DSU 或 DFS | DSU 合并失败即成环 |
| 拓扑排序 | Kahn / DFS | 只对 DAG |
| 压缩大图 | CSR | 静态图,构建一次多次遍历 |
3.3 标准流程
- 明确图类型:有向/无向、带权/无权、是否有平行边/自环。
- 估算 V 和 E:E 远小于 V² 用稀疏表示,接近 V² 用矩阵。
- 明确操作组合:查单边、遍历邻居、扫全部边、动态加删边。
- 选表示;静态大图优先 CSR,动态图优先邻接表,稠密小图优先矩阵。
- 处理边界并用不变量测试:0/1 起点、
INF哨兵、平行边/自环、offset单调、DSU 根唯一、拓扑序方向。
3.4 与相邻技术的组合
- 图算法:表示决定 BFS/DFS/Dijkstra 的常数;CSR 适合静态图上的重复遍历。
- Kruskal:边列表 + 排序 + 并查集,三者组合成一个算法。
- Bellman-Ford:边列表直接扫全部边,不需要邻居遍历。
- 强连通分量:需要反向图;邻接表和 CSR 都要能快速构建转置。
3.5 选型维度
| 维度 | 取值 | 影响 |
|---|---|---|
| 图密度 | 稀疏 / 稠密 | 邻接表/CSR vs 矩阵 |
| 更新 | 静态 / 动态 | CSR vs 邻接表 |
| 主要操作 | 查边 / 遍历邻居 / 扫全边 | 矩阵 / 表 / 边列表 |
| 内存 | 紧张 / 充足 | 矩阵可能直接不可行 |
| 缓存 | 敏感 / 不敏感 | CSR 连续访问占优 |
| 连通性查询 | 频繁 / 少量 | DSU vs BFS/DFS |
3.6 决策规则
- E ≪ V²:邻接表或 CSR,不要用矩阵。
- E ≈ V² 且 V 不大:矩阵,查边 O(1) 且实现简单。
- 图静态、需要反复 BFS/DFS:CSR。
- 图频繁加边/删边、需要遍历邻居:邻接表。
- 只需要全边扫描/排序:边列表。
- 只需要连通性/合并:DSU,不要建完整图。
- 需要拓扑序:先确认 DAG;Kahn 比 DFS 更容易报告环。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 邻接矩阵 | 查边 O(1)、实现简单 | O(V²) 空间、邻居遍历 O(V) | 稠密小图 |
| 邻接表 | 空间 O(V+E)、动态 | 查边 O(deg)、指针开销 | 稀疏动态图 |
| 边列表 | 全边扫描/排序直接 | 查邻居 O(E) | Kruskal、Bellman-Ford |
| CSR | 连续、缓存友好、省指针 | 不可变、插入需重建 | 静态大图 |
| DSU | 合并/查询近似 O(1) | 不支持删除/有向可达 | 连通性、Kruskal |
| 拓扑排序 | 线性、能发现环 | 只对 DAG | 依赖解析 |
3.8 何时不该用
- 稀疏图用矩阵:空间直接爆,邻居遍历也慢。
- 动态图用 CSR:每次加边重建,代价高于收益。
- 有向图用 DSU 判环:DSU 只维护无向连通性,方向信息丢失。
- 需要删除边却用 DSU:不支持拆分,只能重建。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 建图时内存爆 | 用了 O(V²) 矩阵存稀疏图 | 改邻接表/CSR |
| 邻居里出现重复边 | 平行边未去重 | 建图时去重或计数 |
| CSR 加边后遍历错乱 | 静态结构被原地修改 | 重建 CSR 或改邻接表 |
| 拓扑排序输出少于 V | 图中有环 | 返回剩余点定位环 |
| DSU 在有向图上判环错误 | DSU 丢失方向 | 用 DFS 颜色/SCC |
| DSU 越来越慢 | 没有路径压缩/按秩合并 | 两者都加上 |
| 权重 0 的边被当成不存在 | 用 0 当“无边”哨兵 | 用 INF/布尔表 |
| 下标越界/错位 | 0/1 起点混用 | 统一起点并封装转换 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 所有图都用矩阵 | 稀疏图内存爆炸 | 先算 E/V² |
| 用 DSU 做有向可达性 | 结果错误 | DFS/BFS/SCC |
| CSR 上频繁插边 | 每次 O(V+E) 重建 | 邻接表或动态 CSR |
| 用顶点标签直接做数组下标 | 标签稀疏时浪费 | label → index 映射 |
4.3 可观测信号
建图耗时与内存、offset 是否单调、平均/最大度、邻居遍历耗时、DSU 的 find 路径长度、拓扑排序剩余点数、CSR 重建次数。大图还要看缓存 miss 和页错误。
4.4 安全 / 性能 / 一致性边界
- 内存:矩阵的 V² 是硬上限;先估算再选表示,不能等 OOM 再改。
- 正确性:有向图和无向图的环检测语义不同;DSU 不能替代有向环检测。
- 一致性:CSR 是不可变视图,任何加删边都要重建;不要边遍历边改。
- 性能:CSR 的优势来自连续访问;如果算法本身随机跳转,收益会消失。