首页/数据结构/第 6 章 图
408 计算机学科专业基础 数据结构 第 6 章

图
存储、遍历与四大应用

选择题 3–4 道,应用题常客。必会的四个“手算表格”:最小生成树、Dijkstra 最短路径、拓扑排序、关键路径——本页每个都配了逐步模拟器。

图是最一般的结构:任意两个元素之间都可以有关系。地图导航(最短路径)、布线(最小生成树)、课程先修关系(拓扑排序)、工程排期(关键路径)都是图的应用。

6 个考点模块 5 个交互模拟器
12 34 56
00
复习策略

考频地图

★★★★★ 核心章 选择 + 综合

图的选择题 3–4 道,综合题(应用题)也常考:给一个图,写邻接矩阵 / 邻接表,求最小生成树、最短路径、拓扑序列或关键路径。每一种都有固定的“手算表格”,照着模拟器的表格格式写就是标准答案。

考点考频常见问法
图的基本概念★★★☆☆“n 个顶点保证连通至少需要多少条边”
邻接矩阵 / 邻接表★★★★☆“空间复杂度”“求入度的时间”
BFS / DFS★★★★☆“可能的 DFS 序列”“时间复杂度”
最小生成树★★★★★“Prim / Kruskal 依次选出的边”
最短路径★★★★★“Dijkstra 求得的最短路径顺序”
拓扑排序与关键路径★★★★★“关键路径长度”“哪些活动是关键活动”
一句话:稠密图用邻接矩阵(O(n²)),稀疏图用邻接表(O(n + e));遍历的复杂度跟着存储走。MST 有两种贪心(Prim 加点、Kruskal 加边),最短路径 Dijkstra 不能有负权,AOE 网中 d = l − e = 0 的活动是关键活动。
01
6.1 · 打基础

图的基本概念

★★★☆☆ 中频 选择题
概念结论
边数上限无向图 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 条边;再加一条边必成环
简单路径 / 回路顶点不重复的路径;第一个顶点和最后一个相同的路径叫回路
#
例:8 个顶点的无向图,至少多少条边才能保证它一定连通?
计算
1
最“坏”的连法:7 个顶点构成完全图,第 8 个孤立
7×6/2 = 21 条边仍不连通
2
再多 1 条边就必然连到孤立点
21 + 1 = 22
02
6.2 · 高频

存储结构与遍历

★★★★☆ 高频 选择题
存储空间找边 (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 序列”:每一步访问的顶点必须是当前顶点未访问的邻接点;若没有,回溯到最近的有未访问邻接点的顶点。
03
6.3 · 必考

最小生成树

★★★★★ 必考 选择 + 综合

带权连通无向图中,边权之和最小的生成树叫最小生成树(MST)。两种贪心算法:

算法做法时间复杂度适合
Prim从一个顶点出发,每次选“一端在树内、一端在树外”的最小边,加入新顶点O(n²)稠密图(与边数无关)
Kruskal把边按权值从小到大排序,依次选不会形成回路的边(用并查集判断)O(e log e)稀疏图
  • MST 不一定唯一(有权值相同的边时),但 MST 的总权值唯一。各边权值都不同时 MST 唯一。
  • MST 的边数是 n − 1;最小生成树上两点间路径不一定是最短路径。
  • Prim 每次加入的是“顶点”,Kruskal 每次加入的是“边”,过程中 Kruskal 的选中边可能暂时不连通。
04
6.4 · 必考

最短路径

★★★★★ 必考 选择 + 综合
算法问题时间负权边
BFS无权图的单源最短路径O(n + e)—
Dijkstra带权图的单源最短路径O(n²)不允许
Floyd每对顶点之间的最短路径O(n³)允许负权边,但不允许负权回路

Dijkstra:每轮确定一个顶点

  1. dist[] 初始化为源点到各顶点的直接边权(没有边为 ∞),S = {源点}。
  2. 在不在 S 中的顶点里选 dist 最小的 u 加入 S(它的最短距离已确定)。
  3. 用 u 更新其他顶点:若 dist[u] + w(u, v) < dist[v],则更新 dist[v] 和 path[v]。
  4. 重复 2–3 直到所有顶点加入 S。

为什么不能有负权:Dijkstra 假设“当前最小的 dist 不会再被别的路径缩短”。有负权边时,以后经过负权边的路径可能更短,已确定的结果就错了。
Floyd:依次以每个顶点 k 作为中转点,A[i][j] = min(A[i][j], A[i][k] + A[k][j]),三重循环,k 在最外层。

05
6.5 · 必考

有向无环图:拓扑排序与关键路径

★★★★★ 必考 选择 + 综合

一、DAG 描述表达式

表达式中相同的子式可以共享一个结点。例(2019 真题):((x + y) × ((x + y) / x)) 的 DAG 最少需要 5 个顶点:x、y、+、/、×(x + y 只出现一次,x 也只出现一次)。

二、拓扑排序(AOV 网)

  1. 选一个入度为 0 的顶点输出;
  2. 删除它和它的所有出边(后继入度 −1);
  3. 重复,直到图空(成功)或剩下的顶点入度都不为 0(有回路)。

时间 O(n + e)(邻接表)。若某步有多个入度为 0 的顶点,拓扑序列就不唯一。也可以用 DFS:每个顶点 DFS 结束时记录,得到的是逆拓扑序列。若邻接矩阵是三角矩阵,则一定存在拓扑序列(反之不一定)。

三、关键路径(AOE 网)

边表示活动、权值表示持续时间、顶点表示事件。从源点到汇点最长的路径叫关键路径,其长度就是完成整个工程的最短时间。

事件 vₖ 最早发生 ve(k) = max{ ve(j) + 活动(j→k) 时间 }  按拓扑序从前往后 事件 vₖ 最迟发生 vl(k) = min{ vl(j) − 活动(k→j) 时间 }  按逆拓扑序从后往前,vl(汇点) = ve(汇点) 活动 aᵢ(j→k):e(i) = ve(j),l(i) = vl(k) − 时间,d(i) = l(i) − e(i) d(i) = 0 → 关键活动
  • 关键路径可能不止一条;缩短某个关键活动不一定缩短总工期(可能变成非关键,或别的关键路径仍在)。只有缩短所有关键路径共有的关键活动才一定能缩短工期。
  • ve 取 max(要等所有前驱活动都完成),vl 取 min。
  • 拓扑排序能用来判断有向图是否有环;无向图判环用 DFS 或并查集。
06
实战

真题与自测

★★★★★ 收口 选择 + 综合

一、真题问法

问法 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,没有余量,延误一点都会推迟整个工期。

三、考前速览

4 句话

矩阵 O(n²),邻接表 O(n + e)。
Prim 加点 O(n²),Kruskal 加边 O(e log e)。
Dijkstra 不能负权,Floyd O(n³)。
ve 取 max、vl 取 min,d = 0 为关键。

3 个易错

① 保证连通要 (n−1)(n−2)/2 + 1 条边。
② MST 不唯一但权值唯一。
③ 缩短关键活动不一定缩短工期。