大纲对照
- 一图的基本概念→ 01
有向无环图描述表达式(真题曾出现,建议会做) · Bellman-Ford 等其他最短路径算法。
图的基本概念
| 概念 | 要点 |
|---|---|
| 完全图 | 无向:任意两点都有边,n(n−1)/2 条;有向:任意两点都有两条方向相反的弧,n(n−1) 条 |
| 度 | 无向图 Σ度 = 2e;有向图 Σ入度 = Σ出度 = e |
| 连通 / 连通分量 | 无向图任意两点有路径 = 连通;极大连通子图 = 连通分量 |
| 强连通 / 强连通分量 | 有向图任意两点互相可达 |
| 生成树 | 连通图的极小连通子图:含全部 n 个顶点、n − 1 条边;多一条边就有环,少一条就不连通 |
| 简单路径 / 回路 | 顶点不重复的路径叫简单路径;首尾相同叫回路(环) |
① 简单无向图有 28 条边,至少有多少个顶点?② 8 个顶点的无向图,要保证无论边怎么连都是连通图,至少需要多少条边?
② 最“坏”的连法:7 个顶点连成完全图(21 条边),第 8 个孤立;再加 1 条就必然连通 → 22 条。
图的存储
邻接表:绿色是顶点表,后面挂的是边结点(存邻接点下标)。6 条边在无向图的邻接表中出现 12 次(每条边存两遍)。
| 对比 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | O(n²) | 无向 O(n + 2e),有向 O(n + e) |
| 判断 (i, j) 是否有边 | O(1) | O(度) |
| 求顶点的度 | 扫一行(有向图入度扫一列) | 出度扫自己的链;入度要扫全部链 |
| 表示唯一吗 | 唯一 | 不唯一(链中顺序可变) |
| 适合 | 稠密图 | 稀疏图 |
十字链表与邻接多重表
- 十字链表:有向图专用。每条弧一个结点,同时挂在“弧尾的出边链”和“弧头的入边链”上 → 出度、入度都好求。
- 邻接多重表:无向图专用。每条边只用一个结点(邻接表中每条边存两次),同时挂在两个端点的链上 → 删边方便。
- 记法:“十字”有方向(有向图),“多重”是一边多用(无向图)。
图的遍历:BFS 与 DFS
visited[] 数组避免重复访问。BFS:V0 V1 V3 V2 V4(下方是队列变化);DFS:V0 V1 V2 V3 V4——从 V2 先走到 V3,V3 无路可走退回 V2,再走 V4。
| BFS | DFS | |
|---|---|---|
| 辅助结构 | 队列 | 栈(递归) |
| 时间(邻接矩阵 / 邻接表) | O(n²) / O(n + e) | |
| 空间 | O(n) | |
| 特别用途 | 无权图单源最短路径;生成的 BFS 树高度最小 | 判断有向图是否有环(存在回边);拓扑排序(逆后序) |
- 给定邻接矩阵,遍历序列唯一;给定的只是“图”或邻接表顺序不定时,遍历序列不唯一——选择题常问“下列哪个不可能是 DFS 序列”。
- 判断不可能的 DFS 序列:每访问一个新顶点,它必须和“当前递归栈里最上面那个还有未访问邻居的顶点”相邻。
最小(代价)生成树
| Prim | Kruskal | |
|---|---|---|
| 每一步 | 加入离当前树最近的顶点 | 加入最短的、不成环的边(并查集判环) |
| 时间 | O(n²),与边数无关 | O(e log e),主要花在排序 |
| 适合 | 稠密图 | 稀疏图 |
边:A–B 4,A–C 1,B–C 2,B–D 5,C–D 8,C–E 10,D–E 2,D–F 6,E–F 3。
Prim(从 A 开始):A–C 1 → C–B 2 → B–D 5 → D–E 2 → E–F 3,权和同为 13,但加边顺序不同——题目常问“第几条加入的边是哪条”。
- MST 不一定唯一;所有边权都不相同时唯一。但 MST 的总权值一定唯一。
- MST 中两点间的路径不一定是这两点的最短路径。
- 最小权的边一定在某棵 MST 中;最大权的边不一定不在(如果它是桥就必须在)。
最短路径:Dijkstra 与 Floyd
有向边:V0→V1 10,V0→V3 30,V0→V4 100,V1→V2 50,V2→V4 10,V3→V2 20,V3→V4 60。求 V0 到其余各点的最短路径。
| 轮次 | V1 | V2 | V3 | V4 | 选中 |
|---|---|---|---|---|---|
| 初始 | 10 | ∞ | 30 | 100 | V1 |
| 2 | — | 60(经 V1) | 30 | 100 | V3 |
| 3 | — | 50(经 V3) | — | 90(经 V3) | V2 |
| 4 | — | — | — | 60(经 V2) | V4 |
V2 的距离先被更新成 60(经 V1),后来发现经 V3 只要 50,又被改小——这就是“松弛”。
| 算法 | 问题 | 时间 | 负权边 |
|---|---|---|---|
| BFS | 无权图单源 | O(n + e) | — |
| Dijkstra | 单源 | O(n²) | 不能有 |
| Floyd | 所有顶点对 | O(n³) | 可以有负权边,但不能有负权回路 |
- Dijkstra 一旦把顶点“定下来”就不再修改,所以负权边会让它出错。
- Dijkstra 和 Prim 很像,区别:Prim 比的是“到树的距离”(单条边权),Dijkstra 比的是“到起点的距离”(路径总长)。
Bellman-Ford、SPFA
能处理负权边、检测负权回路的单源最短路径算法,O(ne)。大纲未列。
拓扑排序
- 选一个入度为 0 的顶点输出。
- 删掉它和它发出的所有边(邻居入度 −1)。
- 重复,直到全部输出,或者找不到入度为 0 的顶点——后者说明图中有环。
第 1~3 步都不止一个可选,所以拓扑序列不唯一,例如“离散 → 程设 → …”也对。
- 时间:邻接表 O(n + e),邻接矩阵 O(n²)。用栈或队列存入度为 0 的顶点都行(结果可能不同)。
- 拓扑序列唯一的条件:每一步都恰好只有一个入度为 0 的顶点。
- 若邻接矩阵是三角矩阵(主对角线以下全 0),则一定存在拓扑序列(反过来不一定)。
- 也可用 DFS:按顶点结束(退出递归)的时间逆序输出,即逆拓扑序的反转。
用有向无环图描述表达式
把表达式树中相同的子表达式合并成一个结点,得到 DAG,可以节省存储。做法:先画出表达式树,从叶子(操作数)开始把相同的结点合并,再逐层向上合并相同的运算。例:(a+b)*(a+b)*c 中两个 a+b 只保留一个。该内容不在新大纲“图的基本应用”条目中,但真题曾考过“至少需要几个顶点”,建议会做。
关键路径
活动:a1 <1,2> 3,a2 <1,3> 2,a3 <2,4> 2,a4 <2,5> 3,a5 <3,4> 4,a6 <3,6> 3,a7 <4,6> 2,a8 <5,6> 1。
| 事件 | v1 | v2 | v3 | v4 | v5 | v6 |
|---|---|---|---|---|---|---|
| ve | 0 | 3 | 2 | max(5, 6) = 6 | 6 | max(8, 5, 7) = 8 |
| vl | 0 | min(4, 4) = 4 | min(2, 5) = 2 | 6 | 7 | 8 |
| 活动 | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
|---|---|---|---|---|---|---|---|---|
| e | 0 | 0 | 3 | 3 | 2 | 2 | 6 | 6 |
| l | 1 | 0 | 4 | 4 | 2 | 5 | 6 | 7 |
| d | 1 | 0 | 1 | 1 | 0 | 3 | 0 | 1 |
a6 的余量 d = 3:它可以晚开工 3 天而不影响工期。
- 关键路径是最长路径,不是最短。
- 缩短某个关键活动不一定缩短工期(可能有多条关键路径,或缩短后关键路径变了);只有缩短所有关键路径共有的关键活动才一定有效。
- 非关键活动在余量 d 以内拖延不影响工期。
自测与考前速览
1. 用邻接表存储有向图,求某顶点的入度要怎么做?时间多少?
遍历所有顶点的边链表,数指向它的边数,O(n + e)。若常求入度可用逆邻接表或十字链表。
2. 无权图求单源最短路径用什么?
BFS。
3. 为什么 Dijkstra 不能处理负权边?
它每轮把当前距离最小的顶点永久确定,负权边可能使已确定顶点的距离之后还能变小,但算法不会再修改。
4. 拓扑排序还没输出完所有顶点就找不到入度为 0 的点,说明什么?
图中存在有向回路(不是 DAG)。
5. Prim 和 Kruskal 各自适合什么图?
Prim O(n²) 适合稠密图;Kruskal O(e log e) 适合稀疏图。
6. 关键活动的特征是什么?
最早开始时间 = 最迟开始时间,即时间余量 d = 0。
7. 6 个顶点的无向图,要保证在任何情况下都连通,至少几条边?
5×4/2 + 1 = 11。
矩阵 O(n²) 唯一,邻接表 O(n+e) 不唯一。
BFS 队列、DFS 栈;BFS 求无权最短路。
Prim 选点稠密图,Kruskal 选边稀疏图。
Dijkstra 不能负权,Floyd 中转 k 在最外层。
ve 正推取大,vl 倒推取小,d = 0 是关键活动。
① 十字链表是有向图,邻接多重表是无向图。
② MST 不唯一,但权值和唯一。
③ MST 上的路径不一定最短。
④ 关键路径是最长路径。
⑤ 缩短一个关键活动不一定缩短工期。