图
🎯 一句话秒杀：图是 多对多 的结构——顶点之间的关系是任意的。遍历图需要记录"访问过"的顶点（不然会死循环）。
① 📊【历年真题考情】
本章（图）在广东专升本计算机统考中的位置：
| 项目 | 结论 |
|---|---|
| 出题频次 | ⭐⭐⭐⭐——2026 考纲全解标注"图：单选、填空、计算，约10分"；图的遍历与存储 2/4 年（2023 实考） |
| 常考题型 | 单选、填空、计算大题（Prim/Kruskal/DFS 序列）、简答 |
| 预估分值 | 8~18 分 / 200 分（单选+填空+计算大题，树图合计约 18 分） |
| 考纲归属 | 2026 考纲「非线性结构」考点16（存储、遍历、最小生成树、最短路径） |
考场真实出现过的高频题：
- 2024 填空5：9 个顶点的连通图最少需要 8 条边（n-1）
- 2024 简答4：有向图的出度/入度定义（Σ出度=Σ入度=边数，10 分）
- 2021 大题45：Prim 最小生成树（以结点 1 为起点）
- 2022 大题：从 1 开始 DFS（邻接点升序）写访问序列 + Prim/Kruskal 最小生成树并画树
- 2023：图的遍历（DFS）
🎯 学习目标：学完本章，你能 ① 手算 DFS/BFS 访问序列；② 手算 Prim（加点法）和 Kruskal（加边法）最小生成树；③ 说出度/入度/连通边数公式；④ 选对存储结构——尤其是 2021/2022 两道手算大题，必须会一步步画。
② 🗣️【零基础大白话引入】
图是什么？ 图就是一群点 + 连接它们的线。你手机里的地图导航——城市是"顶点"，道路是"边"；微信好友关系——每个人是顶点，"认识"就是边。图研究的就是"点和点之间怎么连"。
三个生活化比喻：
- DFS（深度优先） = 走迷宫，一条道走到黑，走不通再退回来换一条——"先深后广"
- BFS（广度优先） = 波浪扩散，先看所有"一步能到"的，再看"两步能到"的——"逐层展开"
- 最小生成树 = 给几个村庄修路，要求连通所有村且总路费最少——这就是 Prim/Kruskal 干的事
为什么是考试重点？ 因为图的题"会画就会做"——手算最小生成树和手写遍历序列是计算大题的常客（2021、2022 都考了），把画图过程练熟，10-20 分就到手。
💡 本章主线：术语（怎么描述图）→ 存储（怎么存图）→ 遍历（怎么走图）→ 最小生成树（怎么连图）→ 最短路径/拓扑（图的进阶应用）。
③ 📖【正式核心知识点讲解】
本章知识点 = 考纲要求 + 历年真题实际考过的内容。
3.1 图的定义与术语
图的定义
图 G = (V, E)
V：顶点的非空有限集合
E：边的有限集合
基本术语
| 术语 | 定义 |
|---|---|
| 有向图 | 边有方向（弧） |
| 无向图 | 边无方向 |
| 完全图 | 任意两个顶点间都有边 |
| 度 | 与顶点关联的边数 |
| 入度 | 有向图中指向该顶点的弧数 |
| 出度 | 有向图中从该顶点出发的弧数 |
| 连通图 | 任意两顶点间都有路径 |
| 生成树 | 连通图的极小连通子图（n个顶点，n-1条边） |
🔑 秒杀秘籍（2024 填空5 / 简答4 必考）
完全图边数公式（必背！）：
- 无向完全图：n(n-1)/2 条边
- 有向完全图：n(n-1) 条边（每对顶点两条方向相反的弧）
度与边的关系：
- 无向图：所有顶点的度之和 = 2 × 边数
- 有向图：入度之和 = 出度之和 = 边数
✅ 2024 填空5：9 个顶点的连通图最少需要 8 条边（n 顶点连通最少 n-1 条边，形成树） ✅ 2024 简答4（10 分）：有向图 = 顶点集 + 边集（有序对
<v,w>）；出度 OD(v)=以 v 为弧尾的弧数；入度 ID(v)=以 v 为弧头的弧数；Σ出度=Σ入度=边数
3.2 图的存储
3.2.1 邻接矩阵（顺序存储）
#define MAXVEX 100
typedef struct {
int edges[MAXVEX][MAXVEX]; // 邻接矩阵
int n, e; // 顶点数、边数
} MGraph;无向图邻接矩阵（对称矩阵）：
A B C D
A [[0,1,1,0],
B [1,0,0,1],
C [1,0,0,1],
D [0,1,1,0]]
特点：无向图对称，有向图不一定对称| 特点 | 说明 |
|---|---|
| 优点 | 判断任意两点是否有边 — O(1) |
| 缺点 | 存储空间 O(n²) — 稀疏图浪费大 |
3.2.2 邻接表（链式存储）
typedef struct EdgeNode { // 边结点
int adjvex; // 邻接点下标
struct EdgeNode *next; // 下一条边
} EdgeNode;
typedef struct { // 顶点结点
int data; // 顶点信息
EdgeNode *firstedge; // 第一条边
} VertexNode, AdjList[MAXVEX];
typedef struct {
AdjList adjlist; // 顶点数组
int n, e; // 顶点数、边数
} ALGraph;邻接表（无向图）：
A → B → C
B → A → D
C → A → D
D → B → C
特点：边数 = 链表结点数/2（无向图每条边存两次）| 特点 | 说明 |
|---|---|
| 优点 | 节省空间（稀疏图），找邻接点快 |
| 缺点 | 判断两点是否有边需要遍历链表 |
3.2.3 邻接矩阵 vs 邻接表（2022 单选关联）
| 比较 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | O(n²) | O(n+e) |
| 适用场景 | 稠密图 | 稀疏图 |
| 判断两点相连 | O(1) ✅ | O(度) |
| 找所有邻接点 | O(n) | O(度) ✅ |
💡 记忆：稠密用矩阵（判断快），稀疏用链表（省空间）。
3.3 图的遍历（2023 真题 + 2022 大题）
3.3.1 深度优先搜索 DFS（类似树的先序遍历）
#define MAXVEX 100
int visited[MAXVEX]; // 访问标记数组
void DFS(ALGraph G, int v) {
printf("%d ", v);
visited[v] = 1; // 标记已访问
EdgeNode *p = G.adjlist[v].firstedge;
while (p) {
if (!visited[p->adjvex])
DFS(G, p->adjvex);
p = p->next;
}
}
void DFSTraverse(ALGraph G) {
for (int i = 0; i < G.n; i++)
visited[i] = 0; // 初始化
for (int i = 0; i < G.n; i++)
if (!visited[i])
DFS(G, i); // 处理非连通图
}DFS 手算（2022 大题格式）：从顶点 1 开始，邻接点按编号升序，写访问序列。
图：1-2, 1-3, 2-4, 3-4, 4-5
DFS 从 1 开始：
第1步：访问 1，标记
第2步：1 的邻接点（升序）：2, 3 → 先走 2，访问 2
第3步：2 的邻接点：1(已访问), 4 → 走 4，访问 4
第4步：4 的邻接点：2(已访问), 3, 5 → 升序先 3，访问 3
第5步：3 的邻接点：1(已访问), 4(已访问) → 无新点，**回溯**
第6步：回到 4，还有 5 未访问 → 访问 5
序列：1, 2, 4, 3, 5💡 DFS 手算要点：① 走到死路就回溯；② 邻接点按题目要求排序（升序/降序）；③ 用 visited 数组防死循环。
3.3.2 广度优先搜索 BFS（类似树的层次遍历）
void BFS(ALGraph G, int v) {
int queue[MAXVEX], front=0, rear=0;
printf("%d ", v);
visited[v] = 1;
queue[rear++] = v; // 入队
while (front != rear) {
int w = queue[front++]; // 出队
EdgeNode *p = G.adjlist[w].firstedge;
while (p) {
if (!visited[p->adjvex]) {
printf("%d ", p->adjvex);
visited[p->adjvex] = 1;
queue[rear++] = p->adjvex;
}
p = p->next;
}
}
}BFS 手算（同一张图）：
第1步：访问 1，入队 [1]
第2步：出队 1，邻接点升序 2, 3 → 访问 2、3，入队 [2,3]
第3步：出队 2，邻接点 1(已访问), 4 → 访问 4，入队 [3,4]
第4步：出队 3，邻接点 1(已访问), 4(已访问) → 无新点
第5步：出队 4，邻接点 2,3(已访问), 5 → 访问 5，入队 [5]
第6步：出队 5，结束
序列：1, 2, 3, 4, 5💡 BFS 手算要点：用队列，先访问"所有一步能到的"，再"两步"……一层层展开。
3.3.3 DFS vs BFS
| 对比 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（递归） | 队列 |
| 策略 | 深入优先，走到底再回头 | 逐层展开 |
| 应用 | 判断连通性、查找路径 | 最短路径、网络爬虫 |
✅ 2022 大题第(1)问：从 1 开始 DFS，邻接点升序 → 写访问序列（就是上面的手算过程）
3.4 生成树与最小生成树（2021 大题45 + 2022 大题核心）
生成树
n个顶点、n-1条边的连通子图
DFS生成树：DFS遍历时经过的边构成的树 BFS生成树：BFS遍历时经过的边构成的树
最小生成树 —— 权值和最小的生成树
3.4.1 Prim 算法（加点法 · 2021 大题45）
思想：从一个顶点出发，每次选"已选集合"到"未选集合"的最短边，加入新顶点，直到所有顶点进树。
手算步骤（零基础版）：
- 从起点（如顶点 1）开始，标记"已选"
- 找"已选顶点"和"未选顶点"之间的所有边，选权值最小的一条
- 把这条边的新顶点加入"已选"
- 重复 2-3，直到所有顶点都被选（共 n-1 条边）
手算例题（2021 大题风格）：5 个顶点，边及权值如下，从顶点 1 开始用 Prim 求最小生成树。
边：1-2(3), 1-3(1), 2-3(2), 2-4(5), 3-4(6), 3-5(4), 4-5(7)
| 步骤 | 已选集合 | 候选最短边（权值） | 选中 | 累计权值 |
|---|---|---|---|---|
| 1 | 1-2(3), 1-3(1) | 1-3(1) | 1 | |
| 2 | 1-2(3), 3-2(2), 3-4(6), 3-5(4) | 3-2(2) | 3 | |
| 3 | 2-4(5), 3-4(6), 3-5(4) | 3-5(4) | 7 | |
| 4 | 2-4(5), 3-4(6), 5-4(7) | 2-4(5) | 12 |
最小生成树边集：{1-3, 3-2, 3-5, 2-4}，总权值 12 ✅ Prim 特点：加点法，O(n²)，适合稠密图
3.4.2 Kruskal 算法（加边法 · 2022 大题）
思想：把所有边按权值从小到大排序，从最小开始选，只要不构成回路就选，直到选满 n-1 条边。
手算步骤（零基础版）：
- 把所有边按权值升序排列
- 从最小权值边开始，逐条检查：加入后不形成回路就选
- 选满 n-1 条边结束
手算例题（同一张图，Kruskal）：
边按权值升序：1-3(1), 2-3(2), 1-2(3), 3-5(4), 2-4(5), 3-4(6), 4-5(7)| 步骤 | 边（权值） | 构成回路？ | 选中 |
|---|---|---|---|
| 1 | 1-3(1) | 否 | ✅ |
| 2 | 2-3(2) | 否 | ✅ |
| 3 | 1-2(3) | 是（1-2-3 成环） | ❌ 跳过 |
| 4 | 3-5(4) | 否 | ✅ |
| 5 | 2-4(5) | 否 | ✅（已 4 条边=n-1，结束） |
最小生成树边集：{1-3, 2-3, 3-5, 2-4}，总权值 12（与 Prim 结果一致！） ✅ Kruskal 特点：加边法，O(e log e)，适合稀疏图 ✅ 两种算法结果可能不同（边的选择不同），但总权值最小且唯一（权值不等时）
3.4.3 Prim vs Kruskal 对比表
| 对比 | Prim | Kruskal |
|---|---|---|
| 思路 | 加点法（顶点出发） | 加边法（边出发） |
| 时间复杂度 | O(n²) | O(e log e) |
| 适合 | 稠密图（边多） | 稀疏图（边少） |
| 关键操作 | 每次选最短跨边 | 每次选最短且不成环的边 |
| 真题 | 2021 大题45 | 2022 大题（二选一） |
3.5 最短路径
| 算法 | 解决问题 | 时间复杂度 |
|---|---|---|
| Dijkstra | 单源最短路径 | O(n²) |
| Floyd | 所有顶点间最短路径 | O(n³) |
💡 记忆：Dijkstra 单源（一个起点到所有点），Floyd 全源（任意两点间）。
3.6 拓扑排序
对有向无环图（DAG）的顶点排序——如果A→B，则A在B前面
应用： 课程安排（先修课程）、工程流程
💡 拓扑排序：每次选"入度为 0"的顶点输出，删掉它的所有出边，重复直到全部输出。有环图无法拓扑排序。
④ 🧪【真题同源例题】
例题 1：入门基础题（先热热身）
有 6 个顶点的无向完全图，有多少条边？
逐项推演：
- 无向完全图：每对顶点之间都有边
- 6 个顶点任取 2 个的组合数：C(6,2) = 6×5/2 = 15
- 答案：15 条边（公式 n(n-1)/2）
验证：每个顶点连 5 条边，6 个顶点共 30 但每条边算了两次 → 30/2=15 ✅
例题 2：2022 真题改编（DFS 序列）
从顶点 1 开始 DFS，邻接点按编号升序，写出下面图的访问序列。
图：1-2, 1-3, 2-4, 3-4逐步推演：
| 步骤 | 当前顶点 | 动作 | 已访问序列 |
|---|---|---|---|
| 1 | 1 | 访问 1 | 1 |
| 2 | 1 | 邻接点升序 2,3 → 走 2 | 1, 2 |
| 3 | 2 | 邻接点 1(已访问),4 → 走 4 | 1, 2, 4 |
| 4 | 4 | 邻接点 2(已访问),3 → 走 3 | 1, 2, 4, 3 |
| 5 | 3 | 邻接点 1,4 都已访问 → 回溯 | 结束 |
✅ 答案：1, 2, 4, 3（DFS 序列）
例题 3：2021 真题改编（Prim 最小生成树）
用 Prim 算法从顶点 1 开始求下面图的最小生成树，写出选边顺序和总权值。
边：1-2(2), 1-3(4), 2-3(1), 2-4(5), 3-4(3)逐步推演：
| 步骤 | 已选集合 | 候选边（权值） | 选中 |
|---|---|---|---|
| 1 | 1-2(2), 1-3(4) | 1-2(2) | |
| 2 | 1-3(4), 2-3(1), 2-4(5) | 2-3(1) | |
| 3 | 1-3(4,已选), 2-4(5), 3-4(3) | 3-4(3) | |
| 4 | 全部顶点 | 结束（n-1=3 条边） | — |
✅ 选边顺序：1-2(2) → 2-3(1) → 3-4(3)，总权值 2+1+3=6
例题 4：2022 真题改编（Kruskal 最小生成树）
用 Kruskal 算法求下面图的最小生成树，写出选边顺序。
边：1-2(2), 1-3(4), 2-3(1), 2-4(5), 3-4(3)逐步推演（按权值升序）：
| 步骤 | 边（权值） | 成环？ | 选中 |
|---|---|---|---|
| 1 | 2-3(1) | 否 | ✅ |
| 2 | 1-2(2) | 否 | ✅ |
| 3 | 3-4(3) | 否 | ✅（3 条边，结束） |
| 4 | 1-3(4) | 是（1-2-3 成环） | 不选 |
| 5 | 2-4(5) | 是 | 不选 |
✅ 选边顺序：2-3(1) → 1-2(2) → 3-4(3)，总权值 6（与 Prim 一致）
⑤ ⚠️【历年真题高频扣分坑】
| # | 陷阱 | 错误做法 | 正确做法 | 出处 |
|---|---|---|---|---|
| 1 | 连通图边数 | 9 顶点算 9 条 | 连通最少 n-1=8 条（树） | 2024 填空5 |
| 2 | 完全图 vs 连通图 | 无向完全图当连通图 | 完全图 n(n-1)/2，连通最少 n-1 | 经典 |
| 3 | 出度/入度混淆 | 弧的方向看反 | 出度=从 v 出发，入度=指向 v | 2024 简答4 |
| 4 | Σ度=2×边数 | 有向图也乘 2 | 无向图 Σ度=2e；有向图 Σ出=Σ入=e | 2024 简答4 |
| 5 | Prim 忘"跨边" | 选已选集合内部的边 | 只能选"已选→未选"的边 | 2021 大题45 |
| 6 | Kruskal 忘查环 | 选了成环的边 | 每选一条都要检查是否成环 | 2022 大题 |
| 7 | DFS/BFS 顺序 | 邻接点不排序 | 按题目要求（升序/降序）访问 | 2022 大题 |
| 8 | DFS 用队列 | 以为 DFS 用队列 | DFS 用栈（递归），BFS 用队列 | 经典 |
| 9 | 生成树边数 | n 顶点生成树 n 条边 | 生成树 = n 顶点 n-1 边 | 经典 |
| 10 | 邻接表边数 | 无向图邻接表边结点数=边数 | 无向图每条边存两次，结点数=2e | 经典 |
📌 最值钱的一条：第 5、6 条（Prim 跨边 + Kruskal 查环）是两道手算大题（2021、2022）的得分核心——画表逐步记录，一步都不许跳。
⑥ 📝【课后自测练习题】
1. 有 7 个顶点的连通图，最少需要（ ）条边（2024 真题风格）
A. 7 B. 8 C. 6 D. 21
2. 从顶点 1 开始 BFS（邻接点升序），下面图的访问序列是（ ）（2023 真题风格）
图：1-2, 1-3, 2-4, 3-4A. 1,2,3,4 B. 1,2,4,3 C. 1,3,2,4 D. 1,2,3
3. 用 Prim 算法从顶点 1 开始求最小生成树，选边顺序是（ ）（2021 真题风格）
边：1-2(1), 1-3(3), 2-3(2), 2-4(4), 3-4(5)A. 1-2 → 2-3 → 2-4 B. 1-2 → 2-3 → 3-4 C. 1-2 → 2-4 → 3-4 D. 2-3 → 1-2 → 3-4
4. 判断：DFS 借助队列实现，BFS 借助栈实现。（ ）（经典）
A. 正确 B. 错误
👆 点击展开参考答案与解析
第1题：C. 6
- 连通图最少 n-1=7-1=6 条边（2024 填空5 同款）
第2题：A. 1,2,3,4
- BFS：访问 1 → 出队 1，邻接 2,3 入队并访问 → 出队 2，邻接 4 访问 → 出队 3（无新点）→ 出队 4
- 序列 1,2,3,4（逐层展开）
第3题：A. 1-2 → 2-3 → 2-4
- Prim 逐步推演：
- {1} 候选跨边：1-2(1)、1-3(3) → 选 1-2(1)
- {1,2} 候选跨边：1-3(3)、2-3(2)、2-4(4) → 选 2-3(2)
- {1,2,3} 候选跨边：2-4(4)、3-4(5) → 选 2-4(4)
- 选边顺序：1-2(1) → 2-3(2) → 2-4(4)，总权值 1+2+4=7
- 解析：Prim 每一步只能选"已选集合到未选集合"的跨边，不能选集合内部的边
第4题：B. 错误
- DFS 用栈（递归），BFS 用队列
📝 原有闭卷真题挑战（保留原内容）
（点击下方空白查看答案）
1. 无向完全图 n个顶点，有多少条边？
2. 邻接矩阵和邻接表各自适用于什么场景？
3. 有8个顶点的连通图至少需要几条边？
4. 图的DFS和BFS分别借助什么数据结构实现？
5. 连通图的生成树有几个顶点、几条边？👆 点击展开答案
- n(n-1)/2 条边
- 邻接矩阵→稠密图；邻接表→稀疏图
- 7条（n个顶点连通至少n-1条边，形成树）
- DFS用栈（递归），BFS用队列
- n个顶点、n-1条边
📖 教材习题对照
| 教材习题 | 知识点 | 难度 |
|---|---|---|
| 习题7.1~7.2 | 图的基本术语 | ⭐⭐ |
| 习题7.4~7.5 | 邻接矩阵与邻接表 | ⭐⭐⭐ |
| 习题7.7~7.8 | DFS与BFS | ⭐⭐⭐ |
| 习题7.10~7.14 | 最小生成树/最短路径 | ⭐⭐⭐⭐ |
对应教材：严蔚敏《数据结构》C语言版 第2版 → 第7章 图 对应考试大纲：考点17 — 图
📺 配套视频
复习到本考点 → 先看视频补讲，再刷上面「闭卷挑战」。