C++算法(第3版)--图算法 (2008 年度畅销榜NO.2635 )

本书所关注的是图算法领域。从实用的视角，以独特的结构将有关内容组织在一起，从而使读者不仅可以对这一领域有系统性的认识，而且还可在实践中灵活使用所提供的算法工具本版中，增加了数以千计的新练习、数百个新图表以及数十个新程序，而且对所有的图表和程序都做了详尽的注释说明；不仅涵盖了新的主题，还对许多经典算法提供了更为充分的解释，所有读者都可以从中得到极为丰富的学习资料，从而埂 好地理解基本概念。
本书以C++作为算法描述语言易于理解、便于应用。可作高校计算机相关专业本科生和研究生的教材和补充读物，也可供相关领域工程技术人员参考。

第1章 图的属性和类型
1.1 术语
1.2 图的ADT
1.3 邻接矩阵表示
1.4 邻接表表示
1.5 变化、扩展和开销
1.6 图生成器
1.7 简单路径、欧拉路径和汉密尔顿路径
1.8 图处理问题

第2章 图搜索
2.1 探索迷宫
2.2 浓度优先搜索
2.3 图搜索ADT函数
2.4 DFS森林的属性
2.5 DFS算法
2.6 可分离性和重连通性
2.7 广度优先搜索
2.8 广义图搜索
2.9 图算法分析

第3章 有向图和无环有向图
3.1 术语和游戏规则
3.2 有向图中DFS剖析
3.3 可达性和传递闭包
3.4 等价关系和偏序
3.5 元环有向图
3.6 拓扑排序
3.7 DAG中的可达性
3.8 有向图中的强分量
3.9 再述传递闭包
3.10 展望

第4章 最小生成树
4.1 表示
4.2 MST算法的基本原理
4.3 Prim算法和优先级优先搜索
4.4 Kruskal算法
4.5 Boruvka算法
4.6 比较与改进
4.7 欧几里得MST

第5章 最短路径
5.1 基本原则
5.2 Dijkstra算法
5.3 全源最短路径
5.4 无环网中的最短路径
5.5 欧几里得网
5.6 归约
5.7 负权值
5.8 展望

第6章 网络流
6.1 流网络
6.2 扩充路径最大流算法
6.3 预流-压入最大流算法
6.4 最大流归约
6.5 最小成本流
6.6 网络单纯形算法
6.7 最小成本流归约
6.8 展望

图和图算法在当今的计算应用中颇为常见。对于在实际中出现的图处理问题，本书描述了一些已知的最重要的解决方法。由于需要相关知识的人日渐增多，这本书的主要目的就是让他们了解这些方法及其所蕴藏的基本原则。全书由最基本的原则展开，并从基本概念开始介绍，逐步过渡到经典方法，最后对仍在开发中的最新技术加以讨论。在对算法和应用的描述中，我们提供了精心挑选的示例、详尽的图表以及完备的补充说明。 算法 《C++算法》研究当前所使用的最为重要的计算机算法本书是其中的图算法卷。在学习计算机科学课程之初，即学生已经掌握了基本的编程技巧，熟悉计算机系统，但是尚未选修计算机科学或计算机应用高级领域中的专业课程时，将本书作为教材是很有用的。本书也可用于自学，对从事计算机系统或应用程序开发的人来说，将本书用作参考书也是相当有用的，书中包含了实用算法的实现，并对这些算法的性能特性提供了详尽的信息。本书适于作为这一领域的入门读物。 多年以来，《C++算法》一书已经得到了世界各地的学生和程序员的广泛使用，在第3版中，我完全重写了有关内容，并且增加了数干个新练习、数百个新图表以及数—卜个新程序，而且对所有的图表和程序做了详尽的注释说明。在此不仅涵盖了新的主题，而且还对许多经典算法提供了更为充分的解释。全书强调了抽象数据类型，从而使得有关程序的应用面更广，而且与当今的面向对象编程环境也更为相关。对于已经阅读过本书以前版本的人来说，会从这一版中找到相当多的新内容：而对于所有读者而言，都能从中得到极为丰富的学习资料，可以更好地理解基本概念。 这些书不仅适合程序员和计算机科学专业的学生阅读。每一个使用计算机的人都希望它能运行得更快，或者可解决更大规模的问题。我们所考虑的算法正代表着近50年发展起来的知识体系，该体系是在各种各样的应用中有效地使用计算机的基础。从物理学中的多体仿真问题到分子生物学中的基因序列问题，在此所描述的基本方法在科学研究中已日显重要：另外，对于从数据库系统到Internet搜索引擎等当今的软件系统，这些基本方法也已经成为其基本的组成部分。随着计算机应用的覆盖面越来越广，基本算法的影响也日益显著，特别是本书所介绍的基本图算法，作用更为突出。广大学生以及专业人士可能会参与完成各种计算机应用，随着这些应用中相关需求的增长，本书的目标就是要提供一个有效的资源，从而使他们充分了解并明智地使用图算法。 本书范围 本书共包括6章，分别介绍图的属性和类型、图搜索、有向图、最小生成树、最短路径以及网。这些描述的目的是为了使读者能够了解尽可能多的基本图算法，并对其基本属性有所理解。 如果你曾经学过有关算法设计和分析基本原则的课程，并且有利用诸如C++，Java或C等高级语言编程的经验，那么对于在此介绍的内容，就会充分领略到它的价值。本书假设你已经对数组、链表以及ADT(Abstract Data Type，抽象数据类型)设计等有了基本的了解，而且使用过优先队列、符号表以及并查ADT。 图和图算法的基本属性由最基本的原则即可建立，但要充分理解，则往往需要拥有博大精深的数学背景。在此对高级数学概念的讨论很简短，而且是概括性和描述性的，要想对图算法有更深入的认识，应该有更高的数学水平。不过，数学水平各不相同的读者都可从此书中获益。这种说法可做如下考虑：相对于并非任何人都能理解的一些高级算法，每个人都应该理解并使用的基本图算法只是略有差异。在此的主要意图是结合贯穿于全书的其他方法来讨论重要的算法，而不是对所有数学知识做全面的介绍。不过，好的数学基础往往要求严格的行事方式，而这通常可使我们得到好的程序，因此我尽量在理论家所崇尚的形式规范性和实践家所需要的内容丰富性之间进行权衡，同时也不损害严格性。