图论算法理论实现及应用(第2版高等院校电气信息类专业互联网+创新规划教材)
全新正版 极速发货
￥ 65.61 7.5折 ￥ 88 全新
库存3件
广东广州
认证卖家担保交易快速发货售后保障
作者编者:王桂平//杨建喜//李韧|责编:郑双
出版社北京大学
ISBN9787301323854
出版时间2022-01
装帧平装
开本其他
定价88元
货号31344975
上书时间2024-06-29
商品详情
- 品相描述：全新
- 商品描述
-
作者简介
王桂平，博士，副教授，硕导，重庆交通大学数据科学与大数据技术专业负责人，近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部。
目录
第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
内容摘要
本书系统地介绍了图论算法理论，并选取经典的ACM/ICPC题目为例题阐述图论算法思想，侧重于图论算法的程序实现及应用。本书第1章介绍图的基本概念和图的两种存储表示方法：邻接矩阵和邻接表。第2～9章分别讨论图的遍历与活动网络问题，树与图的生成树，最短路径问题，可行遍性问题，网络流问题，支配集、覆盖集、独立集与匹配，图的连通性问题，平面图及图的着色问题。
本书可以作为高等院校计算机专业(或相关专业)图论等相关课程的主教材，也可作为ACM/ICPC的辅导教材。
主编推荐
本书可以作为高等院校计算机专业(或相关专业)图论等相关课程的主教材，也可作为 ACM/ICPC的辅导教材。
— 没有更多了 —
以下为对购买帮助不大的评价