本书是深入论述算法的三卷本教程《算法：C语言实现》（第3版）中的第二卷——图算法。作者在这次修订中重写了许多内容，增加了数千个新练习、数百个新图表、数十个新程序，并对图表和程序做了详尽的注释说明。新版中不仅涵盖了新的主题，而且还提供了对许多经典算法的更充分的解释，包括图的性质、图搜索、有向图、最小生成树、最短路径和网。本书涵盖了足够的基本内容及较详细的图算法高级主题，既可单独用作数据结构与算法课程的教材，也可与第一卷（第1～4部分）结合使用作为一部较全面的教材。

算法：C语言实现（第5部分）图算法 （原书第3版）　
Algorithms in C Part 5, Graph Algorithms
Third Edition
(美)　Robert Sedgewick(普林斯顿大学)　 著　 霍红卫(西安电子科技大学)　 译
对于在数学分析方面不算熟练且需要留意理论算法的普通程序员来说，本书是一本可读性很强的优秀读本。他们应该会从中获益良多。
—— Steve Summit，《C Programming FAQs》的作者
Sedgewick有一种真正的天赋，可以用易于理解的方式来解释概念。书中采用了一些易懂的实战程序，其篇幅仅有一页左右，这更是锦上添花。而书中大量采用的图、程序、表格也会极大帮助读者的学习和理解，这使本书更显得与众不同。
—— William A. Ward，南亚拉巴马大学
本书是Sedgewick彻底修订和重写的C算法系列的第二本，集中讲解图算法。全书共有6章 (第17~22章)。第17章详细讨论图性质和类型，第18~22章分别讲解图搜索、有向图和DAG、最小生成树、最短路径以及网络流。
书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习。作者用简洁的实现将理论和实践成功地结合了起来，这些实现均可在真实应用上测试，使得本书自问世以来备受程序员的欢迎。
本书可作为高等院校计算机相关专业算法与数据结构课程的教材和补充读物，也可供自学之用。
本书作者的网站http://www.cs.princeton.edu/~rs/为程序员提供了本书的源代码和勘误表。
作者简介
Robert Sedgewick拥有斯坦福大学博士学位 (导师为Donald E. Knuth) ，普林斯顿大学计算机科学系教授，Adobe Systems公司董事，曾是Xerox PARC的研究人员，还曾就职于美国国防部防御分析研究所以及INRIA。除本书外，他还与Philippe Flajolet合著了《算法分析导论》一书。

