这一套算法系列书介绍了当今最重要的算法，共分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
练习 62
18.2 深度优先搜索 63
练习 66
18.3 图搜索ADT函数 67
练习 70
18.4 DFS森林的性质 71
练习 77
18.5 DFS算法 77
练习 80
18.6 分离性和双连通性 82
练习 88
18.7 广度优先搜索 89
练习 95
18.8 通用图搜索 96
练习 101
18.9 图算法的分析 103
练习 107
第19章 有向图和DAG 108
练习 110
19.1 术语和游戏规则 110
练习 117
19.2 有向图中DFS的剖析 118
练习 124
19.3 可达性和传递闭包 125
练习 134
19.4 等价关系和偏序 135
练习 137
19.5 DAG 138
练习 141
19.6 拓扑排序 142
练习 149
19.7 DAG中的可达性 150
练习 152
19.8 有向图中的强分量 153
练习 159
19.9 再论传递闭包 160
练习 163
19.10 展望 163
练习 165
第20章 最小生成树 167
练习 169
20.1 表达方式 169
练习 173
20.2 MST算法原理 173
练习 179
20.3 普里姆算法和优先级优先搜索 179
练习 187
20.4 Kruskal算法 188
练习 193
20.5 Boruvka算法 193
练习 196
20.6 比较与改进 197
练习 200
20.7 欧几米得MST 201
练习 203
第21章 最短路径 204
练习 209
21.1 基本原理 210
练习 215
21.2 Dijkstra算法 215
练习 221
21.3 所有点对最短路径 223
练习 228
21.4 无环网络中的最短路径 229
练习 235
21.5 欧几米得网络 236
练习 239
21.6 归约 240
练习 251
21.7 负权重 253
练习 265
21.8 展望 267
第22章 网络流 269
22.1 流网络 273
练习 281
22.2 增广路径最大流算法 283
练习 301
22.3 前流推进最大流算法 302
练习 312
22.4 最大流归约 314
练习 326
22.5 最小开销流 328
练习 334
22.6 网络单纯形算法 335
练习 348
22.7 最小开销流归约 349
练习 354
22.8 展望 356
第五部分参考文献 359
索引 361
图和图算法在现代计算机应用中广泛流行。本书所讨论的图算法，都是实际中解决图问题的最重要的已知方法。本书的主要宗旨是让越来越多需要了解这些算法的人能够掌握这些方法及基本原理。书中根据基本原理从基本信息开始循序渐进地讲解，然后再介绍一些经典方法，最后介绍仍在进行研究和发展的现代技术。精心挑选的实例、详尽的图示以及完整的实现代码与正文中的算法和应用描述相辅相成。
算法
这本书是三卷中的第二卷，全书的目的是综述当今程序员使用的最重要的计算机算法。第一卷(第一部分到第四部分)包括基本概念(第一部分)、数据结构(第二部分)、排序算法(第三部分)以及搜索算法(第四部分)。本卷(第五部分)包括图和图算法。第三卷(待出版)(第六部分到第八部分)包括字符串(第六部分)、计算几何学(第七部分)以及高级算法与应用(第八部分)。
这些书可作为计算机科学的前期课程教材，供学生在掌握了基本编程技能并熟悉计算机系统之后、但在选修计算机科学或计算机应用高级领域中的专业课程之前选修。这些书也可以作为从事计算机系统或应用程序开发人员的自学教材或参考书，因为它们包含有用算法的实现以及这些算法性能特征的详细信息。本系列书讲解全面，无疑是非常合适的算法导论书。
在这三卷书中，第一、二卷已是第三版，世界各地的许多学生和程序员多年来一直广泛使用。我全部重写了新版内容，添加了上千个新练习、上百幅新图示以及许多新程序。我还为所有插图和程序添加了详细的注释。这些新材料既包含了一些新主题，还对许多经典算法提供了更全面的解释。整本书还添加了一项重点内容，即抽象数据类型，使得这些程序更加通用、更适应于现代面向对象编程环境。阅读过旧版的读者在新版中可以学到大量新知识；所有读者都可以阅读到丰富的教学材料，通过它们可以快速掌握一些重要概念。
这本书不是只为程序员和计算机科学专业的学生而写。几乎每一位使用计算机的人都希望更快地解决较大的问题。本书中的算法代表过去50年的知识发展水平，它们已经成为针对各种不同的应用高效使用计算机不可或缺的武器。从物理学上的N-体模拟(N-bdy simulahon)问题到分子生物学中的遗传序列问题，这里描述的基本方法已成为科学研究中的核心要素；而且从数据库系统到互联网搜索引擎，它们已成为现代软件系统的核心部分。随着计算机的应用范围越来越广泛，一些基本算法的影响也随之增大，尤其是本卷介绍的基本图算法。本书的目标就是作为一种宝贵的资源，让学生和专业人员在所从事的计算机应用中，在需要时可以掌握并巧妙地使用图算法。
讨论范围
本书共6章，包括图性质和类型、图搜索、有向图、最小生成树、最短路径和网络。图算法的基本问题涉及范围较广，这里的讨论是为了让读者了解得尽可能广泛。
如果你选修过算法设计和分析基本原理方面的课程，而且具有某种高级语言(如C、Java或C++)的编程经验，则从本书受益最大。无疑，学习C算法(第三版，第一卷)后，就能顺
利过渡到本卷的学习了。本卷假设读者已具备了数组、链表、ADT设计、运用优先队列、符号表以及并集-查找ADT方面的基本知识，这些知识在第一部分-第四部分中均可找到(在其他很多算法和数据结构导论的书中也可以找到)。
图和图算法的基本性质从基本原理开始逐渐深入进行介绍，但要完全理解算法的性质，则需要深厚且深奥的数学知识。尽管高级数学概念的讨论简短、概括性强而且具有描述性，但与学习第一部分到第四部分的内容相比，要掌握图算法，必定需要更丰富的数学知识。同样，数学知识背景深浅不一的各位读者也可以从本书中汲取营养。本书的内容安排特别适合各层次读者的学习，应当理解且被每个人运用的基本图算法与那些并非每个人都理解的高级算法之间的区别并不大。本书的主要目的是讲解一些重要算法以及其他相关方法，而不是讲授所有数学知识。但严格的数学处理通常会得到优秀的程序，因此，在进行准确的理论分析与实践需求之间，在不失准确性的前提下，我们尽量寻求最佳平衡点。
如何在课程中使用
根据教师在教学方法上的差异以及学生预备知识的多寡，讲授本书的方式可以灵活多变。这里描述的算法多年来得到了广泛的应用，而且代表着在职程序员以及计算机科学学生的核心知识面。本书包含数据结构和算法方面充分的基本材料，因此，可以用于数据结构课程和算法的教学。同时，本书提供了图算法方面的详尽知识，还讨论了一些高级主题，因此可用于图算法的教学。—些老师可能希望重点讲解实现以及实际应用方面的问题，还有一些老师可能希望重点讨论算法分析和理论概念。
对于讲解更全面的课程，本书也可以与第一部分到第四部分一起进行讲授。因此，教师可以按统一的教学方式讲授基础知识、数据结构、排序、搜索和图算法。访问本书的主页，可以找到用于授课的整套幻灯片、示例编程作业布置、学生使用的交互练习以及其他一些教学材料。
书中的练习分为几类(在这一版本中，几乎所有练习都是新添加的)。有些练习是为了测试读者对课文内容的理解，只是要求读者完成一个例子，或者应用正文中描述的概念。有些练习包括实现代码和算法的综合，或者通过试验研究比较算法的变化版本，并学习其性质。还有一些练习提供了许多重要而详细的信息，这些信息不适合于在正文中讲解。每位读者阅读和思考这些练习都可以得到收获。
算法的实用
任何希望更高效使用计算机的人都可以将本书作为参考书，或者用于自学。具有编程经验的人，在全书各章节都可以找到特定主题的有用信息。在很大程度上，读者可以独立阅读各章节，虽然在某些情况下，某一章中的算法可能用前面章节中介绍的方法。
本书的目标就是学习那些可能运用于实践的算法。它为所有算法提供了足够的信息，读者可以编写有把握的实现代码、有的放矢地调试，并且获得有效算法来解决实际问题，或者为应用程序提供功能。书中提供了所讨论方法的完整实现代码，探讨了一系列相关例程中的运算。因为我们提供的是实际代码，而不是伪码，所以这些程序可以直接运用于实践。从本书的主页可以下载所有程序的源代码。
实际上，整本书为这些算法配制了数百幅说明图示。通过这种直观的演示说明，许多算法变得浅显易懂。
书中详细地讨论了这些算法发挥作用的特征和场合。结合算法分析和理论计算机科学进行讲解虽然不是重点内容，但也安排了适当的篇幅。适当地引用试验和分析结论，来说明优先选择某些算法的原因。必要时，书中还描述所讨论的实际算法与纯理论结论之间的关系。本：口综合探讨了算法性能特征以及实现的特定信息。
编程语言
所有实现都使用C语言写成。任何语言都各有优缺点，我们选用C语言，是因为它得到了广泛应用，而且提供了实现所需要的功能。这些程序很容易转换成其他现代编程语言，因为其中使用的C独特结构很少。在适当的时候，我们尽量使用标准C约定，但这本书不是—本学习C语言编程的参考书。
我们尽量提供雅致、紧凑而且可移植的实现，但要时刻着眼于算法的效率，因此，尽量在编制算法的各阶段留意代码的性能特征。新版中添加了许多新程序，同时重写了许多旧程序，主要是为了让它们更容易用作抽象数据类型实现。针对这些程序，书中讨论了扩展性的比较试验测试。
本书的目的是以尽可能简单、直接的形式讲解算法。尽可能保持一致的风格，让所有程序看起来比较统—。对于本书中的许多算法，不管用何种语言写成，它们均保持相似性。举一个突出的例子，Dijkstra算法就是Dijkstra算法，不管是用Algol-60、Basic、Fortran、Smalltalk、Ada、Pascal、C、C++、Modula-3、PostScript、Java，还是用其他各种编程语言和环境来表达这一算法，它同样证明是—种高效的图处理方法。
第二书店&China-pub战略联盟提供专业服务
第二书店联系方式 010-64348411 webmaster@dearbook.com