OI Wiki 学习地图 · 第 4 章 进阶路径二:图论

OI Wiki 学习地图 · 第 4 章 进阶路径二:图论

章节摘要:本章讲图论(docs/graph/ 61篇)。从基础(最短路 Dijkstra/SPFA、最小生成树 Kruskal/Prim)到进阶网络流与连通性。网络流 docs/graph/flow/max-flow.md 是本章难点(★),做慢节奏精讲(最大流/Dinic/费用流/二分图匹配)。本章共 3 节,前置依赖为第 1-3 章。

路径坐标

进阶(本章) → 省选(网络流变体)

学习目标

1. 掌握最短路(Dijkstra/Bellman-Ford/SPFA/Floyd)。
2. 掌握最小生成树(Kruskal/Prim)。
3. 理解网络流最大流Dinic(★)。
4. 理解连通分量(Tarjan)与二分图匹配。

子章节导航

01 最短路与最小生成树(对应 docs/graph/)

图的存储(邻接矩阵/链式前向星);最短路(Dijkstra堆优化/Bellman-Ford/SPFA判负环/Floyd全源);最小生成树(Kruskal+并查集/Prim);拓扑排序;引用 docs/graph/ 基础页。

02 网络流难点精讲 ★

最大流 docs/graph/flow/max-flow.md(FF方法/EK/Dinic分层图/当前弧优化);费用流(MCMF);二分图匹配(匈牙利/KM);网络流建模技巧(拆点/超级源汇);慢节奏精讲Dinic。

03 连通分量与二分图(对应 docs/graph/)

强连通分量(Tarjan/Kosaraju);双连通分量(割点/桥);2-SAT;欧拉回路;二分图判定与匹配;引用 docs/graph/ 连通性页。

前置知识与后续延伸

前置:第1-3章(并查集用于MST)。后续:第6章数学(图论与组合);第7章。