图论算法理论、实现及应用
2011-1
北京大学
王桂平//王衍//任嘉辰
468
无
本书选取经典的ACM/ICPC竞赛题目为例阐述图论算法思想，侧重于图论算法的程序实现及图论算法的应用。本书分为上、下两册。上册为第1～5章，其中第1章介绍图论基本概念和图的两种存储表示方法：邻接矩阵和邻接表，第2～5章分别讨论图的遍历与活动网络，树与生成树问题，最短路径问题，可行遍性问题。下册为第6～9章，分别讨论网络流问题，图的连通性，点支配集、点覆盖集、点独立集、边覆盖集、边独立集（匹配），平面图与图的着色问题等等。本书可以作为高等院校计算机（或相关专业）图论等相关课程的教材，也可作为ACM/ICPC竞赛的辅导教材。
第1章 图的基本概念及图的存储 1.1 基本概念 1.1.1 有向图与无向图 1.1.2 完全图、稀疏图、稠密图 1.1.3 顶点与顶点、顶点与边的关系 1.1.4 顶点的度数及度序列 1.1.5 二部图与完全二部图 1.1.6 图的同构 1.1.7 子图与生成树 1.1.8 路径 1.1.9 连通性 1.1.10 权值、有向网与无向网 1.2 图的存储表示 1.2.1 邻接矩阵 1.2.2 邻接表 1.2.3 关于邻接矩阵和邻接表的进一步讨论 练习第2章 图的遍历与活动网络问题 2.1 DFS遍历 2.1.1 DFS算法思想 2.1.2 DFS算法的实现及复杂度分析 2.1.3 例题解析 练习 2.2 BFS遍历 2.2.1 BFS算法思想 2.2.2 BFS算法的实现及复杂度分析 2.2.3 关于DFS算法和BFS算法的说明 2.2.4 例题解析 练习 2.3 活动网络——AOV网络 2.3.1 AOV网络与拓扑排序 2.3.2 拓扑排序实现方法 2.3.3 关于拓扑排序的进一步说明 2.3.4 例题解析 练习 2.4 活动网络——AOE网络 2.4.1 AOE网络与关键路径 2.4.2 关键路径求解方法第3章 树与图的生成树 3.1 树与森林 3.1.1 树 3.1.2 森林 3.2 生成树及最小生成树 3.2.1 生成树 3.2.2最小生成树 3.3 克鲁斯卡尔(Kruskal)算法 3.3.1 Kruskal算法思想 3.3.2 等价类与并查集 3.3.3 Kruskal算法实现 3.3.4 Boruvka算法 3.3.5 例题解析 练习 3.4 普里姆(Prim)算法 3.4.1 Prim算法思想 3.4.2 Prim算法实现 3.4.3 关于Prim算法的进一步讨论 3.4.4 例题解析 练习 3.5 判定最小生成树是否唯一 3.5.1 最小生成树不唯一的原因分析 3.5.2 判定最小生成树是否唯一的方法 3.5.3 例题解析第4章 最短路径问题第5章 可行遍性问题第6章 网络流问题第7章 支配集、覆盖集、独立集与匹配第8章 图的连通性问题第9章 平面图及图的着色问题附录 本书例题和练习题目录索引参考文献
版权页：插图：在本题中，每个单词只有首尾两个字母很关键，并且每个单词可以看成连接首尾两个字母的一条有向边（由首字母指向尾字母）。这样每个测试数据中的一组单词可以构造成一个图：图中的顶点为26个小写字母，每个单词为图中的一条边。例如，本题样例输入中两个测试数据所构造的有向图如图5.7所示。构造好有向图后，题目要判定是否可以经过重组使得每个单词的第1个字母跟前一个单词最后一个字母相同，等效于判断图中是否存在一条路径经过每条边一次且仅一次，这就是有向欧拉通路。本题的处理方法如下。 （1）读入每个单词时，因为每个单词相当于一条从首字母指向尾字母的边，所以对单词首字母对应的顶点，出度加1；尾字母对应的顶点，入度加1。（2）26个顶点的入度和出度都统计完毕后，根据各项点的出度、入度关系来判断是否存在欧拉通路，但要注意排除每个单词的首尾字母中没有出现过的字母。在下面的代码中，用bused数组来表示每个字母是否在单词的首尾中出现。例如，在图5.7（a）中，只有3个字母对应有顶点，其他23个字母都没有对应顶点。
《图论算法理论、实现及应用》：21世纪全国应用型本科计算机案例型规划教材
无
研究ACM图论算法的好书
内容很全，比起《算法导论》来说对图论部分针对性更高，而且更容易读懂。而且对于每个算法，都有相关题目作为介绍，通俗易懂，特别推荐！
这本书很适合ACM初学图论者，理论讲过之后有OJ上的题作为实例讲解，解析的很清楚，还有实现代码
非常适合学习图论算法
适合想学习图论的人，里面的代码很好，很详细。是少有的里面既有思想又有代码的图论学习书
这书并不火 但是里面的细致超级适合刚刚学习图论和想提高的ACMer
挺好，就是图论很多东西没说
适合图论入门
里面关于图形和算法，有好多地方用编程描述，需要些底子
此书对于搞ACM的同学来说作为入门书籍挺不错的
偶尔从网上看到了这本书，适合中学信息学竞赛使用，内容很全。
这几年出的好的理论教材多了些，作为读者很享受啊。
专业书籍，还是很不错的一本书
这是我第一次在网上买书，感觉不错呦！下次还来~
例子加讲解感觉挺不错的
真心不错，如果想了解这方面的知识，应该可以看看。。
才买来 还没看 挺好的
每个例题都很有代表性，而且都有完整的代码可以参考学习，非常不错！
内容具体化, 不错
图论算法的一本书，还可以
如果你想要学习图论，如果你想要参加ACM，可以看看
讲的很有条理，适合算法竞赛入门
书中经典算法很多，很实用
这本书不错，值得一看！推荐
看同学在看 我借来look 发现 有习题 嘿嘿 最喜欢的就是知识点+习题这种节奏了 果断来一本
书还不错，讲得比较详细
书很新，没有任何损坏，哈哈，给力
不错的书，感兴趣的可以去看看，不过价格有点贵了
书的质量不错， 包装没有折损， 不是二手的。。送货速度挺快的。。总体很满意。。
代码很详细，很不错，而且讲解的比较容易懂
其实这本书名字改成ACM题集(图论篇)更适合。。。
内容很深奥，没有练习题
清华大学的书不是都有防伪标签吗？这书没有，还有送过来时拆开一看，书的保护不太好，有点折了角，给人一种在一个很乱的仓库里地上捡一本一样的感觉。
一直很喜欢这本书，所以感觉还不错。
货收到了，还行吧，呵呵，瞎看呢
图论经典书籍，讲得很细还有参考代码，虽然有的插图上也有一些小错误，不过不影响它的优秀
我是看完之后评论的。这本书引导我入门图论了，适合自学，因为这本书不讲理论。但是，这本书的作者应该挺浮躁，这本书里，我看不到作者的投入和心血，都是直接讲代码；我严重怀疑这本书的代码不是作者写的，因为风格差劲且不统一，对于不经常编程的人，应该不要看这本书，这本书的编程风格很差。平心而论，如果你看不下图论的理论去，可以用这本书入门自学。但是，这本书没什么营养，没有心血。
基本涉及了图论算法所有的基本知识，OI和ACM都基本够用了，题目都是网站上面的题目，十分贴心的给出了中文翻译，讲解也很到位，代码也有必要的注释，非常好
同学买了，看了一下觉得不错，就买了。对练习编程很有帮助。
内容全面，适合自学使用
书的内容丰富，纸张比较薄。另外，书里面有程序代码。应该是不错的图相关理论和算法的书籍。
讲的挺细的，感觉很好~
很好，但是封面有点皱
东西总体上不错，要是有配套光盘就好了