算法：C语言实现—第5部分，图算法(原书第3版)
点击看大图基本信息
- 作者： （美）Robert Sedgewick
- 译者： 霍红卫
- 丛书名： 计算机科学丛书
- 出版社：机械工业出版社
- ISBN：9787111285052
- 上架时间：2009-12-17
- 出版日期：2010 年1月
- 开本：16开
- 页码：303
- 版次：3-1
- 所属分类：
计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
推荐阅读
内容简介回到顶部↑
本书是深入论述算法的三卷本教程《算法：c语言实现》（第3版）中的第二卷——图算法。作者在这次修订中重写了许多内容，增加了数千个新练习、数百个新图表、数十个新程序，并对图表和程序做了详尽的注释说明。新版中不仅涵盖了新的主题，而且还提供了对许多经典算法的更充分的解释，包括图的性质、图搜索、有向图、最小生成树、最短路径和网。本书涵盖了足够的基本内容及较详细的图算法高级主题，既可单独用作数据结构与算法课程的教材，也可与第一卷（第1～4部分）结合使用。.
本书适合高等院校计算机专业师生参考，也可供软件开发人员参考。..
本书是sedgewick彻底修订和重写的c算法系列的第二本，集中讲解图算法。全书共有6章 (第17～22章)。第17章详细讨论图性质和类型，第18～22章分别讲解图搜索、有向图和dag、最小生成树、最短路径以及网络流。
书中提供了用c语言描述的完整算法源程序，并且配有丰富的插图和练习。作者用简洁的实现将理论和实践成功地结合了起来，这些实现均可在真实应用上测试，使得本书自问世以来备受程序员的欢迎。
本书可作为高等院校计算机相关专业算法与数据结构课程的教材和补充读物，也可供自学之用。
本书作者的网站http://www.cs.princeton.edu/～rs/为程序员提供了本书的源代码和勘误表。...
本书适合高等院校计算机专业师生参考，也可供软件开发人员参考。..
本书是sedgewick彻底修订和重写的c算法系列的第二本，集中讲解图算法。全书共有6章 (第17～22章)。第17章详细讨论图性质和类型，第18～22章分别讲解图搜索、有向图和dag、最小生成树、最短路径以及网络流。
书中提供了用c语言描述的完整算法源程序，并且配有丰富的插图和练习。作者用简洁的实现将理论和实践成功地结合了起来，这些实现均可在真实应用上测试，使得本书自问世以来备受程序员的欢迎。
本书可作为高等院校计算机相关专业算法与数据结构课程的教材和补充读物，也可供自学之用。
本书作者的网站http://www.cs.princeton.edu/～rs/为程序员提供了本书的源代码和勘误表。...
作译者回到顶部↑
目录回到顶部↑
出版者的话.
译者序
中文版序
前言
第五部分图算法
第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算法
译者序
中文版序
前言
第五部分图算法
第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算法
译者序回到顶部↑
本书是算法方面的优秀著作之一。它系统地阐述了算法学的特征以及算法的应用领域，讨论了算法分析在理论计算机科学中的作用。并通过实验数据和分析结果表明选择何种算法来解决实际应用问题。这卷书对图的性质和类型、图搜索、有向图、最小生成树、最短路径及网络流等内容进行了透彻的论述。通过归约的概念，建立了调度问题与最短路径问题之间的关系。.
这本书不仅适合于软件设计人员和计算机科学专业的学生，而且也适合于那些想利用计算机并想使它更有效或是想要解决更大问题的人们。这本书中的算法代表了图算法领域所研究的知识主体。对于大量的应用问题，这些知识主体已经成为有效使用计算机的不可缺少的部分，尤其体现在网络算法、电路设计、调度、事务处理、资源分配等领域，在此所描述的基本方法在这些领域的科学研究及应用中已日显重要。作为最有影响的搜索引擎之一Google，其中最有名的PageRank算法就是图模型成功应用的一个典型代表。
本书主要内容及特点如下：
对于图的性质及类型做了完整的综述。..
提供了有向图、最小生成树、最短路径及网络流方面的诸多算法，这些算法是计算机科学的核心基础。
对算法提供了很多可视化的信息，还有大量实验研究和基本分析研究，从而为选择算法解决实际应用问题提供了依据。
提供了700多个练习题，从而有助于深入理解算法的特征以及设计有效的算法。
本书以大量图例说明算法的工作过程，使得算法更加易于理解和掌握。
本书提供了读者易于实现和调试的C语言描述的算法的详尽信息，并通过示例程序展示了算法工作的详尽过程。
适合作为高等院校算法设计课程的教材，同时可作为从事软件开发和工程设计的专业人员的参考书。
由于时间较紧及译者水平有限，译文难免有错误及不妥之处，恳请读者批评指正。
最后感谢本书的编辑们所做的细致工作，使得本书的文字更加优美和流畅。...
霍红卫
西安电子科技大学计算机学院
2009年9月
这本书不仅适合于软件设计人员和计算机科学专业的学生，而且也适合于那些想利用计算机并想使它更有效或是想要解决更大问题的人们。这本书中的算法代表了图算法领域所研究的知识主体。对于大量的应用问题，这些知识主体已经成为有效使用计算机的不可缺少的部分，尤其体现在网络算法、电路设计、调度、事务处理、资源分配等领域，在此所描述的基本方法在这些领域的科学研究及应用中已日显重要。作为最有影响的搜索引擎之一Google，其中最有名的PageRank算法就是图模型成功应用的一个典型代表。
本书主要内容及特点如下：
对于图的性质及类型做了完整的综述。..
提供了有向图、最小生成树、最短路径及网络流方面的诸多算法，这些算法是计算机科学的核心基础。
对算法提供了很多可视化的信息，还有大量实验研究和基本分析研究，从而为选择算法解决实际应用问题提供了依据。
提供了700多个练习题，从而有助于深入理解算法的特征以及设计有效的算法。
本书以大量图例说明算法的工作过程，使得算法更加易于理解和掌握。
本书提供了读者易于实现和调试的C语言描述的算法的详尽信息，并通过示例程序展示了算法工作的详尽过程。
适合作为高等院校算法设计课程的教材，同时可作为从事软件开发和工程设计的专业人员的参考书。
由于时间较紧及译者水平有限，译文难免有错误及不妥之处，恳请读者批评指正。
最后感谢本书的编辑们所做的细致工作，使得本书的文字更加优美和流畅。...
霍红卫
西安电子科技大学计算机学院
2009年9月
前言回到顶部↑
图和图算法在现代计算机应用中颇为常见。对于在实际中出现的一些图处理问题，本书描述了目前最重要的解决方法。由于需要相关知识的人日渐增多，本书的主要目标是使读者了解这些方法及其所蕴含的基本原理。本书从基本原理展开，并从基本信息开始，从经典方法到现代仍在研发中的技术逐一展开讨论。精心选择的示例、详尽的图表以及完善实现的补充材料无一不体现在算法和应用的描述中。.
算法
本书是对当前使用的最重要的计算机算法进行深入研究的三卷中的第二卷：图算法。第一卷（第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。它们都在前四部分中描述过（同时也在其他关于算法与数据结构的书中介绍过）。
图和图算法的基本性质根据基本原理即可确立，但要充分理解算法的性质却需要扎实的数学基础。尽管这里所讨论的高级数学概念是简明的、概括性的和描述性的，但相对于前四部分的主题，还是需要读者有较好的数学基础才能更深入地理解图算法。不过，有不同数学基础的读者都可从中受益。这是因为每个人应该理解并使用的基本图算法只是与并非所有人都理解的高级算法略有差异。在此的主要意图是把一些重要的算法与贯穿本书的其他一些方法放在一起讨论，而不是对所有数学知识做全面的介绍。但是，严谨性是好的数学基础所要求的，由此可以得到好的程序。因此我尽量在理论家所喜爱的形式化处理和实践家所需要的内容丰富性之间进行权衡，同时不失严谨性。
教学用法
在教学中如何使用本书内容有很大的灵活性，这取决于教师的偏好以及学生所做的准备。这里所描述的算法多年以来已经得到广泛应用，而且无论对于从事实际工作的程序员还是计算机科学专业的学生，这些算法都代表了基本的知识体系。书中涵盖了足够的基本内容可用作数据结构和算法课程的学习，也有足够详细的高级主题用于图算法课程。有些教师可能希望强调与实现和实践有关的内容，而另外一些教师则可能把重点放在分析和理论概念上。
也可把本书与前四部分的某些内容结合起来作为一个更为全面的课程教材。这样，教师就可以用一种一致的风格来讲授基础知识、数据结构、排序、搜索和图算法的内容。教学中使用的幻灯片、程序设计示例作业、为学生提供的交互式练习以及与课程有关的其他资料都可在本书的主页上找到。
书中的练习（几乎全都是在这一版中新增加的）可分为几类。一类练习的目的是为了测试对正文中内容的理解，要求读者能够完成某个例子或应用正文中描述的概念。另一类练习则涉及实现算法和把算法整理到一起，或者进行实验研究从而对各种算法进行比较以及了解其性质。还有一类练习则是一些重要信息的知识库，其详细程度本身不适合放在正文中。阅读并思考这些练习，会使每个读者受益匪浅。
实用算法
任何人若希望更有效地使用计算机，都可以把这本书用作参考书，或用于自学。有程序设计经验的人可以从本书中找到有关某个特殊主题的信息。从很大程序上说，尽管某些情况下某一章中的算法使用了前一章中的方法，但读者仍可以独立于本书的其他章节阅读本书的某个章节。
本书的定位是研究实用的算法。本书提供了算法的详尽信息，读者可以放心地实现和调试算法，并使算法能够用于求解某个问题，或者为某个应用提供相关功能。书中包括了所讨论的方法的完整实现，并在一系列一致的示例程序中给出了这些操作的描述。由于我们使用了实际代码，而不是伪代码，因而在实际中可以很快地使用这些程序。通过访问本书的主页可以得到程序的代码清单。
实际上，书中算法的一个实际应用会产生数百幅图表。正是这些图表提供的立体视觉直观地发现了许多算法。
本书详细讨论了算法的特征以及它们可能应用的场合。尽管并不强调，但是书中论述了算法分析与理论计算机科学的联系。在适当的时候，书中都给出了经验性的数据和分析结果用以说明为什么选择使用某些算法。如果有趣，书中还会描述所讨论的实际算法与纯理论结果之间的关系。关于算法性能特征和实现的特定信息的综合、概括和讨论都会贯穿本书的始终。
编程语言
算法
本书是对当前使用的最重要的计算机算法进行深入研究的三卷中的第二卷：图算法。第一卷（第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。它们都在前四部分中描述过（同时也在其他关于算法与数据结构的书中介绍过）。
图和图算法的基本性质根据基本原理即可确立，但要充分理解算法的性质却需要扎实的数学基础。尽管这里所讨论的高级数学概念是简明的、概括性的和描述性的，但相对于前四部分的主题，还是需要读者有较好的数学基础才能更深入地理解图算法。不过，有不同数学基础的读者都可从中受益。这是因为每个人应该理解并使用的基本图算法只是与并非所有人都理解的高级算法略有差异。在此的主要意图是把一些重要的算法与贯穿本书的其他一些方法放在一起讨论，而不是对所有数学知识做全面的介绍。但是，严谨性是好的数学基础所要求的，由此可以得到好的程序。因此我尽量在理论家所喜爱的形式化处理和实践家所需要的内容丰富性之间进行权衡，同时不失严谨性。
教学用法
在教学中如何使用本书内容有很大的灵活性，这取决于教师的偏好以及学生所做的准备。这里所描述的算法多年以来已经得到广泛应用，而且无论对于从事实际工作的程序员还是计算机科学专业的学生，这些算法都代表了基本的知识体系。书中涵盖了足够的基本内容可用作数据结构和算法课程的学习，也有足够详细的高级主题用于图算法课程。有些教师可能希望强调与实现和实践有关的内容，而另外一些教师则可能把重点放在分析和理论概念上。
也可把本书与前四部分的某些内容结合起来作为一个更为全面的课程教材。这样，教师就可以用一种一致的风格来讲授基础知识、数据结构、排序、搜索和图算法的内容。教学中使用的幻灯片、程序设计示例作业、为学生提供的交互式练习以及与课程有关的其他资料都可在本书的主页上找到。
书中的练习（几乎全都是在这一版中新增加的）可分为几类。一类练习的目的是为了测试对正文中内容的理解，要求读者能够完成某个例子或应用正文中描述的概念。另一类练习则涉及实现算法和把算法整理到一起，或者进行实验研究从而对各种算法进行比较以及了解其性质。还有一类练习则是一些重要信息的知识库，其详细程度本身不适合放在正文中。阅读并思考这些练习，会使每个读者受益匪浅。
实用算法
任何人若希望更有效地使用计算机，都可以把这本书用作参考书，或用于自学。有程序设计经验的人可以从本书中找到有关某个特殊主题的信息。从很大程序上说，尽管某些情况下某一章中的算法使用了前一章中的方法，但读者仍可以独立于本书的其他章节阅读本书的某个章节。
本书的定位是研究实用的算法。本书提供了算法的详尽信息，读者可以放心地实现和调试算法，并使算法能够用于求解某个问题，或者为某个应用提供相关功能。书中包括了所讨论的方法的完整实现，并在一系列一致的示例程序中给出了这些操作的描述。由于我们使用了实际代码，而不是伪代码，因而在实际中可以很快地使用这些程序。通过访问本书的主页可以得到程序的代码清单。
实际上，书中算法的一个实际应用会产生数百幅图表。正是这些图表提供的立体视觉直观地发现了许多算法。
本书详细讨论了算法的特征以及它们可能应用的场合。尽管并不强调，但是书中论述了算法分析与理论计算机科学的联系。在适当的时候，书中都给出了经验性的数据和分析结果用以说明为什么选择使用某些算法。如果有趣，书中还会描述所讨论的实际算法与纯理论结果之间的关系。关于算法性能特征和实现的特定信息的综合、概括和讨论都会贯穿本书的始终。
编程语言
序言回到顶部↑
自本书首次在英国出版以来，学生们学习算法的方法一直在发生着深刻的转变。具体来说，个人电脑和工作站的广泛使用，意味着每个学生都可以实现所学的每个算法。中国的教师、学生以及读者谁利用了这种转变，就有机会获得关于算法的更广泛素材的深层次的理解，这是前所未有的。.
学生们可能知道，书中的所有代码均已实现并测试过。出现在书中的代码可在网上得到，每个学生应该从一开始，就习惯性地运行每个算法，测试它的各种输入，开发基本的实验结果，并比较同一任务的不同算法的性能。有了这个准备，学生通过运行算法，往往能回答所想到的算法问题。如果学生想到改进算法的办法，可以进行深入的研究以确定是否会这样。我确信，随着成千上万（甚至百万）新一代的学生学会以这种具体方式所表示的算法，就会发现这些算法新的变型以及发现求解所涉及问题的新算法。..
教师可以鼓励学生利用本书所构建的抽象层的知识来详细了解每个算法的性质。当学生首次遇到优先队列和符号表这样的数据结构时，它们看起来相当抽象，但这些数据结构在开发复杂实际现实问题的有效解决方案方面起着重要的作用。有了对于基本抽象的扎实理解，学生就可准备欣赏它们在解决更加困难问题中的重要性。教师要鼓励学生理解每个算法和数据结构，这样他们将能解决现实世界的问题，而这些是要通过合理地使用基本算法才能做到的。
正如原书练习中的注释中提到的，有太多的练习需要人们尝试。我能给中国学生、教师以及读者的最重要的建议，就是阅读所有的练习，并使用它们（和文中的基本素材）作为我们扩充关于算法知识的起点。...
Robert Sedgewick
2009年10月
学生们可能知道，书中的所有代码均已实现并测试过。出现在书中的代码可在网上得到，每个学生应该从一开始，就习惯性地运行每个算法，测试它的各种输入，开发基本的实验结果，并比较同一任务的不同算法的性能。有了这个准备，学生通过运行算法，往往能回答所想到的算法问题。如果学生想到改进算法的办法，可以进行深入的研究以确定是否会这样。我确信，随着成千上万（甚至百万）新一代的学生学会以这种具体方式所表示的算法，就会发现这些算法新的变型以及发现求解所涉及问题的新算法。..
教师可以鼓励学生利用本书所构建的抽象层的知识来详细了解每个算法的性质。当学生首次遇到优先队列和符号表这样的数据结构时，它们看起来相当抽象，但这些数据结构在开发复杂实际现实问题的有效解决方案方面起着重要的作用。有了对于基本抽象的扎实理解，学生就可准备欣赏它们在解决更加困难问题中的重要性。教师要鼓励学生理解每个算法和数据结构，这样他们将能解决现实世界的问题，而这些是要通过合理地使用基本算法才能做到的。
正如原书练习中的注释中提到的，有太多的练习需要人们尝试。我能给中国学生、教师以及读者的最重要的建议，就是阅读所有的练习，并使用它们（和文中的基本素材）作为我们扩充关于算法知识的起点。...
Robert Sedgewick
2009年10月
媒体评论回到顶部↑
对于在数学分析方面不算熟练且需要留意理论算法的普通程序员来说，本书是一本可读性很强的优秀读本。他们应该会从中获益良多。.
——Steve Summit，《C Programming FAQs》的作者
Sedgewick有一种真正的天赋，可以用易于理解的方式来解释概念。书中采用了一些易懂的实战程序，其篇幅仅有一页左右，这更是锦上添花。而书中大量采用的图、程序、表格也会极大帮助读者的学习和理解，这使本书更显得与众不同。..
——William A. Ward，南亚拉巴马大学...
——Steve Summit，《C Programming FAQs》的作者
Sedgewick有一种真正的天赋，可以用易于理解的方式来解释概念。书中采用了一些易懂的实战程序，其篇幅仅有一页左右，这更是锦上添花。而书中大量采用的图、程序、表格也会极大帮助读者的学习和理解，这使本书更显得与众不同。..
——William A. Ward，南亚拉巴马大学...
加载中...
