本讲定位：图论系列的总纲与路线图。图论是 CSP-J/S 复赛除 DP 之外的第二大板块，也是唯一一个”概念多、模板多、变形多”三者同时成立的专题——学生真正的困难从来不是背不下 Dijkstra，而是看到一道题不知道它是图论题，以及知道是图论题却选错了工具。本系列把整块图论拆成 16 讲正篇 + 2 篇番外，每讲只解决一个可独立训练的问题，用统一的一句话回答”这一讲的工具在什么信号下该被想起来”。
前置知识：数组、循环、递归、结构体、
vector；栈与队列的使用（见顶层06-linear-structures.md）；会读复杂度记号。第 12 讲要用到差分思想（见顶层07-prefix-sum-difference.md）。不需要任何图论基础。适合对象：CSP-J 复赛已过普及组算法关（会 DFS/BFS 暴搜、会排序），目标 CSP-J 一等或 CSP-S 复赛。标 ⭐ 的内容为 CSP-S 层，标 ⭐⭐ 的为选修/超纲拓展，第一轮可整节跳过。
图论既装不进 cspj-series/（那是初赛专用，只讲选择/判断/阅读程序/完善程序），也不该塞进 dp-series/（已 01–08 完结），更不能压成顶层通用线的一两讲——它的体量相当于一整个 dp-series。所以单开 graph-series/，独立编号 01–16，与顶层通用算法线（05 高精度、06 线性结构、07 前缀和与差分、08 二分……）并行推进，两条线互不干扰、互相引用。
与已有系列的分工（写正文时严格遵守，避免重复劳动）：
| 已有内容 | 在哪里 | 本系列怎么处理 |
|---|---|---|
| 树形 DP | dp-series/05-tree-dp.md |
第 11 讲只讲树的结构性质（直径、重心、DFS 序），转移方程细节指路 05 讲 |
| DAG 上的 DP | dp-series/08-dag-dp.md |
第 04 讲只讲拓扑序怎么求出来和”为什么 DAG 才能递推”，状态设计指路 08 讲 |
| 状压 DP | dp-series/06-bitmask-dp.md |
第 16 讲讲哈密顿路时只做联系，不重讲状压 |
| 栈、队列、单调队列 | 06-linear-structures.md |
直接当前置引用，本系列不重讲容器 |
| 序列差分 | 07-prefix-sum-difference.md |
第 12 讲树上差分从”序列差分搬到树上”切入，明确类比 |
| 二分答案 | 顶层 08 讲（待写） | 第 08 讲用到”二分 + 最短路判定”时交叉引用 |
| 线段树、树状数组、树链剖分 | 顶层数据结构线（待写） | 第 12 讲末尾只给指路，不展开 |
难度层含义：J = CSP-J 复赛主线，必须掌握；J⭐ = CSP-J 偶见/进阶；S = CSP-S 复赛常考；S⭐⭐ = 超出 CSP-S 常考范围的选修。
| # | 标题 | 一句话主线 | 难度层 | 代表题 |
|---|---|---|---|---|
| 01 | 图的存储与第一次遍历 | 先把”图”变成数组，再走通它 | J | B3643、P5318 |
| 02 | 图的遍历：性质与陷阱 | 一个 vis 数组换来 $O(n+m)$，代价是什么 |
J | P1443、P1141、P3916 |
| 03 | BFS 的进阶形态 | 状态即结点：多源、01-BFS、状态图搜索 | J⭐ / S | P1379 |
| 04 | 拓扑排序与 DAG | 有向无环图上”谁先谁后”的唯一正确顺序 | J | B3644、P4017、P1983 |
| 05 | 最短路（一）：Dijkstra | 非负权图上的贪心 + 堆 | J | P3371、P4779 |
| 06 | 最短路（二）：Bellman-Ford、SPFA 与负环 | 松弛的本质，以及负权把贪心打破之后 | J / S | P3385 |
| 07 | 最短路（三）：Floyd 与全源最短路 | 三重循环其实是一个 DP | J / S | P6175、P1119 |
| 08 | 最短路（四）：建模与变形 | 难的不是跑最短路，是把题目建成图 | S | P4568、P1144、P1073 |
| 09 | 并查集 | 只回答一个问题：这两点连通吗 | J | P3367、P1525 |
| 10 | 最小生成树 | 用最小代价把所有点连起来 | J / S⭐ | P3366、P4180、P1967 |
| 11 | 树上问题基础 | 树是最简单的图：直径、重心、DFS 序 | J / S | B4016、P1364、P4408 |
| 12 | LCA、倍增与树上差分 | 把序列上的前缀和差分搬到树上 | S | P3379、P3128、P2680 |
| 13 | 强连通分量与缩点 | 把每个环团缩成一个点，有向图就变成了 DAG | S | P3387、P2341 |
| 14 | 割点、割边与双连通分量 | 哪个点/哪条边一删就断 | S | P3388、P2860 |
| 15 | 二分图 | 染两种颜色能不能成功，以及匹配 | S | P1330、P3386 |
| 16 | 欧拉路径与欧拉回路 | 一笔画的充要条件 | S | P7771、P2731 |
| 番外 A | 差分约束与 2-SAT | 把不等式组和布尔约束翻译成图 | S⭐⭐ | P1993、P4782 |
| 番外 B | 网络流入门 | 最大流最小割，以及匹配的另一种视角 | S⭐⭐ | P3376 |
点/边/度/权、有向与无向、简单图、自环与重边、连通与连通块、稀疏图与稠密图、树是特殊的图。三种存图法：邻接矩阵（$O(n^2)$ 空间，$O(1)$ 查边，适合 $n \le 1000$ 与 Floyd）、vector 邻接表（好写，首选）、链式前向星（head/nxt/to/w 四数组，快且省，为网络流的成对边编号 i^1 埋伏笔）。核心表格：三种存法在”查两点是否有边”“枚举某点所有出边”“空间”三项上的对比，以及数据范围到存法的选择流程。外加第四种情况：网格图是隐式图，用 dx/dy 方向数组直接算邻居，根本不存。 本讲后半给出 DFS 与 BFS 两份最简模板（vis 一句话带过，深入留给第 02 讲），让学生学完当场能做题；例题 P5318 把”选存法 → 建图 → 遍历”完整走一遍，同时演示为什么”字典序最小”这个要求让 vector 完胜前向星。高频错误：无向图忘记存两条边、head 初始化为 $-1$ 与 $0$ 的两套写法混用、边数组开小（无向图要 $2m$）、两次遍历共用一个 vis。
不重复第 01 讲的模板，只讲”为什么对”和”哪里会悄悄错”。 先把 vis 的意义讲透——它把”枚举所有路径”压成”枚举所有点”，这是 $O(n+m)$ 的来源，代价是只保留了每个点的一次访问（后面”DFS 求不出最短路”的根子就在这）。然后是三个陷阱，每个配实测：vis 的标记时机（入队 vs 出队，稠密图上入队次数暴涨 162 倍，且无条件覆盖 dis 的版本直接错）、递归 DFS 爆栈（8 MB 约 25 万层）、DFS 冒充最短路（5000 组错 1982 组）。正面结论一条：“层数即无权最短路”的归纳法证明，务必连同”每条边长度为 1”这个前提一起记（第 03、05 讲全靠打破它推进）。三个套路：洪水填充的”圈内难判就从圈外灌”（P1162）、连通块预处理（P1141）、反向建图（P3916：正着做要 $n$ 次 DFS，反着做一次搞定）。
多源 BFS（所有源点一起入队，等价于建超级源点）；01-BFS（边权只有 0/1 时用 deque，0 边压前 1 边压后，$O(n+m)$ 顶替 Dijkstra）；双向 BFS；状态图 BFS——把”局面”当结点、“一次操作”当边，用 map/康托展开判重（P1379 八数码）。收尾一句话：“当边权不全相等时 BFS 就错了，把队列换成优先队列，就是下一讲的 Dijkstra”。