# 图

> 计算机科学 · CIE A-Level 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u10-graphs/

图是用于建模实体之间关系的灵活非线性数据结构。本指南涵盖CIE 9618考试要求的核心术语、存储方法、遍历算法和常见考点。

**先修:** [非线性数据结构](https://www.owlsprep.com/zh/study/cie-9618-u10-non-linear-data-structures/); [树](https://www.owlsprep.com/zh/study/cie-9618-u10-trees/)

## 学习目标

- 定义图的核心术语，区分常见的图类型
- 比较邻接矩阵和邻接表两种图存储方法
- 实现和跟踪BFS与DFS图遍历算法
- 明确图在实际问题中的合适应用场景

## 核心术语与图类型

**图** — 一种非线性数据结构，由有限个顶点（节点）集合和有限条连接顶点对的边集合组成。

*记法:* $G = (V, E)$

*例:* 社交网络：用户是顶点，好友关系是边。

图根据边的性质和连通性分类，以下是考试中最常考查的常见分类：

- **有向 vs 无向**：有向图的边是单向的，无向图的边是双向的。
- **带权 vs 不带权**：带权图为每条边分配一个数值权值，不带权图则没有。
- **连通 vs 不连通**：连通图中任意一对顶点之间都存在路径；不连通图中至少存在两个顶点之间没有连接路径。
- **有环 vs 无环**：有环图至少包含一条起点和终点相同的路径；无环图不存在环。

**例题:** 对下列图进行分类：城市间航线地图，每条航线标注了公里单位距离，且可以双向通航。

1. 第一步，检查边方向：航线可以双向飞行，因此该图是无向图。
2. 第二步，检查边权：每条路线都有距离值，因此该图是带权图。
3. 假设所有城市之间都可到达，因此该图是连通图。最终分类：连通无向带权图。

> **考试提示:** 当要求对图进行分类时，务必检查全部三个性质（方向、权值、连通性），每个正确分类都会给分。

## 图表示：存储方法

**方法对比**

图在内存中通常使用以下两种常见方法存储，CIE考试经常考查二者的比较：

- **邻接矩阵** — 大小为$|V| \times |V|$的二维数组，如果顶点$i$和顶点$j$之间存在边，则$matrix[i][j]$存储1（或边权），否则存储0（或空）。
  - 优点: O(1)时间即可检查两个顶点之间是否存在边; 对小图来说实现简单
  - 缺点: 对于稀疏图会浪费空间; 无论边数多少，空间复杂度都是O(|V|²)

- **邻接表** — 一个由列表组成的数组，每个索引$i$代表一个顶点，索引$i$处的列表存储所有和该顶点相连的顶点（以及边权）。
  - 优点: 对于稀疏图空间效率更高（大多数实际场景的图都是稀疏图）; O(|V| + |E|) 空间复杂度
  - 缺点: 边存在性检查更慢（需要遍历邻接表）

**例题:** 写出下列4顶点无向不带权图的邻接矩阵：边为(0,1), (0,2), (1,2), (2,3)。

1. 4个顶点对应4×4矩阵，无向图的矩阵是对称的，结果如下：
2. $$\begin{bmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
0 & 0 & 1 & 0
\end{bmatrix}$$
3. 对角线元素都是0，因为该图不存在自环。

*计算器:* forbidden

## 图遍历算法

**图遍历** — 按系统顺序访问（探索）图中所有顶点和边的过程。

*例:* 用于寻找节点之间的路径、检查连通性以及搜索特定值。

CIE A-Level考查两种核心遍历算法：广度优先搜索（BFS）和深度优先搜索（DFS）。

- **广度优先搜索（BFS）**：先探索当前深度层的所有顶点，再进入下一个深度层的顶点。使用队列跟踪接下来要访问的顶点。
- **深度优先搜索（DFS）**：沿着单条路径尽可能深入探索，再回溯探索其他路径。使用栈（或递归）跟踪接下来要访问的顶点。

**例题:** 列出前一个例子中4顶点图从顶点0出发的BFS访问顶点顺序。

1. 初始化队列，将顶点0入队，标记0已访问。出队0，加入访问顺序：
2. $$Visited = [0]$$
3. 将0的所有未访问邻居（1、2）入队，标记为已访问。出队1，加入访问顺序：
4. $$Visited = [0, 1]$$
5. 1的所有邻居都已访问。出队2，加入访问顺序：
6. $$Visited = [0, 1, 2]$$
7. 将未访问邻居3入队。出队3，加入访问顺序。遍历完成：
8. $$Final BFS order = [0, 1, 2, 3]$$

**概念自测**

1. DFS遍历使用哪种数据结构？

   - 队列
   - 栈
   - 数组
   - 链表

   *答案:* 栈

   *解析:* 回答正确！DFS使用栈跟踪接下来要探索的路径，而BFS使用队列。

## 图的实际应用

CIE考试经常要求你解释为什么图适合给定问题。图的常见应用包括：

- 社交网络（对用户和连接/好友关系建模）
- 导航系统（对地点和道路/航线连接建模）
- 项目进度管理中的任务依赖图
- 网页图建模（网页和超链接）
- 电路设计（对组件和连接建模）

**例题:** 解释为什么图适合给水管网建模。

1. 图可以将水管接头建模为顶点，水管本身建模为接头之间的边。
2. 管道直径、流量等额外属性可以存储为边的权值。
3. 图遍历算法可以找到任意两个接头之间的路径，用于流量分析和泄漏检测。没有其他常用数据结构能像图一样灵活地对实体之间的任意连接建模。

> **考试提示:** 当被问及为什么图适合某个场景时，务必在答案中明确说明顶点和边分别代表什么，才能拿到满分。

## 常见错误

- **错误做法:** 认为所有邻接矩阵都是对称的
  - 原因: 对称性仅适用于无向图，有向图的邻接矩阵不是对称的
  - 正确做法: 讨论矩阵对称性之前，先检查图是有向还是无向
- **错误做法:** 混淆BFS和DFS使用的数据结构：认为BFS用栈，DFS用队列
  - 原因: 这是考试中最常见的错误之一，会白白丢掉1-2分
  - 正确做法: 记住：BFS（广度）用队列，DFS（深度）用栈
- **错误做法:** 认为邻接表总是比邻接矩阵更高效
  - 原因: 效率取决于图的密度；对于稠密图，邻接矩阵更高效
  - 正确做法: 根据密度比较效率：稠密图用邻接矩阵，稀疏图用邻接表
- **错误做法:** 遍历过程中忘记标记顶点为已访问
  - 原因: 在遍历环图时，未标记顶点会导致无限循环
  - 正确做法: 遍历过程中始终维护一个已访问数组或集合，跟踪已探索的顶点

## 速查表

| 类别 | 项 | 核心性质 |
| --- | --- | --- |
| 存储 | 邻接矩阵 | $\|V\| \times \|V\|$ 数组，O(1)边检查 |
| 存储 | 邻接表 | 列表数组，稀疏图空间高效 |
| 遍历 | BFS | 队列，层序搜索，无向图最短路径 |
| 遍历 | DFS | 栈/递归，路径优先搜索，环检测 |
| 图类型 | 有向 | 边单向，邻接矩阵不对称 |
| 图类型 | 无向 | 边双向，邻接矩阵对称 |
| 图类型 | 带权 | 边带有关联数值权值 |
| 图类型 | 不带权 | 边没有额外存储值 |

## 下一步

图是基础非线性数据结构，是计算机科学中许多高级算法的基础，包括CIE 9618考查的Dijkstra等最短路径算法和最小生成树算法。掌握图的基础对试卷1的选择题、理论题，以及要求实现图或遍历算法的编程实践题都至关重要。理解存储方法和遍历方法之间的权衡，能帮助你为任意问题选择正确解决方案，并为基于这些核心概念的更高级图主题做好准备。

- [树](https://www.owlsprep.com/zh/study/cie-9618-u10-trees/)
- [哈希表](https://www.owlsprep.com/zh/study/cie-9618-u10-hash-tables/)
- [编程](https://www.owlsprep.com/zh/study/cie-9618-u11-overview/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u10-graphs/