目 录 2
第五部分图算法 2
第17章图性质和类型 2
17.1术语 4
练习 11
17.2图ADT 12
练习 15
17.3邻接矩阵表达方式 16
练习 19
17.4邻接表表达方式 20
练习 22
17.5变体、扩展和开销 23
练习 27
17.6图生成器 29
练习 36
17.7简单路径、欧拉路径和哈密顿路径 38
练习 49
17.8图处理问题 50
练习 56
第18章图搜索 58
18.1探索迷宫 58
练习 62
18.2深度优先搜索 63
练习 66
18.3图搜索ADT函数 67
练习 70
18.4 DFS森林的性质 71
18.5.DFS算法 77
练习 77
练习 80
18.6分离性和双连通性 82
练习 88
18.7广度优先搜索 89
练习 95
18.8通用图搜索 96
练习 101
18.9图算法的分析 103
练习 107
第19章有向图和DAG 108
练习 110
19.1术语和游戏规则 110
练习 117
19.2有向图中DFS的剖析 118
练习 124
19.3可达性和传递闭包 125
练习 134
19.4等价关系和偏序 135
练习 137
19.5 DAG 138
练习 141
19.6拓扑排序 142
练习 149
19.7DAG中的可达性 150
练习 152
19.8有向图中的强分量 153
练习 159
19.9再论传递闭包 160
练习 163
19.10展望 163
练习 165
第20章最小生成树 167
练习 169
20.1表达方式 169
练习 173
20.2 MST算法原理 173
练习 179
20.3普里姆算法和优先级优先搜索 179
练习 187
20.4 Kruskal算法 188
20.5 Boruvka算法 193
练习 193
练习 196
20.6比较与改进 197
练习 200
20.7欧几米得MST 201
练习 203
第21章最短路径 204
练习 209
21.1基本原理 210
练习 215
21.2Dijkstra算法 215
练习 221
21.3所有点对最短路径 223
练习 228
21.4无环网络中的最短路径 229
练习 235
21.5欧几米得网络 236
练习 239
21.6归约 240
练习 251
21.7负权重 253
练习 265
21.8展望 267
第22章网络流 269
22.1流网络 273
练习 281
22.2增广路径最大流算法 283
练习 301
22.3前流推进最大流算法 302
练习 312
22.4最大流归约 314
练习 326
22.5最小开销流 328
练习 334
22.6网络单纯形算法 335
练习 348
22.7最小开销流归约 349
练习 354
22.8展望 356
第五部分参考文献 359
索引 361