第六章 图、遍历与最短路径

---

1. 为什么图是数据结构课程的分水岭

线性结构处理的是一对一顺序，树结构处理的是层次关系，而图结构处理的是最一般的连接关系。到了图这一章，数据结构课程真正进入“复杂关系建模”的阶段。

图可以表示：

1. 城市与道路网络。
2. 社交关系。
3. 课程先修依赖。
4. 互联网拓扑。
5. 工作流和状态转移。

如果说树是“有约束的图”，那么图就是解除父子限制后的更一般模型。

2. 图的基本概念

图通常记作 G = (V, E)：

1. V 是顶点集合。
2. E 是边集合。

图可以进一步分为：

1. 无向图。
2. 有向图。
3. 带权图。
4. 稀疏图与稠密图。

3. 图的两种核心存储方式

3.1 邻接矩阵

3.2 邻接表

4. Go 中的邻接表表示

5. 深度优先搜索 DFS

5.1 递归版 DFS

6. 广度优先搜索 BFS

6.1 BFS 为什么能求无权图最短路

7. 拓扑排序：处理依赖关系

7.1 Kahn 算法

8. 最短路径：从 BFS 到 Dijkstra

8.1 使用小根堆实现 Dijkstra

9. 并查集与图的连通性

10. 图这一章最容易犯的错误

11. 本章小结

12. 继续深入