13.4.1 图知识点概述
图是数据结构中最自由也最复杂的一类。线性表是一对一，树是一对多，图是多对多；它没有固定根节点，也没有天然层次。课程把图的学习压缩成四类考点：定义与存储、遍历、拓扑排序、最小生成树与最短路径。
图模块学什么
| 内容 | 学习目标 | 考试状态 |
|---|---|---|
| 图的定义 | 顶点、边、弧、路径、连通、完全图 | 常考概念判断 |
| 图的存储 | 邻接矩阵、邻接表 | 常结合有向/无向、稀疏/稠密考 |
| 图的遍历 | 深度优先、广度优先 | 常判断遍历序列是否合法 |
| 拓扑排序 | 有向无环图的线性化 | 常考入度为 0 的删除过程 |
| MST/最短路径 | Prim、Kruskal、Dijkstra、Floyd | 目前多考算法名称与策略 |
图和树的差别
| 比较项 | 树 | 图 |
|---|---|---|
| 关系 | 层次关系，一对多 | 多对多 |
| 根节点 | 有根或可指定根 | 一般没有天然根 |
| 回路 | 树无回路 | 图可以有回路 |
| 遍历 | 先序、中序、后序、层序 | DFS、BFS |
| 存储 | 孩子/双亲/二叉链表 | 邻接矩阵/邻接表 |
树可以看作图的一种特殊情况：连通且无回路。
做图题先问四件事
mermaid
flowchart TD
A["拿到图题"] --> B["有向还是无向？"]
B --> C["是否带权？"]
C --> D["是否连通/是否有环？"]
D --> E["顶点多边少还是边多？"]
E --> F["选择存储、遍历或路径算法"]本节例题
关于图这种数据结构，下列说法正确的是：
自查清单
- 能否说明图为什么比树更一般？
- 能否区分图的遍历与二叉树遍历？
- 能否在做题前先判断方向、权值、连通性和稠密程度？