第 11 章 · 树与图论

图论是 CSP-S 第二轮的必考内容：存图 → 遍历 → 最短路 → 最小生成树 → 拓扑排序，这条工具链能解决大半个提高级的图论题。

学习目标

• 掌握邻接矩阵、邻接表（vector 建图）两种存图方式
• 熟练写出图的 DFS / BFS 遍历
• 掌握 Dijkstra（堆优化）、SPFA / Bellman-Ford、Floyd 三类最短路及适用场景
• 掌握 Kruskal、Prim 求最小生成树
• 理解拓扑排序及其在 DAG 上的应用
• 了解树的直径、最近公共祖先（LCA）的概念

课程规划（编写中）

• 树与图的基本概念、存储
• 图的遍历
• 最短路三剑客
• 最小生成树
• 拓扑排序与 DAG
• 树上的经典问题

建图模板

提高 级图论题 80% 的代码以同一个「建图 + 遍历」骨架开头，先把模板写熟。