ACM-ICPC程序设计系列 图论及应用

出版时间：2012-3  出版社：哈尔滨工业大学出版社  作者：冯林，金博，姚翠莉　主编  页数：240  
Tag标签：无  

内容概要

本书主要介绍ACM—ICPC比赛中涉及的图论，其中包括许多实际问题的抽象表示与求解，以及部分图论理论内容的证明。全书共分6章，第1章介绍了图论的基础知识，包括基础概念、存储方法和遍历方法；第2章介绍了有关树的问题，着重讲解生成树和一些树上特殊点集的求法；第3章介绍了最短路径问题，包括几种通用算法和特殊图上的算法；第4章介绍图论中有关连通性的问题，包括有向图的强连通、无向图的双连通及其扩展问题；第5章介绍网络流解法，包括几种常用的网络流算法和对于问题如何抽象成网络流模型的经验方法；第6章介绍二分图的相关问题，重点为二分图的匹配及其变种问题。本书的内容基本满足ACM—ICPC比赛对于图论方面的要求，讲解清晰易懂，代码规范，例题丰富。

书籍目录

第1章 图
 1.1 图的定义和术语
 1.1.1 图的定义
 1.1.2 特殊的图
 1.1.3 有向图和无向图
 1.1.4 路径与连通
 1.2 图的存储结构
 1.2.1 邻接矩阵
 1.2.2 前向星
 1.2.3 邻接表
 1.3 图的遍历
 1.3.1 图的深度优先遍历
 1.3.2 图的宽度优先遍历
 1.3.3 图的拓扑排序
 1.3.4 图的可行遍性
第2章 树
 2.1 树的定义和遍历
 2.1.1 树的相关定义
 2.1.2　树的遍历
 2.2 图的生成树
 2.2.1 最小生成树
 2.2.2　次小生成树
 2.2.3 有向图的最小树形图
 2.3 树的其他问题
 2.3.1 树上两点的最近公共祖先
 2.3.2 树的最小支配集，最小点覆盖与最大独立集
第3章 图的最短路径问题
 3.1 单源最短路径
 3.1.1 Dijkstra算法
 3.1.2 Bellman—Ford算法
 3.1.3 SPFA算法
 3.1.4　例题
 3.2 每对顶点间的最短距离
 3.2.1 Floyd算法
 3.2.2　例题
 3.3 最短路问题的扩展与应用
 3.3.1 k短路
 3.3.2 差分约束系统
 3.3.3 DAG图上的单源最短路径
 3.3.4 Floyd求最小环
第4章 连通性问题
 4.1 图的强连通
 4.1.1 强连通的定义
 4.1.2 Kosaraju算法
 4.1.3 Tarjan算法
 4.1.4 Garbow算法
 4.1.5 例题
 4.2　最小点基
 4.2.1 最小点基的定义
 4.2.2 最小点基
 4.2.3 最小权点基
 4.2.4 例题
 4.3 图的双连通
 4.3.1 双连通的定义
 4.3.2 点双连通分量
 4.3.3 边双连通分量
 4.3.4　例题
4.4 图的全局最小割问题和Stoer—Wagner算法
4.5 2一SAT
 4.5.1 SAT
 4.5.2 2一SAT
 4.5.3 例题
第5章 网络流
第6章 二分图及匹配算法
参考文献

编辑推荐

　　《图论及应用》是ACM-ICPC程序设计系列丛书之一。全书共分6章，内容包括：图，树，图的最短路径问题，连通性问题，网络流，二分图及匹配算法。　　本书既可以作为高等院校信息与计算科学、计算机专业及数学相关专业的图论教材，也可以作为高等学校计算机竞赛的培训教材，还可供计算机软硬件研发人员参考。

用户评论 (总计10条)

•   我毫不吝惜溢美之词来赞美这本书……
  细致全面，大部分都是算法的讲解而非干枯的题目加代码（当然这本书的代码还是很全的，这一套书的特点就是代码全面）。【我觉得只有题目+几句简单分析+贴代码的那种书都是渣渣~】算法讲得蛮透彻的，而且基本算法+稍高级的算法都全了，还有堆优化等的样例代码，只有一些事无巨细的高级算法（比如第K小生成树，最小度限制生成树等）没有讲。总而言之，能在这么小一本书里集成这么多东西，真是太棒了！！
•   比较有针对性的讲解值得看看
•   但是有些例子讲解的不是特别细致，导致我这种菜鸟看不懂呃。。。
•   内容很不错，学习ing
•   专业学习用的书，当当买书真方便呀，速度送到！
•   看别人买的 感觉挺不错 我也买了一本
•   没有时间全部阅读，在里面找了好多小例子，还是很有用的。
•   图论讲解还是比较好的！少了很多枯燥的东西！但是其证明好像太少！
•   有的题目只有部分代码，比较难懂
•   哦给力，还没看