第一章 图的基本概念与性质 #

1.1 图的定义与分类 #

1.1.1 无向图与有向图 #

1.1.2 简单图与多重图 #

1.1.3 完全图与补图 #

1.1.4 连通图与强连通图 #

1.1.5 加权图与无权图 #

1.2 图的基本术语 #

1.2.1 顶点、边、度 #

1.2.2 路径、回路、环 #

1.2.3 子图、生成子图 #

1.2.4 邻接矩阵与邻接表 #

1.3 图的遍历算法 #

1.3.1 深度优先搜索(DFS) #

1.3.2 广度优先搜索(BFS) #

1.3.3 遍历算法的应用 #

第二章 最短路径问题 #

2.1 单源最短路径 #

2.1.1 Dijkstra算法 #

2.1.2 Bellman-Ford算法 #

2.1.3 SPFA算法 #

2.2 多源最短路径 #

2.2.1 Floyd-Warshall算法 #

2.2.2 Johnson算法 #

2.3 特殊图的最短路径 #

2.3.1 有向无环图(DAG)的最短路径 #

2.3.2 网格图的最短路径 #

2.3.3 负权边处理 #

第三章 最小生成树 #

3.1 生成树基本概念 #

3.1.1 生成树定义与性质 #

3.1.2 最小生成树应用场景 #

3.2 经典算法 #

3.2.1 Prim算法 #

3.2.2 Kruskal算法 #

3.2.3 Boruvka算法 #

3.3 进阶问题 #

3.3.1 次小生成树 #

3.3.2 最小瓶颈生成树 #

3.3.3 度限制最小生成树 #

第四章 网络流问题 #

4.1 最大流问题 #

4.1.1 Ford-Fulkerson方法 #

4.1.2 Edmonds-Karp算法 #

4.1.3 Dinic算法 #

4.2 最小割问题 #

4.2.1 最大流最小割定理 #

4.2.2 最小割算法 #

4.3 费用流问题 #

4.3.1 最小费用最大流 #

4.3.2 费用流算法 #

第五章 匹配问题 #

5.1 二分图匹配 #

5.1.1 匈牙利算法 #

5.1.2 Hopcroft-Karp算法 #

5.1.3 二分图最大权匹配 #

5.2 一般图匹配 #

5.2.1 开花算法 #

5.2.2 带花树算法 #

5.3 稳定婚姻问题 #

5.3.1 Gale-Shapley算法 #

5.3.2 稳定匹配的应用 #

第六章 图的连通性 #

6.1 连通分量 #

6.1.1 强连通分量 #

6.1.2 双连通分量 #

6.1.3 连通分量算法 #

6.2 割点与桥 #

6.2.1 割点判定算法 #

6.2.2 桥判定算法 #

6.2.3 应用场景 #

6.3 2-SAT问题 #

6.3.1 2-SAT建模 #

6.3.2 2-SAT求解算法 #

第七章 欧拉图与哈密顿图 #

7.1 欧拉图 #

7.1.1 欧拉回路与欧拉路径 #

7.1.2 欧拉图判定定理 #

7.1.3 欧拉回路算法 #

7.2 哈密顿图 #

7.2.1 哈密顿回路与路径 #

7.2.2 哈密顿图判定 #

7.2.3 旅行商问题 #

第八章 平面图与着色问题 #

8.1 平面图 #

8.1.1 平面图定义与性质 #

8.1.2 欧拉公式 #

8.1.3 平面图判定 #

8.2 图着色 #

8.2.1 顶点着色 #

8.2.2 边着色 #

8.2.3 四色定理 #

8.3 独立集与团 #

8.3.1 最大独立集 #

8.3.2 最大团问题 #

8.3.3 应用实例 #

第九章 动态规划在图论中的应用 #

9.1 状态压缩DP #

9.1.1 旅行商问题的DP解法 #

9.1.2 哈密顿路径计数 #

9.2 树形DP #

9.2.1 树上最长路径 #

9.2.2 树的最大独立集 #

9.2.3 树的重心与直径 #

9.3 图上的DP优化 #

9.3.1 拓扑排序与DP #

9.3.2 记忆化搜索 #

9.3.3 状态转移优化 #

第十章 高级图论算法 #

10.1 支配集与覆盖集 #

10.1.1 最小支配集 #

10.1.2 最小点覆盖 #

10.1.3 最小边覆盖 #

10.2 LCA与RMQ #

10.2.1 最近公共祖先 #

10.2.2 区间最值查询 #

10.2.3 应用实例 #

10.3 图的分解 #

10.3.1 树分解 #

10.3.2 路径分解 #

10.3.3 块分解 #