C算法（第二卷 图算法）（第三版）

　　 这一套算法系列书介绍了当今最重要的算法，共分3卷，这是第2卷（第五部分），集中讲解图算法。本书共有6章（第17章～第22章）。第17章详细讨论图性质和类型，第18章~第22章分别讲解图搜索、有向图和DAG、最小生成树、最短路径以及网络流。书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习。
　　 本书可作为高等院校计算机相关专业算法与数据结构课程的教材和补充读物，也可供自学之用。
　　

第五部分　图算法
第17章 图性质和类型　2
17.1 术语　4
练习　11
17.2 图adt　12
练习　15
17.3 邻接矩阵表达方式　16
练习　19
17.4 邻接表表达方式　20
练习　22
17.5 变体、扩展和开销　23
练习　27
17.6 图生成器　29
练习　36
17.7 简单路径、欧拉路径和哈密顿路径　38
练习　49
17.8 图处理问题　50
练习　56
第18章 图搜索　58
18.1 探索迷宫　58

　　 将数据结构和算法比作计算机科学的基石毫不为过，追求程序的高效是永恒的主题。Robert Sedgewick以三卷Algorithms in C宏大篇幅对算法的意义进行了全新的诠释(第三卷尚未出版)。算法已不再是纯粹的运算实现，它已经发展成一门设计艺术!新版AlgorithmsJn C不仅浓缩了过去几十年间应用于计算机科学领域的最重要、最高效算法，而且紧紧抓住算法的性能特征进行讨论。权威的资料、层次分明的讲解、丰富的配套练习，正是全世界无数院校将它作为算法首选教科书的原因。
　　 本书为Algorithms in C的第二卷，主要内容包括图性质和类型、图搜索、有向图、DAG、最小生成树、最短路径以及网络流。为了便于教师因材施教，全书内容安排层次性清晰、重点突出。与传统参考书相比，主要有如下特点：
　　 ． 各章内容相对独立，可以单独阅读，或者根据实际教学需要，选择性地组合讲解。
　　 ． 为所有重要算法提供了可靠的实现代码。
　　 ． 配套插图丰富，并提供了详细的注释，使学习效果事半功倍。
　　 ． 提供了大量练习。更重要的是，作者将这些练习按不同层次、不同学习目的进行了分类。
　　 ． 详尽的参考文献，供读者进一步学习。
　　 在翻译过程中，我感觉最深刻的还有两点。第一，作者所提供的所有源码尽量保持统一的风格、尽量使用抽象数据类型，因此，用其他高级编程语言来改写这些程序可以轻松实现。第二，全书将算法分析与数据结构的讲解融为一体。这种相得益彰的讲授方式的优势不言而喻。
　　 作为译者，也作为读者，面对这些优秀的算法，我毫不犹豫地将它们运用到我的编程实践中。在应用实践中，有以下几点体会：
　　 ． 应用某一算法前，建议先掌握其性能特征，确保选择的算法不一定是最快的，但必须是最优的。
　　 ． 要透彻理解文中讲解的算法原理，最好的办法就是完成每一章后面的相关练习。
　　 为了方便读者的学习，中文版提供了英、中文对照的索引，并按字母顺利排列。
　　 在我国，Algorithms in C的影印版已经用作许多高校的算法和数据结构教学的参考书。因此，为广大师生和自学者早日奉上中文版无疑具有重要的意义，也使我感觉到责任的重大。但由于水平有限，且时间仓促，错误在所难免，希望广大读者不吝指正。我的联系E-mail：web_zhou@21cn．com。
　　 译者
　　 2003年8月
　　

