首页/考点精讲/数据结构 · 图
考点精讲数据结构大纲 · 图

图
四个应用算法,都是“手算一张表”

选择 2–4 道,应用题常客:Prim/Kruskal 过程、Dijkstra 表、拓扑序列、关键路径;算法题偶尔考邻接矩阵/邻接表上的统计与遍历。

图 = 顶点 + 边。先学会怎么存(矩阵还是链表),再学会怎么走(BFS 一圈圈、DFS 一条道走到黑),最后四个应用都是在“走”的基础上,每一步贪心地挑一个最小的(MST、最短路径)或挑一个没有前驱的(拓扑、关键路径)。

10 个大纲条目 5 种手算过程 2 处仅做理解
00
先看范围

大纲对照

★★★★★ 必考选择 + 应用
  1. 一图的基本概念→ 01
(二)图的存储及基本操作
  1. 1邻接矩阵→ 02
  2. 2邻接表→ 02
  3. 3邻接多重表、十字链表→ 02
(三)图的遍历
  1. 1深度优先搜索→ 03
  2. 2广度优先搜索→ 03
(四)图的基本应用
  1. 1最小(代价)生成树→ 04
  2. 2最短路径→ 05
  3. 3拓扑排序→ 06
  4. 4关键路径→ 07
本页标为“仅做理解”的内容

有向无环图描述表达式(真题曾出现,建议会做) · Bellman-Ford 等其他最短路径算法。

n 个顶点:邻接矩阵 O(n²),邻接表 O(n + e)——遍历、拓扑排序的复杂度都由存储结构决定。MST 和 Dijkstra 都是贪心;拓扑和关键路径都只能用于有向无环图。
01
大纲(一)

图的基本概念

★★★☆☆选择
概念要点
完全图无向:任意两点都有边,n(n−1)/2 条;有向:任意两点都有两条方向相反的弧,n(n−1) 条
度无向图 Σ度 = 2e;有向图 Σ入度 = Σ出度 = e
连通 / 连通分量无向图任意两点有路径 = 连通;极大连通子图 = 连通分量
强连通 / 强连通分量有向图任意两点互相可达
生成树连通图的极小连通子图:含全部 n 个顶点、n − 1 条边;多一条边就有环,少一条就不连通
简单路径 / 回路顶点不重复的路径叫简单路径;首尾相同叫回路(环)
右图中 A、B、C 互相可达,构成一个强连通分量(橙色);D 走不回去,自己单独是一个。所以这个有向图不是强连通图,有 2 个强连通分量。
微信好友是无向图(互为好友);微博关注是有向图(你关注了明星,明星不一定关注你);地图上的路加上距离就是带权图(网)。
常考边数界: n 个顶点的无向图要连通,至少 n − 1 条边 n 个顶点的有向图要强连通,至少 n 条边(一个环) n 个顶点的无向图在任何情况下都连通,至少 (n−1)(n−2)/2 + 1 条边 (先把 n−1 个点连成完全图,再加 1 条边连上最后一个点) n 个顶点、e > n − 1 条边的无向图 → 一定有环

① 简单无向图有 28 条边,至少有多少个顶点?② 8 个顶点的无向图,要保证无论边怎么连都是连通图,至少需要多少条边?

① n(n−1)/2 ≥ 28 → n ≥ 8,至少 8 个顶点(此时恰好是完全图)。
② 最“坏”的连法:7 个顶点连成完全图(21 条边),第 8 个孤立;再加 1 条就必然连通 → 22 条。
02
大纲(二)1–3

图的存储

