前言
本书是在我的在线算法课程基础之上编写的，是4卷本系列的第2卷，第1卷是《算法详解（卷1）——算法基础》。这个在线课程2012年起就定期发布，它建立在我在斯坦福大学讲授多年的本科课程的基础之上。这个系列的卷1并不是阅读卷2的先决要求，任何符合下面“本书的目标读者”中所描述背景并熟悉渐进性表示法（附录对这个主题进行了回顾）的读者均适合阅读本书。
本书涵盖的内容
本书介绍了下面3个主题的基础知识。
图的搜索和应用
图可用于对许多不同类型的网络（包括道路网、通信网络、社交网络，以及多任务之间的依赖性网络）进行建模。图可能非常复杂，但图存在一些运算速度非常快的基本算法。我们首先讨论对图进行搜索的线性算法。该算法应用范围极广，包括网络分析以及任务序列化等。
最短路径
最短路径问题的目标是计算网络中从点A到点B的最佳路线。这个问题具有一些显而易见的应用，例如计算行车路线等。许多更为通用的规划问题的本质就是计算最短路径。我们将对其中一种图搜索算法进行归纳，进而引出著名的Dijkstra最短路径算法。
数据结构
本书将帮助读者熟悉几种不同的数据结构，它们用于维护不断变化的具有键的对象集合。我们的基本目标是培养一种能力，也就是能够判断哪种数据结构比较适合自己的应用。选读的高级章节为如何从头实现这些数据结构提供了一些指导方针。
我们首先讨论堆，它可以快速识别它所存储对象中具有最小键值的对象，适用于排序、实现优先队列以及以线性时间实现Dijkstra算法等场景。搜索树可以维护它所存储对象的整体键顺序，并支持更丰富的数组操作。散列表对超级快速的查找方式进行了优化，在现代程序中具有极其广泛的应用。我们还将讨论布隆过滤器，它是散列表的“近亲”。布隆过滤器的空间需求比散列表的低，但它偶尔会出现错误。
关于本书内容的更详细介绍，可以阅读每章的“本章要点”，它对每一章的内容，特别是那些重要的概念进行了总结。书中带星号的章节是难度较高的章节。时间较为紧张的读者在第一遍阅读时可以跳过这些章节，这并不会影响本书阅读的连续性。
“算法详解”系列其他几卷所涵盖的主题
“算法详解”系列图书的第1卷《算法详解（卷1）——算法基础》讨论了渐进性表示法（大O表示法以及相关表示法），分治算法和主方法，随机化的QuickSort及其分析以及线性时间的选择算法。“算法详解”系列图书的第3卷重点讨论了贪婪算法（调度、最小生成树、集群、霍夫曼编码）和动态编程（背包、序列对齐、最短路径、最佳搜索树等）。“算法详解”系列图书的第4卷则介绍NP完整性及其对算法设计师的意义，还讨论了处理难解的计算问题的一些策略，包括对试探法和局部搜索的分析。
读者的收获
精通算法需要大量的时间和精力，那为什么要学习算法呢？
成为更优秀的程序员
读者将学习一些令人炫目的用于处理数据的高速子程序以及一些实用的数据结构，它们用于组织数据，可以直接部署到自己的程序中。实现和使用这些算法将扩展并提高读者的编程技巧。读者还将学习基本的算法设计范式，它们与许多不同领域的不同问题密切相关，并且可以作为预测算法性能的工具。这些“算法设计模式”可以帮助读者为自己碰到的问题设计新算法。
加强分析技巧
读者将获得大量对算法进行描述和推导的实践机会。通过数学分析，读者将对“算法详解”系列图书所涵盖的特定算法和数据结构产生深刻的理解。读者还将掌握一些广泛用于算法分析的实用数学技巧。
形成算法思维
在学习了算法之后，很难发现有什么地方没有它们的踪影。无论是坐电梯、观察鸟群，还是管理自己的投资组合，甚至是观察婴儿的认知，算法思维如影随形。算法思维在计算机科学之外的领域，包括生物学、统计学和经济学，越来越实用。
融入计算机科学家的圈子
研究算法就像是观看计算机科学最近60年发展的精彩剪辑。当读者参加一场计算机科学界的鸡尾酒会，会上有人讲了一个关于Dijkstra算法的笑话时，你就不会感觉自己被排除在这个圈子之外了。在阅读了本系列图书之后，读者将了解许多这方面的知识。
在技术访谈中脱颖而出
在过去这些年里，有很多学生向我讲述了“算法详解”系列图书是怎样帮助他们在技术访谈中大放异彩的。
其他算法教材
“算法详解”系列图书只有一个目标：尽可能以读者容易接受的方式介绍算法的基础知识。读者可以把本书看成是专家级算法教师的课程记录，老师以课程的形式传道解惑。
市面上还有一些非常优秀的更为传统、全面的算法教材，它们都可以作为“算法详解”系列关于算法的其他细节、问题和主题的有益补充。我鼓励读者探索和寻找自己喜欢的其他教材。另外，还有一些图书的出发点有所不同，它们偏向于站在程序员的角度寻找一种特定编程语言的成熟算法实现。网络中存在大量免费的这类算法的实现。
本书的目标读者
“算法详解”系列图书以及作为其基础的在线课程的整体目标是尽可能地扩展读者群体的范围。学习我的在线课程的人具有不同的年龄、背景、生活方式，有大量来自全世界各个角落的学生（包括高中生、大学生等）、软件工程师（包括现在的和未来的）、科学家和专业人员。
本书并不是讨论编程的，理想情况下读者至少应该熟悉一种标准编程语言（例如Java、Python、C、Scala、Haskell等）并掌握了基本的编程技巧。作为一个立竿见影的试验，读者可以试着阅读2.2节。如果读者觉得自己能够看懂，那么看懂本书的其他部分应该也是没有问题的。如果读者想要提高自己的编程技巧，那么可以学习一些非常优秀的讲述基础编程的免费在线课程。
我们还会根据需要通过数学分析帮助读者理解算法为什么能够实现目标以及它是怎样实现目标的。Eric Lehman和Tom Leighton关于计算机科学的数学知识的免费课程是极为优秀的，可以帮助读者复习数学记法（例如Σ和）、数学证明的基础知识（归纳、悖论等）、离散概率等更多知识。
其他资源
“算法详解”系列的在线课程当前运行于Coursera和Stanford Lagunita平台。另外，还有一些资源可以帮助读者根据自己的意愿提升对在线课程的体验。
•视频。如果读者觉得相比阅读文字，更喜欢听和看，那么可以在视频网站的视频播放列表中观看。这些视频涵盖了“算法详解”系列的所有主题。我希望它们能够激发读者学习算法的持续热情。当然，它们并不能完全取代书的作用。
•小测验。读者怎么才能知道自己是否完全理解了本书所讨论的概念呢？散布于全书的小测验及其答案和详细解释就起到了这个作用。当读者阅读这块内容时，最好能够停下来认真思考，然后继续阅读接下来的内容。
•章末习题。每章的末尾都有一些相对简单的问题，用于测试读者对该章内容的理解程度。另外，还有一些开放性的、难度更大的挑战题。本书并未包含章末习题的所有答案，但是读者可以通过本书的论坛（稍后提及）与作者以及其他读者进行交流。
•编程题。许多章的最后是一个建议的编程项目，其目的是通过创建自己的算法工作程序，来增强读者对算法的理解。读者可以在www.algorithmsilluminated.org上找到数据集、测试例以及它们的答案。
•论坛。在线课程能够取得成功的一个重要原因是它们为参与者提供了互相帮助的机会，读者可以通过论坛讨论课程材料和调试程序。本系列图书的读者也有同样的机会，可以通过www.algorithmsilluminated.org参与活动。
致谢
如果没有过去几年里我的算法课程中数以千计的参与者的热情和渴望，“算法详解”系列图书就不可能面世。这些课程既包括斯坦福大学的课程，又包括在线平台的课程。我特别感谢那些为本书的早期草稿提供详细反馈的人：Tonya Blust、Yuan Cao、Jim Humelsine、Vladimir Kokshenev、Bayram Kuliyev、Patrick Monkelban和Daniel Zingaro。
我非常希望得到来自读者的建议和修正意见，读者可通过上面所提到的讨论组与我进行交流。
蒂姆·拉夫加登
英国伦敦，2018年7月