考频地图
图的选择题 3–4 道,综合题(应用题)也常考:给一个图,写邻接矩阵 / 邻接表,求最小生成树、最短路径、拓扑序列或关键路径。每一种都有固定的“手算表格”,照着模拟器的表格格式写就是标准答案。
| 考点 | 考频 | 常见问法 |
|---|---|---|
| 图的基本概念 | ★★★☆☆ | “n 个顶点保证连通至少需要多少条边” |
| 邻接矩阵 / 邻接表 | ★★★★☆ | “空间复杂度”“求入度的时间” |
| BFS / DFS | ★★★★☆ | “可能的 DFS 序列”“时间复杂度” |
| 最小生成树 | ★★★★★ | “Prim / Kruskal 依次选出的边” |
| 最短路径 | ★★★★★ | “Dijkstra 求得的最短路径顺序” |
| 拓扑排序与关键路径 | ★★★★★ | “关键路径长度”“哪些活动是关键活动” |
图的基本概念
| 概念 | 结论 |
|---|---|
| 边数上限 | 无向图 n(n − 1)/2(完全图),有向图 n(n − 1) |
| 度 | 无向图:所有顶点度数之和 = 2e;有向图:入度之和 = 出度之和 = e |
| 连通 | 无向图 n 个顶点连通至少 n − 1 条边(树);非连通最多 (n − 1)(n − 2)/2 条边 |
| 保证连通 | 无论怎么连都连通,至少需要 (n − 1)(n − 2)/2 + 1 条边 |
| 强连通 | 有向图任意两点互相可达;n 个顶点强连通至少 n 条边(一个环) |
| 生成树 | 连通图的极小连通子图,n 个顶点 n − 1 条边;再加一条边必成环 |
| 简单路径 / 回路 | 顶点不重复的路径;第一个顶点和最后一个相同的路径叫回路 |
存储结构与遍历
| 存储 | 空间 | 找边 (i, j) | 求度 / 出度 | 求入度 | 适合 |
|---|---|---|---|---|---|
| 邻接矩阵 | O(n²) | O(1) | 扫一行 O(n) | 扫一列 O(n) | 稠密图 |
| 邻接表 | O(n + e)(无向图 2e 个边结点) | 扫链表 O(度) | 扫链表 | 要遍历整个表 O(n + e)(或建逆邻接表) | 稀疏图 |
| 十字链表 | O(n + e) | — | 方便 | 方便 | 有向图 |
| 邻接多重表 | O(n + e) | — | 方便 | — | 无向图(每条边只存一次) |
邻接矩阵 A 的 Aᵐ 中元素 [i][j] 表示从 i 到 j 长度为 m 的路径条数。邻接矩阵表示唯一,邻接表不唯一(边的链接顺序可变),所以基于邻接表的遍历序列也不唯一。
| 遍历 | 辅助结构 | 邻接矩阵 | 邻接表 | 用途 |
|---|---|---|---|---|
| BFS | 队列 | O(n²) | O(n + e) | 无权图单源最短路径;层序 |
| DFS | 栈(递归) | O(n²) | O(n + e) | 连通分量、判环、拓扑排序 |
- 对无向图调用一次 BFS/DFS 访问到的是一个连通分量;调用次数 = 连通分量数。
- 判断“可能的 DFS 序列”:每一步访问的顶点必须是当前顶点未访问的邻接点;若没有,回溯到最近的有未访问邻接点的顶点。
最小生成树
带权连通无向图中,边权之和最小的生成树叫最小生成树(MST)。两种贪心算法:
| 算法 | 做法 | 时间复杂度 | 适合 |
|---|---|---|---|
| Prim | 从一个顶点出发,每次选“一端在树内、一端在树外”的最小边,加入新顶点 | O(n²) | 稠密图(与边数无关) |
| Kruskal | 把边按权值从小到大排序,依次选不会形成回路的边(用并查集判断) | O(e log e) | 稀疏图 |
- MST 不一定唯一(有权值相同的边时),但 MST 的总权值唯一。各边权值都不同时 MST 唯一。
- MST 的边数是 n − 1;最小生成树上两点间路径不一定是最短路径。
- Prim 每次加入的是“顶点”,Kruskal 每次加入的是“边”,过程中 Kruskal 的选中边可能暂时不连通。
最短路径
| 算法 | 问题 | 时间 | 负权边 |
|---|---|---|---|
| BFS | 无权图的单源最短路径 | O(n + e) | — |
| Dijkstra | 带权图的单源最短路径 | O(n²) | 不允许 |
| Floyd | 每对顶点之间的最短路径 | O(n³) | 允许负权边,但不允许负权回路 |
Dijkstra:每轮确定一个顶点
- dist[] 初始化为源点到各顶点的直接边权(没有边为 ∞),S = {源点}。
- 在不在 S 中的顶点里选 dist 最小的 u 加入 S(它的最短距离已确定)。
- 用 u 更新其他顶点:若 dist[u] + w(u, v) < dist[v],则更新 dist[v] 和 path[v]。
- 重复 2–3 直到所有顶点加入 S。
为什么不能有负权:Dijkstra 假设“当前最小的 dist 不会再被别的路径缩短”。有负权边时,以后经过负权边的路径可能更短,已确定的结果就错了。
Floyd:依次以每个顶点 k 作为中转点,A[i][j] = min(A[i][j], A[i][k] + A[k][j]),三重循环,k 在最外层。
有向无环图:拓扑排序与关键路径
一、DAG 描述表达式
表达式中相同的子式可以共享一个结点。例(2019 真题):((x + y) × ((x + y) / x)) 的 DAG 最少需要 5 个顶点:x、y、+、/、×(x + y 只出现一次,x 也只出现一次)。
二、拓扑排序(AOV 网)
- 选一个入度为 0 的顶点输出;
- 删除它和它的所有出边(后继入度 −1);
- 重复,直到图空(成功)或剩下的顶点入度都不为 0(有回路)。
时间 O(n + e)(邻接表)。若某步有多个入度为 0 的顶点,拓扑序列就不唯一。也可以用 DFS:每个顶点 DFS 结束时记录,得到的是逆拓扑序列。若邻接矩阵是三角矩阵,则一定存在拓扑序列(反之不一定)。
三、关键路径(AOE 网)
边表示活动、权值表示持续时间、顶点表示事件。从源点到汇点最长的路径叫关键路径,其长度就是完成整个工程的最短时间。
- 关键路径可能不止一条;缩短某个关键活动不一定缩短总工期(可能变成非关键,或别的关键路径仍在)。只有缩短所有关键路径共有的关键活动才一定能缩短工期。
- ve 取 max(要等所有前驱活动都完成),vl 取 min。
- 拓扑排序能用来判断有向图是否有环;无向图判环用 DFS 或并查集。
真题与自测
一、真题问法
问法 1:“用 Dijkstra 求从顶点 1 到其余各顶点的最短路径,依次得到的目标顶点是?”→ 按“加入 S 的顺序”回答。
问法 2:“下列关于关键路径的说法正确的是”→ 记住“缩短关键活动不一定缩短工期”。
问法 3(2021 算法题):“判断无向图是否存在 EL 路径(经过每条边恰好一次):度为奇数的顶点个数为 0 或 2 时存在”→ 遍历邻接矩阵每行统计度数。
问法 4(2023 算法题):“统计有向图中出度大于入度的顶点(邻接矩阵存储)”→ 第 i 行之和是出度,第 i 列之和是入度,O(n²)。
二、折叠自测
1. n 个顶点的有向完全图有几条边?
n(n − 1)。
2. 邻接表存储的有向图,求某顶点入度的时间?
需要遍历所有边结点,O(n + e)。
3. Prim 和 Kruskal 各适合什么图?
Prim O(n²) 适合稠密图;Kruskal O(e log e) 适合稀疏图。
4. Dijkstra 为什么不能处理负权边?
它假设已确定的最短距离不会再被缩短,负权边可能让后面的路径更短,导致已确定结果错误。
5. 拓扑序列唯一的条件?
每一步都恰好只有一个入度为 0 的顶点(此时图中存在一条经过所有顶点的路径)。
6. AOE 网中关键活动的特点?
最早开始时间 e 等于最迟开始时间 l,没有余量,延误一点都会推迟整个工期。
三、考前速览
矩阵 O(n²),邻接表 O(n + e)。
Prim 加点 O(n²),Kruskal 加边 O(e log e)。
Dijkstra 不能负权,Floyd O(n³)。
ve 取 max、vl 取 min,d = 0 为关键。
① 保证连通要 (n−1)(n−2)/2 + 1 条边。
② MST 不唯一但权值唯一。
③ 缩短关键活动不一定缩短工期。