Java算法：图算法（第2卷）

　　本书深入介绍了图算法。书中分别对图属性和类型、图搜索、有向图、最小生成树、最短路径以及网络流的有关内容进行了透彻的讨论。书中不仅对基本内容做了全面的阐述，而且对经典算法也提供了详尽的分析，同时还涵盖了有关的高级主题。全书既强调了与实用有关的内容，在分析和理论研究上也很有深度。另外，对于书中提供的算法，读者可以放心实现和调试，并用这些算法来解决问题。本书内容全面、论述清晰，适合于计算机科学和数学领域各个层次的人员使用。图和图算法在当今的计算应用中颇为常见。对于在实际中出现的图处理问题，本书描述了一些已知的最重要的解决方法。由于需要相关知识的人日渐增多，这本书的主要目的就是让他们了解这些方法及其所蕴藏的基本原则。全书由最基本的原则展开，并从基本概念开始介绍，逐步过渡到经典方法，最后对仍在开发中的最新技术加以讨论。在对算法和应用的描述中，我们提供了精心挑选的示例、详尽的图表以及完备的补充说明。算法为研究当前所使用的最为重要的计算机算法，计划共出版3卷，本书是其中的第2卷。第1卷（第1一Ⅳ部分）所涵盖的是基础知识（第1部分）、数据结构（第Ⅱ部分）、排序算法（第Ⅲ部分）以及查找算法（第Ⅳ部分）；这一卷（第V部分）则讨论图与图算法；而未出版的第3卷（第Ⅵ～Ⅷ部分）将介绍串（第Ⅵ部分）、计算几何（第Ⅶ部分）以及高级算法和应用（第Ⅷ部分）。在学习计算机科学课程之初，即学生已经掌握了基本的编程技巧，熟悉计算机系统，但是尚未选修计算机科学或计算机应用高级领域中的专业课程时，将这些书作为教材是很有用的。这些书也可用于自学，对从事计算机系统或应用程序开发的人来说，将这些书用作参考书也是相当有用的，书中包含了实用算法的实现，并对这些算法的性能特性提供了详尽的信息。该系列图书覆盖面非常之广，因此适于作为这一领域的入门读物。多年以来，《Java算法》一书已由世界各地的学生和程序员广泛使用，而以上这3卷书加在一起则构成了这本书的第3版。在这一版本中，我完全重写了有关内容，并且增加了数千个新练习、数百个新图表以及数十个新程序，而且对所有的图表和程序做了详尽的注释说明。在此不仅涵盖了新的主题，而且还对许多经典算法提供了更为充分的解释。全书强调了抽象数据类型，从而使得有关程序的应用面更广，而且与当今的面向对象编程环境也更为相关。对于已经阅读过本书以前版本的人来说，会从这一版中发现相当多的新内容；而对于所有读者而言，都能从中得到极为丰富的学习资料，可以更好地理解基本概念。这套书不仅适合程序员和计算机科学专业的学生阅读。每一个使用计算机的人都希望它能运行得更快，或者可以解决更大规模的问题。我们所考虑的算法代表了近5年发展起来的知识体系，该体系是在各种各样的应用中有效地使用计算机的基础。从物理学中的多体仿真问题到分子生物学中的基因序列问题，在此所描述的基本方法在科学研究中已日显重要：另外，对于从数据库系统到Internet搜索引擎等当今的软件系统，这些基本方法也已经成为其基本的组成部分。随着计算机应用的覆盖面越来越广，基本算法的影响也日益显著，特别是本书所介绍的基本图算法，作用更为突出。广大学生以及专业人士可能会参与完成各种计算机应用，随着这些应用中相关需求的增长，本书的目标就是要提供一个有效的资源，从而使他们充分了解并明智地使用图算法。本书范围《Java算法》（第3版）的"第V部分：图算法篇"共包括6章，分别介绍图的属性和类型、图搜索、有向图、最小生成树、最短路径以及网。其目的是为了使读者能够了解尽可能多的基本图算法，并对其基本属性有所理解。如果你曾经学过有关算法设计和分析基本原则的课程，并且有利用诸如Java，C++或C等高级语言编程的经验，那么对于在此介绍的内容，就会充分领略到它的价值。当然，《Java算法》（第3版）的第1一Ⅳ部分已经为此做了充分的准备。本书假设你已经对数组、链表以及ADT（AbstractDataType，抽象数据类型）设计等有基本的了解，而且使用过优先队列、符号表以及并查ADT，所有这些在第1一Ⅳ部分中都有详细的描述（而且在另外一些有关算法和数据结构的介绍性文字中也有说明）。图和图算法的基本属性由最基本的原则建立，但要充分理解，则往往需要拥有博大精深的数学背景。尽管在此对高级数学概念的讨论很简短，而且是概括性和描述性的，但与第1一Ⅳ部分所介绍的内容相同，要想对图算法有更深入的认识，自然应该有更高的数学水平。不过广数学水平各不相同的读者都可从此书中获益。这种说法可做如下考虑：相对于并非任何人都能理解的一些高级算法，每个人都应该理解并使用的基本图算法只是略有差异。在此的主要意图是结合贯穿于全书的其他方法来讨论重要的算法，而不是对所有数学知识做全面的介绍。不过，好的数学基础往往要求严格的行事方式，而这通常可使我们得到好的程序，因此我尽量在理论家所崇尚的形式规范性和实践家所需要的内容丰富性之间进行权衡，同时也不损害严格性。教学使用在本书的讲授方式上有很大的灵活性，这取决于教师的偏好，同时也依赖于学生所做的准备。可把本书用作面向初学者的数据结构课程，因为它阐述了足够的基本内容；也可把本书用作面向高水平学生的算法分析与设计课程，因为它不仅足够详细，而且涵盖了高级内容。有些教师可能希望强调与实现和实用有关的内容，而另外一些教师则可能希望把重点放在分析和理论概念上。可将本书与第1一Ⅳ部分结合起来，作为一门更为全面的课程讲授。这样，教师就可以完全用一种一致的风格来介绍基础知识、数据结构、排序、查找和图算法等全部内容。书中的练习（几乎全都是在这一版中新增加的）可分为多种类型。有一些是为了检查对正文中内容的理解，只要求读者完成某个示例，或者应用正文中所描述的概念。另外一些则涉及实现和整理算法，或者进行实验研究，从而对不同算法加以比较以了解其属性。还有一些练习则相当于知识储备，是对一些重要信息所做的相当详细的说明，而这些信息本身不适于放在正文里。阅读这些练习并加以思考，会使每个读者都有意想不到的收获。实用算法任何人若希望更为有效地使用计算机，都可以将这本书作为参考，或用于自学。有编程经验的人可以从书中找到有关一些特定主题的信息。一般地，你可以抽取书中的各章独立地阅读。不过，有些情况下，某一章中的算法可能会用到前一章中所介绍的方法。本书的定位是对很可能会在实际中使用的算法加以研究。本书对所讨论的工具（即算法）提供了详尽的信息，读者可以放心地实现和调试，并用这些算法来解决问题，或在应用中利用它们来提供有关功能。在此对所讨论的方法提供了完整的实现，同时，针对书中一系列一致的示例程序的操作做了描述。由于我们采用了实际代码，而不是编写伪代码，因此这些程序很快就可以在实际中使用。通过访问本书的主页可以得到程序的代码清单。您可以用许多方法使用这些工作程序，从而帮助你研究算法。阅读它们以检查你对算法细节的了解，或用一种方法来处理实例化、边界条件和在编程中可能遇到的其他情况。运行这些程序，看看算法在实际中的表现，以根据经验研究性能，并根据书中提供的表检查结果，或试一下你自己所做的修改。实际上，由算法的一个实际应用已经得到了本书中的数百个图表。许多算法正是通过这些图表所提供的视觉维度直观地发现和得到的。本书将详细讨论这些算法的特性以及它们可能在哪些情况下是有用的。在此可建立算法分析与理论计算机科学之间的联系。在适当的情况下，都将给出经验性的结果以及分析结果，以说明为什么某些算法更为适用。如果有意义，还会对所讨论的实际算法与纯理论结果之间的关系加以描述。对于算法和实现的性能特性的特定信息，全书将对其进行综合性和概要性的讨论。编程语言书中所有实现所用的编程语言均为Java。程序中使用了大量的标准Java习惯用法且对于每个构造，正文中都做了简洁的描述。MikeSchidlowsky和本人基于ADT建立了一种Java编程的风格，并认为这是一个将算法和数据结构表示为实际程序的有效方法。我们在实现的优雅性、简洁性、有效性和可移植性方面做了很大的努力。程序风格会尽可能保持一致，因此类似的程序看-上去也是相似的。本书的目标是以尽可能简单明了的方式宋展示算法。对于许多算法而言，尽管所用的语言不同，但存在着相似性。作为一个突出的例子，Dijkstra算法就是Dijkstra算法，无论采用Algol-6，Basic，Fortran，Smalltalk，Ada，Pascal，C，C++，Modula-3，PostScript，Java，Python，还是任何一种其他的编程语言（这样的语言可谓不计其数）来编写，也不管所在的是何种环境，均可以证实为有效的图处理方法。一方面，采用这些语言（以及其他多种语言）宋实现算法会获得一些经验（本书的C和C++版本已经面世），代码会受到这些经验的影响：另一方面，对于这其中的一些语言，其属性会受其设计人员的经验所左右，而这些经验又来自于他对本书所讨论的部分算法和数据结构的使用。最后，我们认为本书所提供的代码不仅准确地定义了算法，而且在实际工作中也相当有用。