图和图算法在现代计算机应用中颇为常见。对于在实际中出现的一些图处理问题，本书描述了目前最重要的解决方法。由于需要相关知识的人日渐增多，本书的主要目标是使读者了解这些方法及其所蕴含的基本原理。本书从基本原理展开，并从基本信息开始，从经典方法到现代仍在研发中的技术逐一展开讨论。精心选择的示例、详尽的图表以及完善实现的补充材料无一不体现在算法和应用的描述中。
算法
　　本书是对当前使用的最重要的计算机算法进行深入研究的三卷中的第二卷：图算法。第一卷（第1~4部分）覆盖了基本概念（第1部分）、数据结构（第2部分）、排序算法（第3部分）和搜索算法（第4部分）；本卷（第5部分）覆盖了图与图算法；（尚未出版的）第三卷（第6~8部分）覆盖了字符串（第6部分）、计算几何（第7部分）和高级算法及应用（第8部分）。
　　这些书可作为计算机科学低年级本科生的教材。学习本课程之前要求学生掌握基本程序设计技巧并熟知计算机系统，不过尚未选修计算机科学或计算机应用的高级领域的专业课程。这些书还可用作自学或作为从事计算机系统或应用程序开发的参考读本，因为它们包含了实用算法的实现以及关于这些算法性能特征的详尽信息。这些书包含内容广泛，适合作为这一领域的入门读物。
　　多年以来，这三卷书共同构成的《算法：C语言实现》（第3版）已经得到世界各地的学生和程序员的广泛使用。我完全重写了这一版的内容，并且增加了数千个新练习、数百个新图表、数十个新程序以及对图表和程序详尽的注释说明。这个新版本不仅涵盖了新的主题，而且还提供了对许多经典算法的更充分的解释。全书对抽象数据类型的强调使这些程序使用更为广泛，而且在现代面向对象的编程环境中也更为适用。对于已经阅读过以前版本的人来说，会从这一版找到更为丰富的信息；并且所有读者都会从中找到富有教益的内容，有效地学习本书提供的基本概念。
　　这些书适合于程序员和计算机科学专业的学生阅读。每一个使用计算机的人都希望它能运行得更快，或者可解决更大规模的问题。我们所考虑的算法代表了近50年发展起来的知识体系，该体系是在各种应用中有效地使用计算机解决问题不可缺少的部分。从物理学中的N体模拟问题到分子生物学中的基因序列问题，在此所描述的基本方法在科学研究中已日显重要；另外，对于从数据库系统到Internet搜索引擎，这些方法已经成为现代软件系统的重要组成部分。随着计算机应用的覆盖面越来越广，基本算法的影响也日益显著，特别是本书所涵盖的基本图算法，作用更为突出。本书的目标是要提供一种资源，使广大学生以及专业人士可以了解并明智地利用图算法来解决计算机应用中出现的问题。
本书范围
　　本书共6章，包含了图的性质及类型、图搜索、有向图、最小生成树、最短路径和网。希望本书描述的方法使读者能够尽可能广地理解图算法的基本属性。
　　如果读者已经学过算法设计与分析的基本原理，并且有利用C、Java或C++等高级编程语言的经验，你将会更有效地学习本书的内容。当然，可以利用本书第一卷（第1～4部分）做充分的准备。本书假设读者有关于数组、链表和ADT设计的基本知识，并使用过优先队列、符号表以及合并-查找ADT。它们都在前四部分中描述过（同时也在其他关于算法与数据结构的书中介绍过）。
　　图和图算法的基本性质根据基本原理即可确立，但要充分理解算法的性质却需要扎实的数学基础。尽管这里所讨论的高级数学概念是简明的、概括性的和描述性的，但相对于前四部分的主题，还是需要读者有较好的数学基础才能更深入地理解图算法。不过，有不同数学基础的读者都可从中受益。这是因为每个人应该理解并使用的基本图算法只是与并非所有人都理解的高级算法略有差异。在此的主要意图是把一些重要的算法与贯穿本书的其他一些方法放在一起讨论，而不是对所有数学知识做全面的介绍。但是，严谨性是好的数学基础所要求的，由此可以得到好的程序。因此我尽量在理论家所喜爱的形式化处理和实践家所需要的内容丰富性之间进行权衡，同时不失严谨性。
教学用法
　　在教学中如何使用本书内容有很大的灵活性，这取决于教师的偏好以及学生所做的准备。这里所描述的算法多年以来已经得到广泛应用，而且无论对于从事实际工作的程序员还是计算机科学专业的学生，这些算法都代表了基本的知识体系。书中涵盖了足够的基本内容可用作数据结构和算法课程的学习，也有足够详细的高级主题用于图算法课程。有些教师可能希望强调与实现和实践有关的内容，而另外一些教师则可能把重点放在分析和理论概念上。
　　也可把本书与前四部分的某些内容结合起来作为一个更为全面的课程教材。这样，教师就可以用一种一致的风格来讲授基础知识、数据结构、排序、搜索和图算法的内容。教学中使用的幻灯片、程序设计示例作业、为学生提供的交互式练习以及与课程有关的其他资料都可在本书的主页上找到。
　　书中的练习（几乎全都是在这一版中新增加的）可分为几类。一类练习的目的是为了测试对正文中内容的理解，要求读者能够完成某个例子或应用正文中描述的概念。另一类练习则涉及实现算法和把算法整理到一起，或者进行实验研究从而对各种算法进行比较以及了解其性质。还有一类练习则是一些重要信息的知识库，其详细程度本身不适合放在正文中。阅读并思考这些练习，会使每个读者受益匪浅。
实用算法
　　任何人若希望更有效地使用计算机，都可以把这本书用作参考书，或用于自学。有程序设计经验的人可以从本书中找到有关某个特殊主题的信息。从很大程序上说，尽管某些情况下某一章中的算法使用了前一章中的方法，但读者仍可以独立于本书的其他章节阅读本书的某个章节。
本书的定位是研究实用的算法。本书提供了算法的详尽信息，读者可以放心地实现和调试算法，并使算法能够用于求解某个问题，或者为某个应用提供相关功能。书中包括了所讨论的方法的完整实现，并在一系列一致的示例程序中给出了这些操作的描述。由于我们使用了实际代码，而不是伪代码，因而在实际中可以很快地使用这些程序。通过访问本书的主页可以得到程序的代码清单。
　　实际上，书中算法的一个实际应用会产生数百幅图表。正是这些图表提供的立体视觉直观地发现了许多算法。
　　本书详细讨论了算法的特征以及它们可能应用的场合。尽管并不强调，但是书中论述了算法分析与理论计算机科学的联系。在适当的时候，书中都给出了经验性的数据和分析结果用以说明为什么选择使用某些算法。如果有趣，书中还会描述所讨论的实际算法与纯理论结果之间的关系。关于算法性能特征和实现的特定信息的综合、概括和讨论都会贯穿本书的始终。
编程语言
　　书中所有实现所用的程序设计语言均为C语言（本书的C++版本和Java正在开发）。任何特定语言都有优缺点；我们使用C语言是因为它是一种广泛使用的语言，并且能够为本书的实现提供所需的特征。由于没有多少结构是C所特有的，因而用C编写的程序可以很容易地变成用其他现代编程语言编写的程序。在适当的时候，我们会使用标准C中的术语，但本书并不打算成为C程序设计的参考手册。
　　我们力争编写优雅、简明和可移植的代码实现，但同时关注实现的效率，因而我们在开发的各个阶段都试图了解代码的性能特征。在这一版中有很多新的程序，老版的很多程序也已更新，主要的目的是使它们在用作抽象数据类型实现时更为实用。对程序所做的广泛的实验性比较研究贯穿在本书中。
　　本书的目标是以尽可能简单、直接的方式来展示算法。本书使用尽可能一致的风格，因而很多程序看起来是相似的。对于许多算法而言，无论使用哪种语言，算法都具有相似性：例如（选取一个著名的例子）Dijkstra算法就是Dijkstra算法，无论采用Algol60、Basic、Fortran、Smalltalk、Ada、Pascal、C、C++、Modula3、PostScript、Java表示，还是任何一种其他编程语言表示，也不管其所在的环境，它都被证明是一种有效的图处理算法。