★★★★☆选择 + 算法
邻接矩阵 = 一张 n×n 的“谁和谁相连”的表;邻接表 = 每个顶点挂一条链,链上是它能直接到的邻居。边少(稀疏图)用链表省空间,边多(稠密图)用矩阵查得快。
同一个图的两种存法。邻接矩阵 V1 那一行有 3 个 1(橙色)→ V1 的度为 3;矩阵关于主对角线对称。
邻接表:绿色是顶点表,后面挂的是边结点(存邻接点下标)。6 条边在无向图的邻接表中出现 12 次(每条边存两遍)。
城市地铁图:站点少、线路密的小城市用矩阵一目了然;全国铁路网几千个站,每站只连几个邻站,用邻接表才不浪费空间。
对比邻接矩阵邻接表
空间O(n²)无向 O(n + 2e),有向 O(n + e)
判断 (i, j) 是否有边O(1)O(度)
求顶点的度扫一行(有向图入度扫一列)出度扫自己的链;入度要扫全部链
表示唯一吗唯一不唯一(链中顺序可变)
适合稠密图稀疏图
邻接矩阵 A 的 Ak[i][j] = 从 i 到 j 长度为 k 的路径条数。无向图的邻接矩阵对称,可只存上(下)三角。
#define MaxV 100 typedef struct ArcNode { // 边结点 int adjvex; // 这条边指向的顶点 struct ArcNode *next; } ArcNode; typedef struct { // 顶点表结点 VertexType data; ArcNode *first; } VNode; typedef struct { VNode adj[MaxV]; int vexnum, arcnum; } ALGraph;

十字链表与邻接多重表

  • 十字链表:有向图专用。每条弧一个结点,同时挂在“弧尾的出边链”和“弧头的入边链”上 → 出度、入度都好求。
  • 邻接多重表:无向图专用。每条边只用一个结点(邻接表中每条边存两次),同时挂在两个端点的链上 → 删边方便。
  • 记法:“十字”有方向(有向图),“多重”是一边多用(无向图)。
03
大纲(三)

图的遍历:BFS 与 DFS

