第1章 图 1
1.1图的定义和术语 1
1.1.1图的定义 1
1.1.2特殊的图 2
1.1.3有向图和无向图 3
1.1.4路径与连通 3
1.2图的存储结构 4
1.2.1邻接矩阵 4
1.2.2前向星 5
1.2.3邻接表 7
1.3图的遍历 13
1.3.1图的深度优先遍历 13
1.3.2图的宽度优先遍历 14
1.3.3图的拓扑排序 15
1.3.4图的可行遍性 20
第2章 树 33
2.1树的定义和遍历 33
2.1.1树的相关定义 33
2.1.2树的遍历 34
2.2图的生成树 39
2.2.1最小生成树 39
2.2.2次小生成树 47
2.2.3有向图的最小树形图 53
2.3树的其他问题 60
2.3.1树上两点的最近公共祖先 60
2.3.2树的最小支配集，最小点覆盖与最大独立集 66
第3章 图的最短路径问题 78
3.1单源最短路径 78
3.1.1 Dijkstra算法 78
3.1.2 Bellman-Ford算法 83
3.1.3 SPFA算法 85
3.1.4例题 88
3.2每对顶点间的最短距离 90
3.2.1 Floyd算法 90
3.2.2例题 92
3.3最短路问题的扩展与应用 94
3.3.1 k短路 95
3.3.2差分约束系统 99
3.3.3 DAG图上的单源最短路径 104
3.3.4 Floyd求最小环 108
第4章 连通性问题 112
4.1图的强连通 112
4.1.1强连通的定义 112
4.1.2 Kosaraju算法 112
4.1.3 Tarjan算法 115
4.1.4 Garbow算法 118
4.1.5例题 120
4.2最小点基 125
4.2.1最小点基的定义 125
4.2.2最小点基 126
4.2.3最小权点基 126
4.2.4例题 126
4.3图的双连通 131
4.3.1双连通的定义 131
4.3.2点双连通分量 132
4.3.3边双连通分量 134
4.3.4例题 136
4.4图的全局最小割问题和Stoer-Wagner算法 142
4.5 2-SAT 146
4.5.1 SAT 146
4.5.2 2-SAT 147
4.5.3例题 147
第5章 网络流 151
5.1网络 151
5.1.1容量与流 151
5.1.2残留网络及增广路 152
5.1.3最小割最大流定理 153
5.2最大流算法 154
5.2.1 Ford-Fulkson方法的基本思想 154
5.2.2 Edmond-Karp算法 155
5.2.3 SAP算法及其优化 157
5.2.4 Dinic算法 160
5.2.5例题与应用 163
5.3有上下界的网络流 176
5.3.1解决上下界网络流的一般思路 176
5.3.2例题与应用 179
5.4网络的费用流 181
5.4.1连续最短路算法 181
5.4.2例题与应用 186
第6章 二分图及匹配算法 195
6.1匹配问题 195
6.2匹配基本定理 197
6.2.1 Berge定理 197
6.2.2 Hall定理 198
6.3二分图最大匹配 199
6.3.1匈牙利算法 199
6.3.2 Hopcroft-Karp算法 206
6.3.3二分图多重匹配 212
6.3.4二分图最大匹配的网络流解法 217
6.4二分图最佳匹配 218
6.4.1 Kuhn Munkras算法 218
6.5二分图模型的应用 228
6.5.1二分图最小点覆盖 228
6.5.2有向无环图的最小路径覆盖 231
6.5.3二分图的最大独立点集 234
6.5.4最小点权覆盖 236
参考文献 238