06 图
图 = 多对多的关系：地图导航、社交网络、编译器依赖分析、任务调度全靠它。408 图论四大件：存储、遍历、最短路/最小生成树、拓扑排序/关键路径。本章算法名字多，但骨架只有两句：DFS 用栈（递归），BFS 用队列——其余算法都是在这两个骨架上加策略。
一、图的基本概念（选择题高发区）
- 有向图/无向图：边有无方向；有向边 <u,v> 有序，无向边 (u,v) 无序
- 完全图：无向完全图边数 n(n−1)/2；有向完全图 n(n−1)（每个方向一条）
- 顶点的度：无向图 = 关联边数；有向图 = 入度 + 出度
- 握手定理：所有顶点度数之和 = 2 × 边数（每条边贡献两个度）——度数推算的万能钥匙
- 连通（无向：任意两顶点有路径）/ 强连通（有向：双向都有路径）
- 生成树：连通图含全部 n 个顶点的极小连通子图，n−1 条边
- 子图、极大连通子图（连通分量）、极小连通子图（生成树）——"极大"vs"极小"别混：分量求多（极大），生成树求少（极小）
二、存储结构：四选一
| 结构 | 空间 | 适合 | 拿邻接点 |
|---|---|---|---|
| 邻接矩阵 | O(n²)（对称矩阵可压缩，见 栈与队列） | 稠密图、需要 O(1) 判边 | O(n) 扫一行 |
| 邻接表 | O(n + e) | 稀疏图 | 出边快、入边慢 |
| 十字链表 | O(n + e) | 有向图（出边入边都快） | 快 |
| 邻接多重表 | O(n + e) | 无向图（每条边只存一份） | 快 |
⚠️ 高频陷阱：同一个图，邻接表不唯一（邻接点顺序任意）；BFS/DFS 序列也因此不唯一；邻接矩阵唯一。矩阵的行和 = 该点出度，列和 = 入度。
三、遍历：BFS 与 DFS
BFS 广度优先（队列）
1. 起点入队并标记
2. 出队访问，未标记的邻接点全部入队并标记
3. 队空为止
- 按"层次"扩散：同一批入队的顶点距起点等远
- 无权图单源最短路：BFS 天然就是（首次到达 = 最短边数）——这就是 BFS 最重要的隐藏身份
- 复杂度：邻接表 O(n+e)，邻接矩阵 O(n²)；辅助空间 O(n)（队列 + 标记数组）
DFS 深度优先（栈/递归）
1. 访问起点，标记
2. 沿未访问邻接点一路扎下去（递归）
3. 走投无路回退一格，换下一个分支
- 邻接表 O(n+e)、邻接矩阵 O(n²)
- 应用：判连通、找环、拓扑排序、求生成树（DFS 树的回边是关键：有向图判环 = 遇到"正在访问中"的结点）
⚠️ 408 常考：给邻接表/矩阵，手写 BFS/DFS 序列。邻接表要按"题目给定的邻接点顺序"走，别自己排序。
四、最小生成树（MST）：贪心两兄弟
带权连通图里，边权和最小的生成树。
| 算法 | 思想 | 适合 | 复杂度 |
|---|---|---|---|
| Prim | 从点出发：每次把"离已建部分最近的一个点"拉进来 | 稠密图（边多） | O(n²)（邻接矩阵）；堆优化 O(e log n) |
| Kruskal | 从边出发：边按权排序，逐条试放，不构成环就收 | 稀疏图（边少） | O(e log e)（并查集判环） |
💡 手算例题（给 5 点 7 边）：按 Kruskal 排序后依次收边，遇到"两端已在同一棵树"的直接跳过——判环用并查集（find 父亲相同就跳过，不同就 union）。Prim 则从指定点开始，每轮在"横跨已选点集与未选点集"的边里挑最小。
⚠️ 两者都是贪心，但 MST 整体最优（贪心选择性质成立）；MST 不一定唯一（等权边时），但权值和唯一。
五、最短路径：Dijkstra 与 Floyd
Dijkstra 单源最短路（一个起点到全部）
贪心 + 不许有负权边：
1. dist[起点]=0，其余 ∞；每轮选未定结点中 dist 最小的 u，标记"已定"
2. 用 u 松弛所有邻居：dist[v] = min(dist[v], dist[u] + w(u,v))
3. 重复 n 轮
手算例题：v1 起点，边 v1→v2=3, v1→v3=5, v2→v3=1, v2→v4=6, v3→v4=2：
- 第 1 轮：定 v1(0)，松弛 → dist = [_, 3, 5, ∞]
- 第 2 轮：最小 dist 是 v2=3，定 v2，松弛 v3: min(5, 3+1)=4，v4: 3+6=9 → [_, 3, 4, 9]
- 第 3 轮：定 v3=4，松弛 v4: min(9, 4+2)=6 → [_, 3, 4, 6]
- 第 4 轮：定 v4=6 ✅ 最终 v1 到 v4 最短 = 6（路径 v1→v2→v3→v4）
⚠️ 负权边会让 Dijkstra 错（已定点的 dist 可能被后续路径推翻）——负权用 Bellman-Ford（O(ne)）或 SPFA。OSPF 路由协议（网络层）用的正是 Dijkstra。
Floyd 多对多（所有点对）
动态规划：d[i][j] = min(d[i][j], d[i][k] + d[k][j])，k 从 1 到 n 三重循环——O(n³)，代码五行，负权边也可（但不能有负权环）。适合稠密图全源最短路。
六、拓扑排序与关键路径：有向无环图（DAG）
拓扑排序（AOV 网：顶点 = 活动）
1. 找一个入度为 0 的顶点，输出
2. 删除它及其所有出边
3. 重复；若中途找不到入度 0 点 → 有环，排序失败
- 实现：入度数组 + 队列（其实就是 BFS 的变体）；也可用 DFS（按完成时间逆序）
- 拓扑序列不唯一（并列的零入度点顺序随意）；能拓扑排序 ⟺ 有向无环
- 应用：编译依赖（make/CMake）、课程先修关系
关键路径（AOE 网：边 = 活动，顶点 = 事件）
从源点到汇点的最长路径——决定整个工程的最短完工时间；关键路径上的活动不能拖延。
四个量（408 大题套路）：
| 量 | 含义 | 算法 |
|---|---|---|
| 事件最早发生 ve(j) | 顶点 j 最早何时就绪 | 拓扑序推进：ve = max(前驱 ve + 边权) |
| 事件最迟 vl(i) | 顶点 i 最晚何时完成 | 逆拓扑序推进：vl = min(后继 vl − 边权) |
| 活动最早开始 e(i) | 边 <i,j> 的最早开始 | = ve(i) |
| 活动最迟开始 l(i) | 边 <i,j> 的最迟开始 | = vl(j) − w(i,j) |
关键活动：e(i) == l(i)（时间余量 = 0）。缩短关键活动工期才能缩短工期；但关键路径缩短后可能被次关键路径顶替——大题考点。
七、图的应用一张表（面试串讲用）
| 问题 | 算法 | 骨架 |
|---|---|---|
| 无权最短路 | BFS | 队列 |
| 单源带权最短路 | Dijkstra | 贪心 + 优先队列 |
| 全源最短路 | Floyd | 动态规划 |
| 连通最小代价 | Prim / Kruskal | 贪心 |
| 任务依赖 | 拓扑排序 | BFS（入度队列） |
| 工期分析 | 关键路径 | 拓扑 + 逆拓扑 |
| 判环 | DFS 回边 / 并查集 / 拓扑失败 | 栈 |
八、盲点自测
- n 顶点有向完全图几条边？（n(n−1)）
- 度数之和与边数的关系？（和 = 2e）
- BFS 为什么能求无权最短路？（按层扩散，首次到达即最少边数）
- Dijkstra 遇负权为什么错？（"已定"点可能被更短路径推翻）
- Prim 和 Kruskal 各适合什么图？（稠密/稀疏）
- 拓扑排序判环的依据？（中途没有入度 0 的点）
- 关键路径是最长路径还是最短路径？（最长；但它决定工程最短完工时间）
- 邻接表为什么 BFS/DFS 序列不唯一？（邻接点顺序不唯一）
九、动手玩
# 拓扑排序：入度数组 + 队列（背下来就是模板）
from collections import deque
def topo_sort(n, edges):
adj = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
q = deque(i for i in range(n) if indeg[i] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else None # None = 有环
print(topo_sort(4, [(0,1),(0,2),(1,3),(2,3)])) # [0, 1, 2, 3]
print(topo_sort(3, [(0,1),(1,2),(2,0)])) # None（有环）
💬 评论