图论算法理论、实现及应用PDF电子书下载

第1章 图的基本概念及图的存储 1

1.1基本概念 1

1.1.1有向图与无向图 1

1.1.2完全图、稀疏图、稠密图 2

1.1.3顶点与顶点、顶点与边的关系 3

1.1.4顶点的度数及度序列 3

1.1.5二部图与完全二部图 5

1.1.6图的同构 6

1.1.7子图与生成树 6

1.1.8路径 8

1.1.9连通性 8

1.1.10权值、有向网与无向网 10

1.2图的存储表示 10

1.2.1邻接矩阵 10

1.2.2邻接表 17

1.2.3关于邻接矩阵和邻接表的进一步讨论 24

练习 24

第2章 图的遍历与活动网络问题 25

2.1 DFS遍历 25

2.1.1 DFS算法思想 25

2.1.2 DFS算法的实现及复杂度分析 26

2.1.3例题解析 29

练习 38

2.2 BFS遍历 41

2.2.1 BFS算法思想 41

2.2.2 BFS算法的实现及复杂度分析 42

2.2.3关于DFS算法和BFS算法的说明 44

2.2.4例题解析 45

练习 58

2.3活动网络——AOV网络 63

2.3.1 AOV网络与拓扑排序 63

2.3.2拓扑排序实现方法 65

2.3.3关于拓扑排序的进一步说明 70

2.3.4例题解析 71

练习 79

2.4活动网络——AOE网络 81

2.4.1 AOE网络与关键路径 81

2.4.2关键路径求解方法 82

第3章 树与图的生成树 88

3.1树与森林 88

3.1.1树 88

3.1.2森林 88

3.2生成树及最小生成树 89

3.2.1生成树 89

3.2.2最小生成树 89

3.3克鲁斯卡尔（Kruskal）算法 90

3.3.1 Kruskal算法思想 90

3.3.2等价类与并查集 91

3.3.3 Kruskal算法实现 95

3.3.4 Boruvka算法 99

3.3.5例题解析 99

练习 105

3.4普里姆（Prim）算法 109

3.4.1 Prim算法思想 109

3.4.2 Prim算法实现 110

3.4.3关于Prim算法的进一步讨论 114

3.4.4例题解析 114

练习 119

3.5判定最小生成树是否唯一 123

3.5.1最小生成树不唯一的原因分析 123

3.5.2判定最小生成树是否唯一的方法 124

3.5.3例题解析 126

第4章 最短路径问题 131

4.1边上权值非负情形的单源最短路径问题——Dijkstra算法 131

4.1.1算法思想 131

4.1.2算法实现 133

4.1.3关于Dijkstra算法的进一步讨论 137

4.1.4例题解析 137

练习 144

4.2边上权值为任意值的单源最短路径问题——Bellman-Ford算法 148

4.2.1算法思想 148

4.2.2算法实现 150

4.2.3关于 Bellman-Ford算法的进一步讨论 153

4.2.4例题解析 156

练习 164

4.3 Bellman-Ford算法的改进——SPFA算法 167

4.3.1算法思想 167

4.3.2算法实现 167

4.3.3关于SPFA算法的进一步讨论 171

4.3.4例题解析 171

练习 178

4.4所有顶点之间的最短路径——Floyd算法 180

4.4.1算法思想 180

4.4.2算法实现 182

4.4.3关于Floyd算法的进一步分析 185

4.4.4例题解析 185

练习 192

4.5差分约束系统 198

4.5.1差分约束系统与最短路径 198

4.5.2例题解析 200

练习 208

第5章 可行遍性问题 212

5.1欧拉回路 212

5.1.1基本概念及定理 212

5.1.2欧拉回路的判定 216

练习 223

5.2欧拉回路的求解 223

5.2.1 DFS搜索求解欧拉回路 223

5.2.2 Fleury（佛罗莱）算法 232

练习 236

5.3中国邮递员问题 237

5.4汉密尔顿回路 238

5.4.1基本概念及定理 239

5.4.2汉密尔顿回路求解 241

第6章 网络流问题 246

6.1网络最大流 246

6.1.1基本概念 247

6.1.2最大流最小割定理 251

6.1.3网络最大流的求解 252

6.1.4一般增广路方法——Ford-Fulkerson算法 253

6.1.5最短增广路算法 261

6.1.6连续最短增广路算法——Dinic算法 264

6.1.7一般预流推进算法 266

6.1.8最高标号预流推进算法 270

6.1.9网络最大流算法总结 270

6.1.10例题解析 271

练习 285

6.2最小割的求解 289

练习 301

6.3流量有上下界的网络的最大流和最小流 304

6.3.1流量有上下界的容量网络 304

6.3.2流量有上下界的网络的最大流 307

6.3.3流量有上下界的网络的最小流 307

6.3.4例题解析 313

练习 325

6.4最小费用最大流 327

6.4.1基本概念 327

6.4.2最小费用最大流算法 328

6.4.3例题解析 330

练习 338

第7章 支配集、覆盖集、独立集与匹配 342

7.1点支配集、点覆盖集、点独立集 342

7.1.1点支配集 342

7.1.2点覆盖集 344

7.1.3点独立集 345

7.1.4点支配集、点覆盖集、点独立集之间的联系 347

7.2点支配集、点覆盖集、点独立集的求解 347

7.2.1逻辑运算 347

7.2.2极小点支配集的求解 348

7.2.3极小点覆盖集、极大点独立集的求解 348

7.3边覆盖集与边独立集 349

7.3.1边覆盖集 349

7.3.2边独立集（匹配） 350

7.3.3最大边独立集（最大匹配）与最小边覆盖集之间的联系 352

7.4匹配问题 353

7.4.1完美匹配 353

7.4.2二部图的完备匹配与完美匹配 354

7.4.3最佳匹配 354

7.4.4匹配问题求解的基本概念及思路 354

7.5二部图最大匹配问题的求解 356

7.5.1网络流解法 356

7.5.2匈牙利算法 358

7.5.3例题解析 361

练习 377

第8章 图的连通性问题 382

8.1基本概念 382

8.1.1连通图与非连通图 382

8.1.2无向图的点连通性 383

8.1.3无向图的边连通性 385

8.1.4无向图顶点连通性和边连通性的联系 386

8.1.5有向图的连通性 386

8.2无向图点连通性的求解及应用 387

8.2.1关节点的求解 387

8.2.2重连通分量的求解 394

8.2.3顶点连通度的求解 396

练习 401

8.3无向图边连通性的求解及应用 403

8.3.1割边的求解 403

8.3.2边双连通分量的求解 407

8.3.3边连通度的求解 414

练习 416

8.4有向图强连通性的求解及应用 418

8.4.1有向图强连通分量的求解算法 418

8.4.2有向图强连通分量的应用 421

练习 435

第9章 平面图及图的着色问题 438

9.1基本概念 438

9.1.1平面图与非平面图 438

9.1.2区域与边界 439

9.1.3极大平面图与极小非平面图 440

9.1.4平面图的对偶图 440

9.1.5关于平面图的一些定理 441

9.2欧拉公式及其应用 441

9.2.1欧拉公式 441

9.2.2欧拉公式的应用 442

练习 445

9.3平面图的判定 446

9.4图的着色问题 447

9.4.1地图染色与四色猜想 447

9.4.2图的着色 448

9.4.3图着色的应用 450

9.4.4图着色求解算法及例题解析 451

练习 455

附录 本书例题和练习题目录 457

索引 461

参考文献 469