扫一扫
关注中图网
官方微博
本类五星书更多>
-
>
中医基础理论
-
>
高校军事课教程
-
>
思想道德与法治(2021年版)
-
>
毛泽东思想和中国特色社会主义理论体系概论(2021年版)
-
>
中医内科学·全国中医药行业高等教育“十四五”规划教材
-
>
中医诊断学--新世纪第五版
-
>
中药学·全国中医药行业高等教育“十四五”规划教材
图论算法理论、实现及应用(第2版) 版权信息
- ISBN：9787301323854
- 条形码：9787301323854 ; 978-7-301-32385-4
- 装帧：一般胶版纸
- 册数：暂无
- 重量：暂无
- 所属分类：>>
图论算法理论、实现及应用(第2版) 本书特色
本书可以作为高等院校计算机专业(或相关专业)图论等相关课程的主教材，也可作为 ACM/ICPC的辅导教材。
图论算法理论、实现及应用(第2版) 内容简介
本书系统地介绍了图论算法理论，并选取经典的 ACM/ICPC 题目为例题阐述图论算法思想，侧重于图论算法的程序实现及应用。本书第 1章介绍图的基本概念和图的两种存储表示方法：邻接矩阵和邻接表。第 2～9章分别讨论图的遍历与活动网络问题，树与图的生成树，*短路径问题，可行遍性问题，网络流问题，支配集、覆盖集、独立集与匹配，图的连通性问题，平面图及图的着色问题。 本书可以作为高等院校计算机专业(或相关专业)图论等相关课程的主教材，也可作为 ACM/ICPC的辅导教材。
图论算法理论、实现及应用(第2版) 目录
第1章 图的基本概念及图的存储 1
1.1 基本概念 1
1.1.1 有向图与无向图 1
1.1.2 完全图、稀疏图、稠密图 2
1.1.3 顶点与顶点、顶点与边的关系 3
1.1.4 顶点的度数及度序列 3
1.1.5 二部图与完全二部图 6
1.1.6 图的同构 7
1.1.7 子图与生成树 8
1.1.8 路径 9
1.1.9 连通性 10
1.1.10 权值、有向网与无向网 11
1.2 图的存储表示 11
1.2.1 邻接矩阵 12
1.2.2 可达性矩阵 20
1.2.3 邻接表 21
1.2.4 关于邻接矩阵和邻接表的进一步讨论 26
练习 27
第2章 图的遍历与活动网络问题 28
2.1 DFS遍历 28
2.1.1 DFS算法思想 28
2.1.2 DFS算法的实现及复杂度分析 29
2.1.3 例题解析 32
练习 42
2.2 BFS遍历 45
2.2.1 BFS算法思想 45
2.2.2 BFS算法的实现及复杂度分析 46
2.2.3 关于DFS算法和BFS算法的说明 48
2.2.4 例题解析 48
练习 58
2.3 活动网络——AOV网络 66
2.3.1 AOV网络与拓扑排序 66
2.3.2 拓扑排序实现方法 67
2.3.3 关于拓扑排序的进一步说明 71
2.3.4 例题解析 72
练习 82
2.4 活动网络——AOE网络 84
2.4.1 AOE网络与关键路径 84
2.4.2 关键路径求解方法 85
第3章 树与图的生成树 91
3.1 树与森林 91
3.1.1 树 91
3.1.2 森林 92
3.2 生成树及*小生成树 92
3.2.1 生成树 92
3.2.2 *小生成树 92
3.3 Kruskal算法和Boruvka算法 93
3.3.1 Kruskal算法思想 93
3.3.2 等价类与并查集 94
3.3.3 Kruskal算法实现 98
3.3.4 关于Kruskal算法的进一步讨论 101
3.3.5 Boruvka算法 101
3.3.6 例题解析 102
练习 106
3.4 Prim算法 109
3.4.1 Prim算法思想 109
3.4.2 Prim算法实现 111
3.4.3 关于Prim算法的进一步讨论 114
3.4.4 例题解析 114
练习 118
3.5 *小生成树问题的拓展 121
3.5.1 带权并查集 121
3.5.2 *大生成树 124
3.5.3 *小生成森林、*大生成
森林 124
3.5.4 判定*小生成树是否唯一 125
练习 129
第4章 *短路径问题 131
4.1 边上权值非负情形的单源*短路径问题——Dijkstra算法 131
4.1.1 算法思想 131
4.1.2 算法实现 133
4.1.3 关于Dijkstra算法的进一步讨论 137
4.1.4 例题解析 137
练习 142
4.2 边上权值为任意值的单源*短路径问题——Bellman-Ford算法 146
4.2.1 算法思想 146
4.2.2 算法实现 148
4.2.3 关于Bellman-Ford算法的进一步讨论 151
4.2.4 例题解析 154
练习 161
4.3 Bellman-Ford算法的改进——SPFA算法 163
4.3.1 算法思想 163
4.3.2 算法实现 164
4.3.3 关于SPFA算法的进一步讨论 167
4.3.4 例题解析 167
练习 173
4.4 所有顶点之间的*短路径——Floyd算法 175
4.4.1 算法思想 176
4.4.2 算法实现 177
4.4.3 关于Floyd算法的进一步讨论 180
4.4.4 例题解析 180
练习 186
4.5 *短路径问题拓展 190
4.5.1 有向网*短路径、回路与*短简单路径 190
4.5.2 无向网中的*短路径问题 190
4.5.3 单源*短路径三角形不等式 192
4.5.4 *长路径 193
4.6 差分约束系统 197
4.6.1 差分约束系统与*短路径问题 197
4.6.2 例题解析 199
练习 207
第5章 可行遍性问题 210
5.1 欧拉回路 210
5.1.1 基本概念及定理 210
5.1.2 欧拉回路的判定 214
练习 219
5.2 欧拉回路的求解 220
5.2.1 DFS算法求解欧拉回路 220
5.2.2 Fleury算法求解欧拉回路 226
练习 229
5.3 中国邮递员问题 231
5.4 汉密尔顿回路 232
5.4.1 基本概念及定理 233
5.4.2 汉密尔顿回路求解 234
第6章 网络流问题 239
6.1 网络*大流 239
6.1.1 基本概念 240
6.1.2 *大流*小割定理 245
6.1.3 网络*大流的求解 245
6.1.4 一般增广路方法——Ford-Fulkerson算法 246
6.1.5 *短增广路算法 254
6.1.6 连续*短增广路算法——Dinic算法 257
6.1.7 一般预流推进算法 261
6.1.8 *高标号预流推进算法 265
6.1.9 网络*大流算法总结 266
6.1.10 例题解析 266
练习 279
6.2 *小割的求解 283
练习 293
6.3 流量有上下界的网络的*大流和*小流 296
6.3.1 流量有上下界的容量网络 296
6.3.2 流量有上下界的网络的*大流 299
6.3.3 流量有上下界的网络的*小流 300
6.3.4 例题解析 305
练习 317
6.4 *小费用*大流 318
6.4.1 基本概念 318
6.4.2 *小费用*大流算法 319
6.4.3 例题解析 322
练习 329
第7章 支配集、覆盖集、独立集与匹配 333
7.1 点支配集、点覆盖集、点独立集 333
7.1.1 点支配集 333
7.1.2 点覆盖集 335
7.1.3 点独立集 336
7.1.4 点支配集、点覆盖集、点独立集之间的联系 338
7.2 点支配集、点覆盖集、点独立集的求解 339
7.2.1 逻辑运算 339
7.2.2 极小点支配集的求解 339
7.2.3 极小点覆盖集、极大点独立集的求解 340
7.3 边覆盖集与边独立集 341
7.3.1 边覆盖集 341
7.3.2 边独立集(匹配) 342
7.3.3 *大边独立集(*大匹配)与*小边覆盖集之间的联系 344
7.4 匹配问题 345
7.4.1 完美匹配 345
7.4.2 二部图的完备匹配与完美匹配 346
7.4.3 *佳匹配 346
7.4.4 匹配问题求解的基本概念及思路 346
7.5 二部图*大匹配问题的求解 348
7.5.1 网络流解法 348
7.5.2 匈牙利算法 349
7.5.3 例题解析 352
练习 367
第8章 图的连通性问题 373
8.1 基本概念 373
8.1.1 连通图与非连通图 373
8.1.2 无向图的顶点连通性 374
8.1.3 无向图的边连通性 376
8.1.4 无向图顶点连通性和边连通性的联系 377
8.1.5 有向图的连通性 378
8.2 无向图顶点连通性的求解及应用 378
8.2.1 关节点的求解 378
8.2.2 重连通分量的求解 384
8.2.3 顶点连通度的求解 390
练习 394
8.3 无向图边连通性的求解及应用 396
8.3.1 割边的求解 396
8.3.2 边双连通分量的求解 400
8.3.3 边连通度的求解 403
练习 404
8.4 有向图连通性的求解及应用 405
8.4.1 有向图的深度优先搜索 405
8.4.2 有向图强连通分量的求解算法 407
8.4.3 有向图强连通分量的应用 412
8.4.4 有向图单连通性的判定 421
8.4.5 有向图弱连通性的判定 424
练习 424
第9章 平面图及图的着色问题 427
9.1 基本概念 427
9.1.1 平面图与非平面图 427
9.1.2 区域与边界 428
9.1.3 极大平面图与极小非平面图 429
9.1.4 平面图的对偶图 429
9.1.5 关于平面图的一些定理 430
9.2 欧拉公式及其应用 431
9.2.1 欧拉公式 431
9.2.2 欧拉公式的应用 431
练习 434
9.3 平面图的判定 435
9.4 图的着色问题 436
9.4.1 地图染色与四色猜想 436
9.4.2 图的着色 437
9.4.3 图着色的应用 440
9.4.4 图着色求解算法及例题解析 440
练习 444
附录 本书例题和练习题目录 446
参考文献 450
1.1 基本概念 1
1.1.1 有向图与无向图 1
1.1.2 完全图、稀疏图、稠密图 2
1.1.3 顶点与顶点、顶点与边的关系 3
1.1.4 顶点的度数及度序列 3
1.1.5 二部图与完全二部图 6
1.1.6 图的同构 7
1.1.7 子图与生成树 8
1.1.8 路径 9
1.1.9 连通性 10
1.1.10 权值、有向网与无向网 11
1.2 图的存储表示 11
1.2.1 邻接矩阵 12
1.2.2 可达性矩阵 20
1.2.3 邻接表 21
1.2.4 关于邻接矩阵和邻接表的进一步讨论 26
练习 27
第2章 图的遍历与活动网络问题 28
2.1 DFS遍历 28
2.1.1 DFS算法思想 28
2.1.2 DFS算法的实现及复杂度分析 29
2.1.3 例题解析 32
练习 42
2.2 BFS遍历 45
2.2.1 BFS算法思想 45
2.2.2 BFS算法的实现及复杂度分析 46
2.2.3 关于DFS算法和BFS算法的说明 48
2.2.4 例题解析 48
练习 58
2.3 活动网络——AOV网络 66
2.3.1 AOV网络与拓扑排序 66
2.3.2 拓扑排序实现方法 67
2.3.3 关于拓扑排序的进一步说明 71
2.3.4 例题解析 72
练习 82
2.4 活动网络——AOE网络 84
2.4.1 AOE网络与关键路径 84
2.4.2 关键路径求解方法 85
第3章 树与图的生成树 91
3.1 树与森林 91
3.1.1 树 91
3.1.2 森林 92
3.2 生成树及*小生成树 92
3.2.1 生成树 92
3.2.2 *小生成树 92
3.3 Kruskal算法和Boruvka算法 93
3.3.1 Kruskal算法思想 93
3.3.2 等价类与并查集 94
3.3.3 Kruskal算法实现 98
3.3.4 关于Kruskal算法的进一步讨论 101
3.3.5 Boruvka算法 101
3.3.6 例题解析 102
练习 106
3.4 Prim算法 109
3.4.1 Prim算法思想 109
3.4.2 Prim算法实现 111
3.4.3 关于Prim算法的进一步讨论 114
3.4.4 例题解析 114
练习 118
3.5 *小生成树问题的拓展 121
3.5.1 带权并查集 121
3.5.2 *大生成树 124
3.5.3 *小生成森林、*大生成
森林 124
3.5.4 判定*小生成树是否唯一 125
练习 129
第4章 *短路径问题 131
4.1 边上权值非负情形的单源*短路径问题——Dijkstra算法 131
4.1.1 算法思想 131
4.1.2 算法实现 133
4.1.3 关于Dijkstra算法的进一步讨论 137
4.1.4 例题解析 137
练习 142
4.2 边上权值为任意值的单源*短路径问题——Bellman-Ford算法 146
4.2.1 算法思想 146
4.2.2 算法实现 148
4.2.3 关于Bellman-Ford算法的进一步讨论 151
4.2.4 例题解析 154
练习 161
4.3 Bellman-Ford算法的改进——SPFA算法 163
4.3.1 算法思想 163
4.3.2 算法实现 164
4.3.3 关于SPFA算法的进一步讨论 167
4.3.4 例题解析 167
练习 173
4.4 所有顶点之间的*短路径——Floyd算法 175
4.4.1 算法思想 176
4.4.2 算法实现 177
4.4.3 关于Floyd算法的进一步讨论 180
4.4.4 例题解析 180
练习 186
4.5 *短路径问题拓展 190
4.5.1 有向网*短路径、回路与*短简单路径 190
4.5.2 无向网中的*短路径问题 190
4.5.3 单源*短路径三角形不等式 192
4.5.4 *长路径 193
4.6 差分约束系统 197
4.6.1 差分约束系统与*短路径问题 197
4.6.2 例题解析 199
练习 207
第5章 可行遍性问题 210
5.1 欧拉回路 210
5.1.1 基本概念及定理 210
5.1.2 欧拉回路的判定 214
练习 219
5.2 欧拉回路的求解 220
5.2.1 DFS算法求解欧拉回路 220
5.2.2 Fleury算法求解欧拉回路 226
练习 229
5.3 中国邮递员问题 231
5.4 汉密尔顿回路 232
5.4.1 基本概念及定理 233
5.4.2 汉密尔顿回路求解 234
第6章 网络流问题 239
6.1 网络*大流 239
6.1.1 基本概念 240
6.1.2 *大流*小割定理 245
6.1.3 网络*大流的求解 245
6.1.4 一般增广路方法——Ford-Fulkerson算法 246
6.1.5 *短增广路算法 254
6.1.6 连续*短增广路算法——Dinic算法 257
6.1.7 一般预流推进算法 261
6.1.8 *高标号预流推进算法 265
6.1.9 网络*大流算法总结 266
6.1.10 例题解析 266
练习 279
6.2 *小割的求解 283
练习 293
6.3 流量有上下界的网络的*大流和*小流 296
6.3.1 流量有上下界的容量网络 296
6.3.2 流量有上下界的网络的*大流 299
6.3.3 流量有上下界的网络的*小流 300
6.3.4 例题解析 305
练习 317
6.4 *小费用*大流 318
6.4.1 基本概念 318
6.4.2 *小费用*大流算法 319
6.4.3 例题解析 322
练习 329
第7章 支配集、覆盖集、独立集与匹配 333
7.1 点支配集、点覆盖集、点独立集 333
7.1.1 点支配集 333
7.1.2 点覆盖集 335
7.1.3 点独立集 336
7.1.4 点支配集、点覆盖集、点独立集之间的联系 338
7.2 点支配集、点覆盖集、点独立集的求解 339
7.2.1 逻辑运算 339
7.2.2 极小点支配集的求解 339
7.2.3 极小点覆盖集、极大点独立集的求解 340
7.3 边覆盖集与边独立集 341
7.3.1 边覆盖集 341
7.3.2 边独立集(匹配) 342
7.3.3 *大边独立集(*大匹配)与*小边覆盖集之间的联系 344
7.4 匹配问题 345
7.4.1 完美匹配 345
7.4.2 二部图的完备匹配与完美匹配 346
7.4.3 *佳匹配 346
7.4.4 匹配问题求解的基本概念及思路 346
7.5 二部图*大匹配问题的求解 348
7.5.1 网络流解法 348
7.5.2 匈牙利算法 349
7.5.3 例题解析 352
练习 367
第8章 图的连通性问题 373
8.1 基本概念 373
8.1.1 连通图与非连通图 373
8.1.2 无向图的顶点连通性 374
8.1.3 无向图的边连通性 376
8.1.4 无向图顶点连通性和边连通性的联系 377
8.1.5 有向图的连通性 378
8.2 无向图顶点连通性的求解及应用 378
8.2.1 关节点的求解 378
8.2.2 重连通分量的求解 384
8.2.3 顶点连通度的求解 390
练习 394
8.3 无向图边连通性的求解及应用 396
8.3.1 割边的求解 396
8.3.2 边双连通分量的求解 400
8.3.3 边连通度的求解 403
练习 404
8.4 有向图连通性的求解及应用 405
8.4.1 有向图的深度优先搜索 405
8.4.2 有向图强连通分量的求解算法 407
8.4.3 有向图强连通分量的应用 412
8.4.4 有向图单连通性的判定 421
8.4.5 有向图弱连通性的判定 424
练习 424
第9章 平面图及图的着色问题 427
9.1 基本概念 427
9.1.1 平面图与非平面图 427
9.1.2 区域与边界 428
9.1.3 极大平面图与极小非平面图 429
9.1.4 平面图的对偶图 429
9.1.5 关于平面图的一些定理 430
9.2 欧拉公式及其应用 431
9.2.1 欧拉公式 431
9.2.2 欧拉公式的应用 431
练习 434
9.3 平面图的判定 435
9.4 图的着色问题 436
9.4.1 地图染色与四色猜想 436
9.4.2 图的着色 437
9.4.3 图着色的应用 440
9.4.4 图着色求解算法及例题解析 440
练习 444
附录 本书例题和练习题目录 446
参考文献 450
展开全部
图论算法理论、实现及应用(第2版) 作者简介
王桂平，博士，副教授，硕导，重庆交通大学数据科学与大数据技术专业负责人，近20年程序设计竞赛指导经验，出版教材6本，主持省部级教学研究项目2项；主要从事交通基础设施状态监测、损伤识别研究，以及机器学习、深度学习算法和大数据分析与处理算法研究，主持省部级科研项目3项，主研国家自然科学基金项目3项（均排名第2）、省部级科研项目4项；发表学术论文40多篇，其中第一作者SCI检索期刊论文9篇、EI检索期刊论文10篇。杨建喜，博士，教授，重庆交通大学，主要从事桥梁健康监测、安全性评估及寿命预测方面的基础理论研究及工程实践。获得国家科技进步二等奖1项、省部级科技一、二、三等奖各1项；发明专利1项；出版学术著作1部；获得软件著作权3项；发表学术论文30多篇，其中：第一作者SCI检索6篇、EI检索10篇；主持国家自然科学基金项目1项、省部级重点课题1项、省部级一般基金项目3项；主研973前期计划项目1项、国家自然科学基金2项、省部级课题10项。李韧，博士，副教授，重庆交通大学，主要从事大数据、神经网络方面的研究，共开发表论文21篇，主参编教材6部。
书友推荐
本类畅销
-
初等数论-(I)
¥15.6¥18 -
流体力学(第二版)
¥68.2¥96 -
模糊数学
¥47.5¥56 -
4.23文创礼盒A款--“作家言我精神状态”
¥42.3¥206 -
4.23文创礼盒B款--“作家言我精神状态”
¥42.3¥206 -
一句顶一万句 (印签版)
¥40.4¥68