★★★★★选择 + 算法
BFS 像水波:先访问所有邻居,再访问邻居的邻居(用队列,类似树的层序)。DFS 像走迷宫:一条路走到底,走不通再退回上一个路口(用栈/递归,类似树的先序)。两者都要一个 visited[] 数组避免重复访问。
按上面的邻接表顺序(邻居下标从小到大)。圈号是访问次序,橙色边组成生成树,虚线是没用到的边。
BFS:V0 V1 V3 V2 V4(下方是队列变化);DFS:V0 V1 V2 V3 V4——从 V2 先走到 V3,V3 无路可走退回 V2,再走 V4。
BFS 像在社交网络里找“二度人脉”:先看所有直接好友,再看好友的好友,所以第一次找到某人时走的就是最少的“中间人”(无权最短路)。DFS 像走迷宫时一只手扶着墙一直走,走到死胡同再退回上一个岔路口。
void BFS(Graph G, int v) { void DFS(Graph G, int v) { visit(v); visited[v] = true; visit(v); visited[v] = true; EnQueue(Q, v); for (w = 第一个邻接点; w 存在; w = 下一个) while (!IsEmpty(Q)) { if (!visited[w]) DFS(G, w); DeQueue(Q, v); } for (每个邻接点 w) if (!visited[w]) { // 非连通图:对每个未访问顶点调用一次 visit(w); visited[w] = true; // 调用次数 = 连通分量数 EnQueue(Q, w); } } }
动手试一试:输入边表,看 BFS / DFS 序列
BFSDFS
辅助结构队列栈(递归)
时间(邻接矩阵 / 邻接表)O(n²) / O(n + e)
空间O(n)
特别用途无权图单源最短路径;生成的 BFS 树高度最小判断有向图是否有环(存在回边);拓扑排序(逆后序)
  • 给定邻接矩阵,遍历序列唯一;给定的只是“图”或邻接表顺序不定时,遍历序列不唯一——选择题常问“下列哪个不可能是 DFS 序列”。
  • 判断不可能的 DFS 序列:每访问一个新顶点,它必须和“当前递归栈里最上面那个还有未访问邻居的顶点”相邻。
04
大纲(四)1

最小(代价)生成树

★★★★★选择 + 应用
要把 n 个村子用公路连起来,总造价最低:选 n − 1 条边,连通、无环、权值和最小。两种贪心:Prim 从一个村子出发“逐个拉进来”(每次挑跨出已选集合的最短边);Kruskal 把所有边从短到长看一遍,“不成环就要”。
PrimKruskal
每一步加入离当前树最近的顶点加入最短的、不成环的边(并查集判环)
时间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。

Kruskal:A–C 1 ✓,B–C 2 ✓,D–E 2 ✓,E–F 3 ✓,A–B 4 ✗(A、B 已连通),B–D 5 ✓ → 共 5 条,权和 13。
Prim(从 A 开始):A–C 1 → C–B 2 → B–D 5 → D–E 2 → E–F 3,权和同为 13,但加边顺序不同——题目常问“第几条加入的边是哪条”。
橙色 5 条边就是最小生成树,权和 13。Kruskal 按权值从小到大看边:A–B 时 A、B 已经通过 C 连通,再加就成环,跳过;选够 n − 1 = 5 条就停。
要给 6 个村子修路实现“村村通”,每条可修道路有不同造价:最小生成树就是总造价最低、又能让所有村子连通的修路方案。铺设光缆、电网布线也是同一个问题。
动手试一试:输入带权边,对比 Prim 与 Kruskal 的加边顺序
  • MST 不一定唯一;所有边权都不相同时唯一。但 MST 的总权值一定唯一。
  • MST 中两点间的路径不一定是这两点的最短路径。
  • 最小权的边一定在某棵 MST 中;最大权的边不一定不在(如果它是桥就必须在)。
05
大纲(四)2

最短路径:Dijkstra 与 Floyd

★★★★★选择 + 应用
Dijkstra(单源):从起点出发,每次在“还没确定的顶点”中挑当前距离最小的,把它定下来,再用它去更新邻居的距离(“松弛”)。Floyd(所有点对):依次允许经过顶点 0、1、…、n−1 中转,看能不能把 i 到 j 变短。

有向边:V0→V1 10,V0→V3 30,V0→V4 100,V1→V2 50,V2→V4 10,V3→V2 20,V3→V4 60。求 V0 到其余各点的最短路径。

轮次V1V2V3V4选中
初始10∞30100V1
2—60(经 V1)30100V3
3—50(经 V3)—90(经 V3)V2
4———60(经 V2)V4
顶点确定顺序 V1、V3、V2、V4;V4 的最短路径 V0→V3→V2→V4,长度 60。
节点下方数字是 V0 到它的最短距离;橙色边组成最短路径树。V0 → V4 直达要 100,绕 V3、V2 只要 30 + 20 + 10 = 60。
V2 的距离先被更新成 60(经 V1),后来发现经 V3 只要 50,又被改小——这就是“松弛”。
手机导航找最短路线:路口是顶点、道路是边、行驶时间是权值。Dijkstra 从出发地一圈圈往外“确定”最近的路口,直到确定目的地。
动手试一试:逐轮看 dist[] 和 path[] 的变化
Floyd: for (k = 0; k < n; k++) // 中转点放最外层! for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (A[i][k] + A[k][j] < A[i][j]) A[i][j] = A[i][k] + A[k][j], path[i][j] = k;
算法问题时间负权边
BFS无权图单源O(n + e)—
Dijkstra单源O(n²)不能有
Floyd所有顶点对O(n³)可以有负权边,但不能有负权回路
  • Dijkstra 一旦把顶点“定下来”就不再修改,所以负权边会让它出错。
  • Dijkstra 和 Prim 很像,区别:Prim 比的是“到树的距离”(单条边权),Dijkstra 比的是“到起点的距离”(路径总长)。

Bellman-Ford、SPFA

能处理负权边、检测负权回路的单源最短路径算法,O(ne)。大纲未列。

06
大纲(四)3

拓扑排序

★★★★☆选择 + 应用
课程有先修关系:学“数据结构”之前要学“C 语言”。把课程排成一个顺序,使得每门课都排在它所有先修课之后——这就是拓扑排序。图叫 AOV 网(顶点表示活动),必须是有向无环图 DAG。
  1. 选一个入度为 0 的顶点输出。
  2. 删掉它和它发出的所有边(邻居入度 −1)。
  3. 重复,直到全部输出,或者找不到入度为 0 的顶点——后者说明图中有环。
每行列出当时入度为 0(先修课都学完了)的课程,橙色是这一步选出来的。结果:程设 → 离散 → 计组 → 数据结构 → 操作系统 → 计网。
第 1~3 步都不止一个可选,所以拓扑序列不唯一,例如“离散 → 程设 → …”也对。
  • 时间:邻接表 O(n + e),邻接矩阵 O(n²)。用栈或队列存入度为 0 的顶点都行(结果可能不同)。
  • 拓扑序列唯一的条件:每一步都恰好只有一个入度为 0 的顶点。
  • 若邻接矩阵是三角矩阵(主对角线以下全 0),则一定存在拓扑序列(反过来不一定)。
  • 也可用 DFS:按顶点结束(退出递归)的时间逆序输出,即逆拓扑序的反转。

用有向无环图描述表达式

把表达式树中相同的子表达式合并成一个结点,得到 DAG,可以节省存储。做法:先画出表达式树,从叶子(操作数)开始把相同的结点合并,再逐层向上合并相同的运算。例:(a+b)*(a+b)*c 中两个 a+b 只保留一个。该内容不在新大纲“图的基本应用”条目中,但真题曾考过“至少需要几个顶点”,建议会做。

07
大纲(四)4

关键路径

★★★★★应用
一个工程分成若干活动,有的可以并行。整个工程最快多久完成?答案是从开始到结束最长的那条路径(因为它上面的活动一个都不能拖)——这条路径叫关键路径。图叫 AOE 网:边表示活动、边权是持续时间,顶点表示事件(“某些活动都完成了”)。
事件(顶点): ve(j) 最早发生时间:从源点往后推,取 max(所有前驱活动都完成才算发生) vl(j) 最迟发生时间:从汇点往前推,取 min(不能耽误任何后继) vl(汇点) = ve(汇点) 活动(边 a = <i, j>,权 w): e(a) = ve(i) 最早开始 l(a) = vl(j) − w 最迟开始 d(a) = l(a) − e(a) 时间余量;d = 0 的活动是关键活动

活动: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。

事件v1v2v3v4v5v6
ve032max(5, 6) = 66max(8, 5, 7) = 8
vl0min(4, 4) = 4min(2, 5) = 2678
活动a1a2a3a4a5a6a7a8
e00332266
l10442567
d10110301
关键活动 a2、a5、a7,关键路径 v1 → v3 → v4 → v6,工程最短工期 8。
顶点下方是 ve / vl;ve = vl 的事件(绿色)都在关键路径上,橙色的 a2 → a5 → a7 是关键活动,总长 2 + 4 + 2 = 8。
a6 的余量 d = 3:它可以晚开工 3 天而不影响工期。
做一顿饭:煮饭 30 分钟,同时洗菜 5 分钟 → 切菜 10 分钟 → 炒菜 10 分钟。最快多久开饭?取最长的那条:30 分钟(煮饭)。煮饭是“关键活动”,切菜慢一点(余量 5 分钟内)不影响开饭;想更早开饭,只能想办法让饭快点熟。
动手试一试:输入 AOE 网,自动算 ve、vl、e、l 和关键路径
  • 关键路径是最长路径,不是最短。
  • 缩短某个关键活动不一定缩短工期(可能有多条关键路径,或缩短后关键路径变了);只有缩短所有关键路径共有的关键活动才一定有效。
  • 非关键活动在余量 d 以内拖延不影响工期。
08
收口

自测与考前速览

★★★★★自测
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 上的路径不一定最短。
④ 关键路径是最长路径。
⑤ 缩短一个关键活动不一定缩短工期。