　　 图和图算法在现代计算机应用中广泛流行。本书所讨论的图算法，都是实际中解决图问题的最重要的已知方法。本书的主要宗旨是让越来越多需要了解这些算法的人能够掌握这些方法及基本原理。书中根据基本原理从基本信息开始循序渐进地讲解，然后再介绍一些经典方法，最后介绍仍在进行研究和发展的现代技术。精心挑选的实例、详尽的图示以及完整的实现代码与正文中的算法和应用描述相辅相成。
　　 算法
　　 这本书是三卷中的第二卷，全书的目的是综述当今程序员使用的最重要的计算机算法。第一卷(第一部分到第四部分)包括基本概念(第一部分)、数据结构(第二部分)、排序算法(第三部分)以及搜索算法(第四部分)。本卷(第五部分)包括图和图算法。第三卷(待出版)(第六部分到第八部分)包括字符串(第六部分)、计算几何学(第七部分)以及高级算法与应用(第八部分)。
　　 这些书可作为计算机科学的前期课程教材，供学生在掌握了基本编程技能并熟悉计算机系统之后、但在选修计算机科学或计算机应用高级领域中的专业课程之前选修。这些书也可以作为从事计算机系统或应用程序开发人员的自学教材或参考书，因为它们包含有用算法的实现以及这些算法性能特征的详细信息。本系列书讲解全面，无疑是非常合适的算法导论书。
　　 在这三卷书中，第一、二卷已是第三版，世界各地的许多学生和程序员多年来一直广泛使用。我全部重写了新版内容，添加了上千个新练习、上百幅新图示以及许多新程序。我还为所有插图和程序添加了详细的注释。这些新材料既包含了一些新主题，还对许多经典算法提供了更全面的解释。整本书还添加了一项重点内容，即抽象数据类型，使得这些程序更加通用、更适应于现代面向对象编程环境。阅读过旧版的读者在新版中可以学到大量新知识；所有读者都可以阅读到丰富的教学材料，通过它们可以快速掌握一些重要概念。
　　 这本书不是只为程序员和计算机科学专业的学生而写。几乎每一位使用计算机的人都希望更快地解决较大的问题。本书中的算法代表过去50年的知识发展水平，它们已经成为针对各种不同的应用高效使用计算机不可或缺的武器。从物理学上的付—体模拟(N-body simulation)问题到分子生物学中的遗传序列问题，这里描述的基本方法已成为科学研究中的核心要素；而且从数据库系统到互联网搜索引擎，它们已成为现代软件系统的核心部分。随着计算机的应用范围越来越广泛，一些基本算法的影响也随之增大，尤其是本卷介绍的基本图算法。本书的目标就是作为一种宝贵的资源，让学生和专业人员在所从事的计算机应用中，在需要时可以掌握并巧妙地使用图算法。
　　 讨论范围
　　 本书共6章，包括图性质和类型、图搜索、有向图、最小生成树、最短路径和网络。图算法的基本问题涉及范围较广，这里的讨论是为了让读者了解得尽可能广泛。
　　 如果你选修过算怯设计和分析基本原理方面的课程，而且具有某种高级语言(如C、Java或C++)的编程经验，则从本书受益最大。无疑，学习C算法(第三版，第一卷)后，就能顺利过渡到本卷的学习了。本卷假设读者己具备了数组、链表、ADT设计、运用优先队列、符号表以及并集-查找ADT方面的基本知识，这些知识在第一部分一第四部分中均可找到(在其他很多算法和数据结构导论的书中也可以找到)。
　　 ，图和图算法的基本性质从基本原理开始逐渐深入进行介绍，但要完全理解算法的性质，则需要深厚且深奥的数学知识。尽管高级数学概念的讨论简短、概括性强而且具有描述性，但与学习第一部分到第四部分的内容相比，要掌握图算法，必定需要更丰富的数学知识。同样，数学知识背景深浅不一的各位读者也可以从本书中汲取营养。本书的内容安排特别适合各层次读者的学习，应当理解且被每个人运用的基本图算法与那些并非每个人都理解的高级算法之间的区别并不大。本书的主要目的是讲解一些重要算法以及其他相关方法，而不是讲授所有数学知识。但严格的数学处理通常会得到优秀的程序，因此，在进行准确的理论分析与实践需求之间，在不失准确性的前提下，我们尽量寻求最佳平衡点。
　　 如何在课程中使用
　　 根据教师在教学方法上的差异以及学生预备知识的多寡，讲授本书的方式可以灵活多变。这里描述的算法多年来得到了广泛的应用，而且代表着在职程序员以及计算机科学学生的核心知识面。本书包含数据结构和算法方面充分的基本材料，因此，可以用于数据结构课程和算法的教学。同时，本书提供了图算法方面的详尽知识，还讨论了一些高级主题，因此可用于图算法的教学。一些老师可能希望重点讲解实现以及实际应用方面的问题，还有一些老师可能希望重点讨论算法分析和理论概念。
　　 对于讲解更全面的课程，本书也可以与第一部分到第四部分一起进行讲授。因此，教师可以按统一的教学方式讲授基础知识、数据结构、排序、搜索和图算法。访问本书的主页，可以找到用于授课的整套幻灯片、示例编程作业布置、学生使用的交互练习以及其他一些教学材料。
　　 书中的练习分为几类(在这一版本中，几乎所有练习都是新添加的)。有些练习是为了测试读者对课文内容的理解，只是要求读者完成一个例子，或者应用正文中描述的概念。有些练习包括实现代码和算法的综合，或者通过试验研究比较算法的变化版本，并学习其性质。还有一些练习提供了许多重要而详细的信息，这些信息不适合于在正文中讲解。每位读者阅读和思考这些练习都可以得到收获。
　　 算法的实用
　　 任何希望更高效使用计算机的人都可以将本书作为参考书，或者用于自学。具有编程经验的人，在全书各章节都可以找到特定主题的有用信息。在很大程度上，读者可以独立阅读各章节，虽然在某些情况下，某一章中的算法可能用前面章节中介绍的方法。
　　 本书的目标就是学习那些可能运用于实践的算法。它为所有算法提供了足够的信息，读者可以编写有把握的实现代码、有的放矢地调试，并且获得有效算法来解决实际问题，或者为应用程序提供功能。书中提供了所讨论方法的完整实现代码，探讨了一系列相关例程中的运算。因为我们提供的是实际代码，而不是伪码，所以这些程序可以直接运用于实践。从本书的主页可以下载所有程序的源代码。
　　 实际上，整本书为这些算法配制了数百幅说明图示。通过这种直观的演示说明，许多算法变得浅显易懂。
　　 书中详细地讨论了这些算法发挥作用的特征和场合。结合算法分析和理论计算机科学进行讲解虽然不是重点内容，但也安排了适当的篇幅。适当地引用试验和分析结论，来说明优先选择某些算法的原因。必要时，书中还描述所讨论的实际算法与纯理论结论之间的关系。本书综合探讨了算法性能特征以及实现的特定信息。
　　 编程语言