暂缺《Java算法：图算法（第2卷）》作者简介

第17章  图的属性和类型
  17.1  术语
  17.2  图的ADT
  17.3  邻接矩阵表示
  17.4  邻接表表示
  17.5  变化、扩展和开销
  17.6  图生成器
  17.7  简单路径、欧拉路和哈密顿路径
  17.8  图处理问题
第18章  图搜索
  18.1  探索迷宫
  18.2  深度优先搜索
  18.3  图搜索ADT方法
  18.4  DFS森林的属性
  18.5  DFS算法
  18.6  可分离性和重连通性
  18.7  广度优先搜索
  18.8  广义图搜索
  18.9  图算法分析
第19章  有向图和无环有向图
  19.1  术语和游戏规则
  19.2  有向图中的DFS剖析
  19.3  可达性和传递闭包
  19.4  等价关系和偏序
  19.5  无环有向图
  19.6  拓扑排序
  19.7  DAG中的可达性
  19.8  有向图中的强分量
  19.9  再述传递闭包
  19.10  展望
第20章  最小生成树
  20.1  表示
  20.2  MST算法的基本原理
  20.3  Prim算法和优先级优先搜索，
  20.4  Kruskal算法
  20.5  Bomvka算法
  20.6  Lt较与改进
  20.7  欧几里得MST
第21章  最短路径
  21.1  基本原则
  21.2  Dijkstra算法
  21.3  全源最短路径
  21.4  无环网中的最短路径
  21.5  欧几里得网
  21.6  归约
  21.7  负权值
  21.8  展望
第22章  网络流
  22.1  流网络
  22.2  扩充路径最大流算法
  22.3  预流-压入最大流算法
  22.4  最大流归约
  22.5  最小成本流
  22.6  网络单纯形算法
  22.7  最小成本流归约
  22.8  展望