有关练习的说明
　　给练习分类是一件充满风险的事情，因为本书读者的知识背景和经验参差不齐。虽然如此，还应适当加上指导，所以许多练习都加了一个记号(共有4种不同记号)，以帮助你判断如何加以解决。
　　测试你对内容理解程度的练习用空心三角符号标识，如下所示：
　172给出下图的所有连通子图。

0102031323


　　通常，这样的练习是与正文中的例子直接相关的。它们的难度不大，但是完成这些练习会使你了解某个事实或掌握某个概念，它们可能是你在阅读正文时感到困惑不解的问题。
　　为正文内容添加新的且需要思考的信息的练习用空心圆符号标识，如下所示：
　　○ 182在对图182和183中所示的迷宫进行Trémaux探索时，以下序列中，哪一个不能作为各交叉点开灯的顺序？

07453162
02643715
05347162
07462135

　　这种练习将鼓励你考虑与正文中内容相关的重要概念，或者回答出现在你阅读正文时遇到的一个问题。即使你没有时间做这些练习，也会发现阅读这些练习是非常有价值的。
　　具有挑战性的练习用黑色圆点标识，如下所示：
　　● 192在线找出一个大型DAG图，可以是一个大型软件系统中函数定义依赖关系所定义的DAG图，也可以一个大型文件系统的目录连接所定义的DAG图。
　　这种练习可能需要花费大量时间才能完成，这取决于你的经验。一般而言，最有效的方法是分几个阶段来解决。
　　少数难度极大的练习(相对于其他大多数练习)用两个(甚至三个)黑色圆点标识，如下所示：
　　●● 2035开发一个用于生成V个顶点、E条边的随机图的合理程序，使得Prim算法的PFS实现（程序204）的运行时间是非线性的。
　　这种练习类似于研究文献上所讨论的问题，但本书中的内容可能会让你做好准备，乐于尝试解决这些问题（而且很可能成功）。
　　对于考察你的程序设计能力和数学能力的练习，则没有明确记号。这些要求程序设计能力或数学分析能力的练习是一种自我检查。我们鼓励所有的读者都通过实现算法来检测对算法的理解程度。
致谢
　　对于本书早期的版本，很多人提供了有用的反馈信息。特别要提出的是普林斯顿大学和布朗大学成百上千的学生们在过去的多年里一直承受着初稿的粗糙。特别要感谢Trina Avery和Tom Freeman对于第一版的出版所给与的帮助；还要感谢Janet Incerpi，是她的创造力和聪明才智使我们使用早期原始的数字排版硬件和软件来制作本书的第一版；要感谢Marc Brown，他参与了算法可视化研究，而本书中的很多图表正来源于此；感谢Dava Hanson，对于我提出的关于C语言方面的所有问题，他总是乐于回答。感谢Kevin Wayne，它耐心回答了我关于网的基本问题。我还要感谢众多读者，他们对各个版本提供了详尽的评论，这其中包括：Guy Almes、Jon Bentley、Marc Brown、Jay Gischer、Allan Heydon、Kennedy Lemke、Udi Manber、Dana Richards、John Reif、M. Rosenfeld、Stephen Seidman、Michael Quinn和William Ward。
　　为了成这一新版本，我有幸与AddisonWesley的Peter Gordon和Helen Goldstein一起工作。他们耐心地指导这个项目的完成，使其经历了从一般性修改到大幅度重写的过程。同样我还有幸与AddisonWesley的许多专业人员一起工作。这个项目的性质使得本书带给他们非同寻常的挑战，对于他们的忍耐力我致以诚挚的感谢。
　　在写这本书的过程中，我得到了两位良师益友。在此我要特别向他们表示感谢。首先，Steve Summit从技术的角度对各版本的初稿都做了仔细的检查，并向我提出了数千条详尽的意见，尤其是关于程序方面的建议。Steve很清楚我的目标是要提供优雅、有效且实用的实现代码，他的意见不仅帮助我给出实现一致性的度量标准，而且还帮助我对其中许多实现做了重大的改进。其次是Lyn Dupre，他也对我的手稿提出了数千条的意见，这些建议对我来说是无价之宝，不仅帮助我改正和避免了许多语法错误，而且更重要的是，使我找到一种一致性的写作风格，由此才使我把如此繁多的技术资料整理在一起。能够有机会向Steve和Lyn学习，我万分感激。他们的投入对于本书的完成至关重要。
　　我在这里所写的内容大多受益于Don Knuth的授课和著作，他是我在斯坦福大学的导师。尽管Don对本书没有直接的影响，但在本书中仍然能够感受到他的存在，因为正是他为算法研究奠定了科学基础，才使像本书这样的工作得以完成。我的朋友兼同事Philippe Flajolet是使算法分析发展成为一个成熟领域的主力，他对这本书具有同样的影响力。
　　非常感谢普林斯顿大学、布朗大学以及法国国立计算机与自动化研究所（Institute National de Recherce en Informatique et Automatique，INRIA）给予的支持，在这些地方，我完成了本书大部分的工作；还要感谢美国国防部防御分析研究所（Institute for Defense Analysis）以及施乐的帕洛阿尔托研究中心（Xeror Palo Alto Research Center），我在他们那里访问期间完成了本书的一些工作。本书的某些部分离不开国家自然科学基金（National Science Foundation）和海军研究中心（Office of Naval Research）的慷慨支持。最后，我要感谢Bill Bowen、Aaron Lemonick和Neil Rudenstine，感谢他们对建立普林斯顿大学学术环境的支持，使我能够在这样良好的环境中，在承担众多其他事务的同时完成本书。
Robert Sedgewick
MarlyleRoi，法国，1983年2月
普林斯顿，新泽西州，1990年1月
詹姆斯镇，罗得岛，2001年5月

