终于到图（Graph）了——最通用的数据结构：城市路网 🗺️、社交关系 👥、网页链接、任务依赖，万物皆可图。前 12 章学的树、堆、哈希表、并查集，本章全部上阵。
🕸️ 图的基本词汇
图 = 顶点（vertex）集合 + 边（edge）集合，边描述顶点间的成对关系：
- 无向图：好友关系（你我是朋友，双向）；
- 有向图（digraph）：关注关系（我关注你，你未必关注我）；
- 带权图：每条边带一个代价（路程、时间、费用）；
- 度：一个顶点连接的边数；路径、环、连通……
🗄️ 三种存储方案
| 结构 | 空间 | 查「u,v 相邻吗」 | 遍历 u 的邻居 | 适合 |
|---|---|---|---|---|
| 边列表 | O(m) | O(m) ❌ | O(m) | 很少查邻接 |
| 邻接矩阵 | O(n²) | O(1) 🏆 | O(n) | 稠密图 |
| 邻接表 | O(n+m) 🏆 | O(deg(u)) | O(deg(u)) 🏆 | 稀疏图（现实常态） |
现实中的图几乎都是稀疏图（n² 条可能的边只存在少数几条），邻接表（每个顶点挂一个邻居链表）是默认选择。
🚶 两种遍历：潜水员 vs 涟漪
DFS（深度优先）：一条路走到黑，走不通就回头。用栈（递归调用栈）。副产品丰富：
- 拓扑排序：DFS 完成时间的逆序 = DAG 的合法任务顺序（选课先修、编译依赖 📚）；
- 找环、连通分量（DFS 几次就有几个分量）；
- 强连通分量（有向图里互相可达的团伙）：跑两遍 DFS 的 Kosaraju 算法。
BFS（广度优先）：像水波纹一圈圈扩散。用队列（第 5 章！）。副产品：无权图最短路径——第一次到达某点的层数就是最短跳数。面试名场面：「社交网络里我和某明星的最短关系链」= BFS ⭐。
两者时间都是 O(n + m)：每个顶点入栈/队一次，每条边扫一次——扎实又优雅。
🗺️ 最短路径：Dijkstra 算法
边带权时，BFS 失效（跳数少 ≠ 代价小）。Dijkstra：贪心 + 优先队列（第 8 章！积木复用 🧱）：
- 起点距离 0，其余 ∞，全部丢进优先队列；
- 每次取出当前距离最小的顶点 u（它已确定最优，不可能再被绕路改善——贪心的正确性来源）；
- 用 u 松弛它的邻居：
dist[v] = min(dist[v], dist[u] + w(u,v))，更新过的入队； - 重复到取完。
总时间 O((n+m) log n)。⚠️ 限制：边权不能为负（贪心前提崩塌），负权图要用 Bellman-Ford。
🌉 最小生成树（MST）
用 n-1 条边把 n 个顶点连成一片，总权重最小。两大贪心算法：
- Kruskal：边按权重从小到大排序，逐条尝试加入，用并查集（第 11 章！）判环——不成环就要，成环跳过；
- Prim：从一点出发，像滚雪球一样，每次把「离树最近的顶点」吸进来——又是优先队列的主场。
两个都是 O(m log n) 级别，一个爱稀疏图一个爱稠密图。光缆铺设、电网规划、聚类分析，全是 MST 的地盘 🌐。
🎯 本章通关清单
- [ ] 三种图存储结构的空间与查询代价对比
- [ ] 说出 DFS 用栈 / BFS 用队列，各举两个应用
- [ ] 手工对一个小图跑 Dijkstra，解释「为什么取出时就是最优」
- [ ] Kruskal 和 Prim 分别用了前面哪两章的数据结构？
到此，课内武器库全部集齐 🎓。最后一章面向真实硬件：当数据大到内存装不下怎么办？——B-Tree 登场 💾