graph
09. 图
0. 本章先解决什么问题
树表达层级,但现实中很多关系不是单一父子关系:
城市道路
网络连接
任务依赖
社交关系
网页链接
课程先修关系
状态转移
这些都更适合用图。
本章要解决:
- 图的顶点和边是什么?
- 有向图、无向图、带权图有什么区别?
- 邻接矩阵和邻接表如何存图?
- DFS、BFS 分别解决什么?
- 拓扑排序、最短路、连通性是什么?
- 图在系统问题里如何建模?
这张图怎么读
这张图强调图遍历最核心的两个状态:visited 表示已经确认处理过的点,frontier 表示下一批要扩展的边界。BFS 和 DFS 的差异,本质上是 frontier 的数据结构不同:队列一层层扩展,栈/递归沿路径深入。
1. 图的最小模型
图由顶点和边组成。
V = vertices
E = edges
示意:
顶点表示对象,边表示关系。
| 对象 | 顶点 | 边 |
|---|---|---|
| 道路 | 城市 | 道路 |
| 网络 | 设备 | 连接 |
| 任务 | 任务 | 依赖 |
| 社交 | 人 | 关系 |
| 状态机 | 状态 | 转移 |
2. 有向图和无向图
无向图:
A — B
表示关系双向。
有向图:
A -> B
表示关系有方向。
例子:
| 图 | 方向 |
|---|---|
| 朋友关系 | 通常可看作无向 |
| 关注关系 | 有向 |
| 道路 | 可能有向,也可能无向 |
| 任务依赖 | 有向 |
| 网页链接 | 有向 |
方向决定遍历和可达性。
3. 带权图
边可以有权重:
A —5— B
权重可以表示:
- 距离。
- 时间。
- 成本。
- 延迟。
- 容量。
- 风险。
最短路问题就是在带权图上寻找总代价最小的路径。
4. 邻接矩阵
邻接矩阵用二维数组表示边。
matrix[u][v] = 是否有边或边权
优点:
- 查询两个点是否相连 O(1)。
- 实现简单。
缺点:
- 空间 O(V^2)。
- 稀疏图浪费空间。
适合:
- 顶点少。
- 边很密。
- 频繁查询任意两点是否相连。
5. 邻接表
邻接表为每个顶点保存邻居列表。
A: B, C
B: A, C, D
C: A, B, D
D: B, C
空间:
O(V + E)
适合稀疏图。
大多数实际图都更常用邻接表,因为边远少于 V^2。
6. DFS:深度优先搜索
DFS 思路:
从一个点出发
沿一条路走到底
走不动再回退
可以用递归或显式栈。
适合:
- 判断连通性。
- 找路径。
- 检测环。
- 树/图遍历。
- 拓扑排序的部分实现。
- 回溯搜索。
DFS 关键是 visited 集合,避免重复访问和无限循环。
7. BFS:广度优先搜索
BFS 思路:
先访问距离 1 的点
再访问距离 2 的点
一层一层扩展
用队列实现。
适合:
- 无权图最短路径。
- 层序扩展。
- 找最少步数。
- 状态空间搜索。
无权图中,BFS 第一次到达某点时,路径边数就是最短。
机制深挖:BFS 为什么能保证无权最短路
BFS 的关键不变量是:
队列中节点按距离从小到大被处理
从起点开始:
距离 0: 起点
距离 1: 起点的邻居
距离 2: 距离 1 节点的未访问邻居
…
因为每条边的代价都相同,所以第一次到达某个点时,已经是最少边数路径。反例也很重要:如果边有不同权重,BFS 就不再保证总代价最小。
| 图类型 | BFS 是否能求最短 |
|---|---|
| 无权图 | 可以,最少边数 |
| 所有边权相同 | 可以,等价无权 |
| 非负但不同权重 | 不可以,需要考虑累计权重 |
| 有负权 | 更不能直接用 BFS |
所以看到“最短路”三个字,不要立刻写 BFS。先问:边有没有权重?权重是否相同?目标是最少步数还是最小成本?
8. 拓扑排序
拓扑排序用于有向无环图。
表示依赖关系:
A -> B
表示 A 必须在 B 之前。
应用:
- 编译依赖。
- 课程先修。
- 任务调度。
- 构建系统。
如果图里有环:
A -> B -> C -> A
就不存在合法拓扑顺序。
这说明依赖互相等待,系统可能无法推进。
建模反例:边方向画反,答案会完全错
任务依赖里,A -> B 通常表示:
A 必须先完成,B 才能开始
如果你把边画成“B 依赖 A,所以 B -> A”,拓扑排序仍然能跑,但输出语义会反过来。图算法最危险的错误之一就是:算法对了,图建错了。
建模时可以用一句话检查边方向:
沿着边走,时间/因果/依赖是否在向前推进?
常见方向约定:
| 场景 | 边 u -> v 通常表示 |
|---|---|
| 任务依赖 | u 完成后 v 才能做 |
| 网页链接 | u 页面指向 v 页面 |
| 状态机 | u 状态可转移到 v 状态 |
| 调用图 | u 调用 v |
| 资源等待图 | u 正在等待 v |
方向一错,入度、出度、可达性、环的含义都会错。
9. 最短路
最短路根据图类型选择算法思想。
| 图类型 | 常用思路 |
|---|---|
| 无权图 | BFS |
| 非负权图 | 贪心 + 优先队列 |
| 有负权边 | 需要更谨慎的松弛算法 |
最短路核心概念是松弛:
如果经过 u 到 v 更短
就更新 dist[v]
图算法经常和堆、队列、集合组合使用。
10. 连通性和环
连通性问:
两个点能不能互相到达?
环问:
是否存在从某点出发又回到自己的路径?
环在不同场景意义不同:
| 场景 | 环的意义 |
|---|---|
| 任务依赖 | 依赖循环,无法执行 |
| 状态机 | 可能是合法循环 |
| 道路 | 正常 |
| 资源等待 | 可能是死锁 |
不要只说“有环坏”。要看业务语义。
11. 联系实际:把问题建模成图
图最难的常常不是算法,而是建模。
步骤:
- 什么是顶点?
- 什么是边?
- 边有没有方向?
- 边有没有权重?
- 需要求可达、最短、环、连通,还是顺序?
- 图规模多大?
- 边是稀疏还是稠密?
- 图会不会动态变化?
例子:任务调度。
顶点 = 任务
边 = 依赖
A -> B 表示 A 完成后 B 才能开始
问题变成:
- 是否有环?
- 如何给出执行顺序?
- 哪些任务可以并行?
建模卡:别急着套算法,先定义图
很多图问题做不出来,不是因为 BFS/DFS 忘了,而是图建错了。建模时先填这张表:
| 问题 | 选择会影响什么 |
|---|---|
| 顶点是什么 | 决定搜索对象和规模 |
| 边是什么 | 决定关系是否存在 |
| 边有方向吗 | 决定可达性和拓扑排序 |
| 边有权重吗 | 决定能否用 BFS,还是需要最短路算法 |
| 图是稀疏还是稠密 | 决定邻接表还是邻接矩阵 |
| 是否会动态变化 | 决定能不能预处理 |
| 需要找什么 | 可达、最短、环、连通、顺序、割点、匹配等 |
例子:排查任务依赖为什么卡住。
顶点 = 任务
有向边 A -> B = A 完成后 B 才能开始
目标 = 找是否有环,以及哪些任务入度为 0 可以先执行
如果出现:
A -> B -> C -> A
这不是“遍历慢”,而是依赖环导致没有合法推进顺序。建模清楚后,拓扑排序或环检测才有意义。
手推:邻接矩阵和邻接表为什么会改变成本
假设有:
V = 10000 个顶点
E = 30000 条边
邻接矩阵需要记录每一对顶点是否相连:
V * V = 10000 * 10000 = 100000000
也就是 1 亿个格子。即使每格只用 1 bit,也要约 12.5 MB;如果用整数或布尔数组,实际可能更大。它的优势是:
判断 u 和 v 是否有边很快。
邻接表只记录真实存在的边:
V + E ≈ 40000 级别的记录
它的优势是遍历某个点的邻居更自然,尤其适合稀疏图。
选择不是背结论,而是看操作:
| 主要操作 | 更倾向 |
|---|---|
| 频繁问两个点是否直接相连 | 邻接矩阵 |
| 频繁遍历某点邻居 | 邻接表 |
| 图非常稀疏 | 邻接表 |
| 图非常稠密 | 邻接矩阵可能可接受 |
| 顶点动态增删很多 | 邻接表或专门结构更灵活 |
如果用错表示,算法复杂度会被存储结构拖垮。很多图问题不是 BFS/DFS 写错,而是图的表示和操作模式不匹配。
边界条件:带权图不能直接套无权 BFS
BFS 能求最短路的前提是:
每条边成本相同。
如果边有不同权重:
A -> B 权重 100
A -> C 权重 1
C -> B 权重 1
从 A 到 B:
- 按边数最少:A -> B,只走 1 条边
- 按权重最小:A -> C -> B,总成本 2
如果你在带权图上直接用 BFS,会得到“边数最少”,而不是“成本最低”。这类错误很隐蔽,因为算法能跑出结果,但结果的语义错了。
建模时必须先说清:
所谓最短,是边数最少、时间最短、费用最低、风险最低,还是某种综合成本最低?
只要“短”的定义变了,边权和算法选择就要跟着变。
12. 学完本章你能解决什么问题
学完这一章,你应该能解决或开始分析这些问题:
- 图为什么比树更适合表达复杂关系?
- 有向图、无向图、带权图有什么区别?
- 邻接矩阵和邻接表如何选择?
- DFS 和 BFS 的核心差异是什么?
- 为什么 BFS 能求无权图最短路?
- 拓扑排序如何发现依赖顺序和依赖环?
- 最短路问题为什么要看权重类型?
- 如何把真实系统问题建模成图?
图是关系建模的通用工具。很多复杂系统问题,第一步都是把对象和关系画出来。