同本书影印书 （书号ISBN 7-111-19769-0)

霍红卫　译：暂无简介

本书是算法方面的优秀著作之一。它系统地阐述了算法学的特征以及算法的应用领域，讨论了算法分析在理论计算机科学中的作用。并通过实验数据和分析结果表明选择何种算法来解决实际应用问题。这卷书对图的性质和类型、图搜索、有向图、最小生成树、最短路径及网络流等内容进行了透彻的论述。通过归约的概念，建立了调度问题与最短路径问题之间的关系。
　　这本书不仅适合于软件设计人员和计算机科学专业的学生，而且也适合于那些想利用计算机并想使它更有效或是想要解决更大问题的人们。这本书中的算法代表了图算法领域所研究的知识主体。对于大量的应用问题，这些知识主体已经成为有效使用计算机的不可缺少的部分，尤其体现在网络算法、电路设计、调度、事务处理、资源分配等领域，在此所描述的基本方法在这些领域的科学研究及应用中已日显重要。作为最有影响的搜索引擎之一Google，其中最有名的PageRank算法就是图模型成功应用的一个典型代表。
　　本书主要内容及特点如下：
　　 对于图的性质及类型做了完整的综述。
　　 提供了有向图、最小生成树、最短路径及网络流方面的诸多算法，这些算法是计算机科学的核心基础。
　　 对算法提供了很多可视化的信息，还有大量实验研究和基本分析研究，从而为选择算法解决实际应用问题提供了依据。
　　 提供了700多个练习题，从而有助于深入理解算法的特征以及设计有效的算法。
　　 本书以大量图例说明算法的工作过程，使得算法更加易于理解和掌握。
　　 本书提供了读者易于实现和调试的C语言描述的算法的详尽信息，并通过示例程序展示了算法工作的详尽过程。
　　 适合作为高等院校算法设计课程的教材，同时可作为从事软件开发和工程设计的专业人员的参考书。
　　由于时间较紧及译者水平有限，译文难免有错误及不妥之处，恳请读者批评指正。
　　最后感谢本书的编辑们所做的细致工作，使得本书的文字更加优美和流畅。
霍红卫
西安电子科技大学计算机学院
2009年9月

出版者的话
译者序
中文版序
前言
第五部分图算法
第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4DFS森林的性质
185DFS算法
186可分离性和双连通性
187广度优先搜索
188广义图搜索
189图算法分析
第19章有向图和有向无环图
191术语和游戏规则
192有向图中的DFS剖析
193可达性和传递闭包
194等价关系和偏序
195有向无环图
196拓扑排序
197有向无环图中的可达性
198有向图中的强连通分量
199再论传递闭包
1910展望
第20章最小生成树
201表示
202MST算法的基本原理
203Prim算法和优先级优先搜索
204Kruskal算法
205Boruvka算法
206比较与改进
207欧几里得MST
第21章最短路径
211基本原理
212Dijkstra算法
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展望
第五部分参考文献