图

本章在选择题中考察，也有可能作为一道概念题在大题中出现，需要熟练掌握图的存储结构（代码实现），并且要求在概念上理解图的应用，要求能够手工模拟。

学习思维导图：

## 图

### 图的基本概念

### 图的存储结构及基本操作

- 邻接矩阵
- 邻接表
- 邻接多重表、十字链表

### 图的遍历

- 深度优先搜索
- 广度优先搜索

### 图的基本应用

- 最小生成树
- 最短路径
- 拓扑排序
- 关键路径

---

从图的性质选择算法

图题先把“顶点表示什么、边表示什么、边是否有方向和权值”写清，再选择存储和算法：

已知性质或目标	首先考虑	关键前提
顶点较少、需要快速判两点是否相邻	邻接矩阵	空间为 $O(V^2)$
边较少、需要遍历所有邻接点	邻接表	访问某两点是否相邻未必是常数时间
求连通分量、可达性或层数	DFS / BFS	无权最短路使用 BFS 的层次性质
连通无向带权图的最小连通代价	Prim / Kruskal	最小生成树不是任意两点的最短路径
有向无环图的先后约束	拓扑排序 / 关键路径	出现环时不存在完整拓扑序

算法过程题应始终标出“已访问集合、候选边或队列/栈、当前距离或入度”。这些状态正是解释算法为何不会漏点、不会重复选边，以及何时发现环或不连通图的依据。

学习目录

定义

算法和应用