考研 408 · 图核心知识点
考研 408 · 图核心知识点
图是 408 大题最爱：存储 → 遍历 → 生成树 → 最短路 → 拓扑/关键路径。
1. 图的存储
邻接矩阵
1 2 3 4
1 [ 0 1 1 0 ]
2 [ 1 0 1 1 ]
3 [ 1 1 0 1 ]
4 [ 0 1 1 0 ]无向图对称；有向图按出边填写。判断两点是否相邻 O(1)，求度方便；但空间 O(n²)。
邻接表
1 → 2 → 3
2 → 1 → 3 → 4
3 → 1 → 2 → 4
4 → 2 → 3空间 O(n+e)，适合稀疏图；求某点出度方便，判断相邻需扫描。
| 存储 | 空间 | 判断相邻 | 求所有邻点 |
|---|---|---|---|
| 邻接矩阵 | O(n²) | O(1) | O(n) |
| 邻接表 | O(n+e) | O(degree) | O(degree) |
2. 遍历
DFS（深度优先，用栈/递归）
访问顶点 → 递归访问第一个未访问邻点 → 回溯BFS（广度优先，用队列）
访问顶点 → 邻点全部入队 → 逐个出队重复复杂度：邻接表 O(n+e)，邻接矩阵 O(n²)。
BFS 还能求无权图最短路径（边数）、判断连通分量数。
3. 最小生成树 MST
Prim（加点）
从一个顶点出发，每次选择"连接已选集合与未选集合的最短边"加入集合，直到覆盖全部顶点。
复杂度：邻接矩阵 O(n²)；适合稠密图。Kruskal（加边）
边按权排序，从小到大选边，用并查集避免成环，选 n−1 条为止。
复杂度：O(e·log e)；适合稀疏图。示例
1 --2-- 2
| \ |
2 4 3
| \ |
3 --1-- 4
按 Kruskal：先取 3-4(1)、1-2(2)、1-3(2)（跳过 2-4(3)） ⇒ MST 总权 54. 最短路径
Dijkstra（单源，非负权）
维护 dist[]，每次取未确定顶点中 dist 最小者，松弛其邻边。
复杂度：邻接矩阵 O(n²)；堆优化 O((n+e)log n)。
不能处理负权边。Floyd（多源）
三重循环：d[i][j] = min(d[i][j], d[i][k] + d[k][j])
复杂度 O(n³)；可处理负权（无负环）。示例（Dijkstra 从 1 出发）
2
1 ───── 3
| 1 1 |
2 ───── 4
3
dist: 1→1=0, 1→2=1, 1→3=2, 1→4=3（经 3）5. 拓扑排序（AOV 网）
无环有向图，顶点表示活动。
反复：选入度为 0 的顶点输出，删除其出边，直到全部输出。
若剩余顶点仍有入度 ⇒ 存在环。
复杂度：邻接表 O(n+e)。示例
课程依赖：A→C, B→C, C→D
拓扑序之一：A B C D（不唯一）6. 关键路径（AOE 网）
顶点 = 事件，边 = 活动（带权=耗时）
ve(最早发生) 正向取 max；vl(最迟发生) 逆向取 min
活动最早 e = ve(弧尾)；活动最迟 l = vl(弧头) − 权
e == l 的活动为关键活动，串联成关键路径
关键路径长度 = 工程最短工期示例
v1 ─2─▶ v2 ─3─▶ v4
\ ▲
4 ────────▶ 3
ve: v1=0, v2=2, v4=5, v3=4
vl: v1=0, v2=2, v4=5, v3=2（逆向）
关键活动：v1→v2(2), v2→v4(3)，关键路径长 57. 常考题型
- 画邻接矩阵/邻接表；
- 给图写 DFS/BFS 序列；
- Prim/Kruskal 过程与总权；
- Dijkstra/Floyd 逐步表；
- 拓扑排序与环检测；
- 求 ve/vl/e/l 与关键路径；
- 判断有向图强连通、无向图连通分量。
8. 易错点
- Dijkstra 不适用负权，Floyd 可；
- MST 不含权值相等的唯一性讨论（可能不唯一）；
- 拓扑排序不唯一；
- 关键路径可能不止一条；
- BFS 求最短路只对无权图。