主题
第五章 图结构及其存储与遍历
📖 ⏱️ 预计阅读时长 1 分钟 👑 会员专属
1. 图的基本概念
图结构比树更一般，因为树可以看作一种特殊的图，而图能够描述任意复杂的多对多关联。图由顶点集合和边集合组成，常记作 G = (V, E)。图用于描述对象之间复杂的多对多关系。
图可以进一步分类：
- 无向图：边没有方向。
- 有向图：边有起点和终点。
- 带权图：边带有权值，如距离、费用、时间等。
- 稠密图与稀疏图：边的多少不同，适合的存储方式也不同。
2. 图的基本术语
- 顶点的度：与该顶点关联的边数。
- 入度、出度：有向图中分别表示进入和离开某顶点的边数。
- 路径：从一个顶点到另一个顶点经过的边序列。
- 连通图：任意两个顶点之间都存在路径。
- 生成树：连通图中包含全部顶点且无环的子图。
- 环：从某个顶点出发又回到自身的路径。
图之所以重要，是因为许多真实系统天然就是图结构。例如社交网络中的用户与关注关系，地图中的城市与道路关系，编译系统中的模块依赖关系，课程系统中的先修关系等。
3. 图的存储表示
3.1 邻接矩阵
邻接矩阵用二维数组表示顶点之间是否相连或边的权值。
其特点是：
- 判断两点是否相邻很快，通常为
O(1)。 - 空间复杂度通常为
O(|V|^2)。 - 适合稠密图。
邻接矩阵的优势来自“空间换时间”的思想。因为它直接用二维表记录点与点之间是否相连，所以判断一条边是否存在非常快；但也正因如此，即便某些顶点之间根本没有边，也必须为其预留存储位置，因此当图很稀疏时会显得浪费。
3.2 邻接表
邻接表为每个顶点维护一个链表或动态表，记录与其相邻的顶点。
其特点是：
- 空间复杂度通常为
O(|V| + |E|)。 - 更适合稀疏图。
- 遍历某个顶点的全部邻居更高效。
邻接表的优势来自“只存真实存在的边”。对于边远少于顶点平方数量的稀疏图，它能显著降低空间开销，并使得遍历相邻点更自然。因此，在很多实际系统中，邻接表比邻接矩阵更常见。
3.3 两种存储方式比较
| 比较项目 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间占用 | `O( | V |
| 判断是否存在边 | 快 | 较慢 |
| 遍历邻居 | 对稀疏图较浪费 | 更高效 |
| 适用场景 | 稠密图 | 稀疏图 |
4. 图的遍历
4.1 广度优先搜索（BFS）
BFS 按层扩展节点，通常借助队列实现。它适合处理：
- 无权图最短路径。
- 层次遍历。
- 连通分量搜索。
若图采用邻接表存储，则 BFS 的时间复杂度通常为 O(|V| + |E|)；若采用邻接矩阵存储，则在遍历邻接点时常表现为 O(|V|^2)。这说明图算法的效率与图的存储方式密切相关。
4.2 深度优先搜索（DFS）
DFS 沿一条路径尽量深入，通常借助递归或显式栈实现。它适合处理：
- 回溯问题。
- 连通性分析。
- 拓扑排序。
- 强连通分量、桥和割点等结构分析。
在邻接表表示下，DFS 的时间复杂度同样通常为 O(|V| + |E|)。BFS 与 DFS 的差别不在于“谁更高级”，而在于搜索顺序不同，因此适合解决的问题类型也不同。
4.3 BFS 与 DFS 的直观区别
- BFS 像水波一样向外一层层扩散，因此更适合求最短层数和最少边数。
- DFS 像沿着一条路径不断深入，因此更适合回溯、枚举和结构分析。
很多图问题并不是“必须选一个算法”，而是要先判断题目需要按层推进，还是需要深入搜索。
5. 图结构的典型应用
- 地图导航与路径规划。
- 社交网络关系分析。
- 课程先修关系建模。
- 网络路由与通信拓扑设计。
- 编译系统中的依赖分析。
图结构的价值在于：它能够表示比树更一般、更复杂的关联关系，因此在工程系统和算法设计中极其重要。
6. 图算法与数据结构的关系
图本身只是表示关系的方法，而真正让图“动起来”的，是围绕它展开的一系列算法。例如最短路径算法、最小生成树算法、拓扑排序、强连通分量算法等，都是建立在图结构之上的。进一步学习算法时，会发现图不仅是一个知识点，更是一类问题建模语言。
7. 学习图结构时的重点
7.1 先分清“表示”与“算法”
初学图结构时，很多人容易把“邻接矩阵、邻接表”和“BFS、DFS、最短路径算法”混在一起。实际上前者属于存储表示，后者属于运行在图结构之上的算法。必须先理解图怎样存，再理解图怎样算。
7.2 注意图和树的区别
树中不存在环，且通常强调单根层次关系；图则可以有环，也可以没有统一根节点。很多在树中成立的结论，到了图中就未必成立。因此，不能把图简单理解为“节点更多的树”。
7.3 注意有向与无向、带权与无权的区别
图问题中，边是否有方向、边是否带权，往往直接决定算法选择。例如无权图最短路径通常可以使用 BFS，而带正权图则更常使用 Dijkstra。若忽略这些基本条件，就很容易在解题和建模时出错。
8. 本章小结
图结构用于描述复杂关联关系，是数据结构课程从“线性”和“层次”走向“网络化”的关键一步。学习本章的重点，不只是记住顶点、边、邻接表等术语，更重要的是理解图为何需要不同存储方式，以及 BFS 和 DFS 为什么会成为众多图算法的基础。