推荐一本算法书，这是算法详解系列4卷中其中的一卷。本书是第2卷——图算法和数据结构。本书共有6章，主要介绍了3个主题，分别是图的搜索和应用、最短路径以及数据结构。附录A简单回顾了渐进性表示法。本书的每一章均有小测验、章末习题和编程题，这为读者的自我检查以及进一步学习提供了方便。

《算法详解（卷2）——图算法和数据结构》提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维和计算思维的IT专业人士，以及正在准备面试的应聘者和面试官阅读参考。

《算法详解（卷2）——图算法和数据结构》涵盖的内容

本书介绍了下面3个主题的基础知识。

图的搜索和应用

图可用于对许多不同类型的网络，包括道路网、通信网络、社交网络，以及任务之间的依赖性网络进行建模。图可能非常复杂，但图存在一些运算速度非常快的基本算法。我们首先讨论对图进行搜索的线性算法，其应用范围极广，包括网络分析以及任务序列化等。

最短路径

在最短路径问题中，其目标是计算网络中从点A到点B的最佳路线。这个问题具有一些显而易见的应用，例如计算行车路线等。许多更为通用的规划问题的本质就是计算最短路径的问题。我们将对其中一种图搜索算法进行归纳，进而引出著名的Dijkstra最短路径算法。

数据结构

本书将帮助读者熟悉几种不同的数据结构，它们用于维护不断变化的具有键的对象集合。我们的基本目标是培养一种能力，也就是能够判断哪种数据结构比较适合自己的应用。选读的高级章节对如何从头实现这些数据结构提供了一些指导方针。

我们首先讨论堆，它可以快速识别它所存储对象中具有最小键值的对象，适用于排序、实现优先队列以及以线性时间实现Dijkstra算法。搜索树可以维护它所存储对象的整体键顺序，并支持更丰富的数组操作。散列表对超级快速的查找方式进行了优化，在现代程序中具有极其广泛的应用。我们还将讨论布隆过滤器，它是散列表的“近亲”。布隆过滤器的空间需求较散列表更低，但它偶尔会出现错误。

关于本书内容的更详细介绍，可以阅读每章的“本章要点”，它对每一章的内容，特别是那些重要的概念进行了总结。书中带星号的章节是难度较高的章节。时间较为紧张的读者在第一遍阅读时可以跳过这些章节，这并不会影响本书阅读的连续性。

分享本书第一章内容：

第1章　图的基础知识

本章将会简单地介绍图的概念、图的用途以及计算机程序中常见的图表示形式。接下来的两章将深入讨论一些著名的与图有关的实用算法。

1.1　基本术语

提到“图”这个词，我们很自然就会联想到x轴、y轴等术语（见图1.1(a)）。从算法的角度来说，图也可以看作成对的对象之间的关系的表现形式（见图1.1(b)）。

图1.1　在算法中，图是一组对象以及每对对象之间的关系（例如朋友关系）的表现形式

第二种类型的图具有两个组成部分：图所表示的对象集合以及每一对对象之间的关系。前者称为图的顶点或端点[1]。每一对对象之间的关系可以看成是图的边。我们通常用V和E分别表示图的顶点集和边集，有时用表达式G=(V,E)表示图G具有顶点集V和边集E。

图有两种风格，一种是有向图，另一种是无向图。这两种类型的图非常重要，具有极为普遍的应用，因此我们应该同时熟悉这两种图。在无向图中，每条边对应于一个无序的顶点对(v,w)，其中v和w是这条边的端点（图1.2(a)）。在无向图中，边(v,w)和边(w,v)没有区别。在有向图中，边(v,w)是个有序的顶点对，这条边的方向是从第1个顶点v（称为尾）到第2个顶点w（称为头），参见图1.2(b)。[2]

图1.2　具有4个顶点和5条边的图（无向图和有向图的边分别是无序的顶点对和有序的顶点对）

1.2　图的一些应用

图是一个基本概念，广泛存在于计算机科学、生物学、社会学和经济学等领域。下面是图的无数应用中的一些例子。

道路网。当手机的导航软件计算行驶路线时，它在一个表示道路网络的图中进行搜索，图中的顶点表示道路的交汇处，图中的每条边表示一条单独的道路。

万维网（World Wide Web）。万维网可以用有向图来建模，其中的顶点对应于单个的Web页面，边对应于超链接，边的方向是从包含超链接的页面到目标页面。

社交网络。社交网络也可以用图来表示，其中顶点对应于个人，边对应于某种类型的关系。例如，一条边可以表示它的两个顶点为朋友关系，或者表示其中一个顶点是另一个顶点的关注者。在当前流行的社交网络中，哪些建模为无向图更为自然？哪些建模为有向图更为自然？两者都有一些有趣的例子。

优先级约束。图对于那些缺少明显的网络结构的问题也是非常适用的。假设我们必须完成一组受到优先级约束的任务，例如把自己看成是大学一年级的新生，计划按照某种顺序学习几门课程。解决这种问题的一种方法是把本书2.5节描述的拓扑排序算法应用于下面这种图：每个顶点表示专业所要求的一门课程，从课程A到课程B的有向边表示学完课程A是学习课程B的先决条件。

1.3　图形的度量

与卷1一样，在本书中，我们用输入长度的一个函数来分析不同算法的运行时间。当输入是单个数组时（例如在排序算法中），就存在一种很明显的方式来定义“输入长度”，它就是数组的长度。当算法的输入涉及图时，就必须指定图的表现形式，并明确它的“长度”的含义。

1.3.1　图的边数量

图的度量是由两个参数所控制的，分别是顶点的数量和边的数量。下面是这两个量较常用的表示方法。

图的表示法

对于具有顶点集V和边集E的图G = (V, E) ：

1．n = |V|表示顶点的数量；

2．m = |E|表示边的数量。[3]

在小测验1.1中，我们思考无向图中边的数量与顶点数量的依赖关系。对于这个问题，我们假设每对顶点之间最多只有一条无向边，不允许出现“平行边”。我们还假设图是“连接的”，2.3节将正式定义这个概念。连接的图就是指图是“一整块的”，没有办法在不切断任何一条边的情况下把图分割为两个部分。图1.1(b)和图1.2(a)中的图是连接的，但图1.3中的图是非连接的。

图1.3　非连接的无向图

小测验1.1

考虑一个具有n个顶点并且没有平行边的无向图。假设这个图是连接的，也就是“一整块的”。这个图最少有几条边？最多有几条边？

（a）n−1和

（b）n−1和n2

（c）n和2n

（d）n和nn

（正确答案和详细解释参见1.3.3节）

1.3.2　稀疏图和稠密图

在小测验1.1中，我们已经看到了图的边数是如何因顶点的数量而异的。现在，我们可以讨论稀疏图和稠密图之间的区别。它们的区别是非常重要的，因为有些数据结构和算法更适用于稀疏图，而另一些则更适用于稠密图。

我们把小测验1.1的答案转换为渐进性表示法[4]。首先，如果一个具有n个顶点的无向图是连接的，那么边的数量m至少与n呈线性关系（也就是说，m=Ω (n)）。[5]其次，如果这个图没有平行边，那么m=O(n2)。[6]我们可以总结为：一个不存在平行边的连接无向图的边数是在顶点数的线性关系与平方关系之间。

通俗地说，如果边的数量接近于与顶点的数量呈线性关系，那么这个图就是稀疏图；如果边的数量接近于与顶点的数量呈平方关系，那么这个图就是稠密图。例如，具有n个顶点和O(n log n)条边的图一般被认为是稀疏图，而边的数量为Ω (n2/log n)的图一般被认为是稠密图。边的数量约等于n3/2的“部分稀疏”图既可以认为是稀疏图，又可以认为是稠密图，取决于具体的应用。

1.3.3　小测验1.1的答案

正确答案：（a）。在一个具有n个顶点并且没有平行边的连接无向图中，边的数量至少为n−1，最多为n(n−1)/2。为了理解这个下界为什么是正确的，可以以图G=(V,E)为例。作为一种思维试验，可以想象在创建G时一次创建一条边，从顶点集V和0条边开始。首先，在添加任何边之前，n个顶点中的每一个顶点都是完全隔离的，因此这个图可以看成n个不同的“片段”。添加一条边(v,w)的效果就是把包含v的片段与包含w的片段融合在一起（见图1.4）。因此，每添加一条边，最多会把片段的数量减少1。[7]为了从n个片段最终缩减为1个片段，至少需要添加n−1条边。有大量的连接图具有n个顶点并且只有n−1条边，这种图称为树（见图1.5）。

图1.4　添加一条新边把包含了顶点的两个片段融合为一个片段在这个例子中，不同片段的数量从3减少为2

图1.5　两个具有4个顶点和3条边的无向图

一个没有平行边的图的最大边数是由完全图实现的，它包含了每一条可能出现的边。

由于一个具有n个顶点的图共有

对顶点，因此它也是边的最大数量。例如，当n=4时，边的最大数量是

（见图1.6）。[8]

图1.6　具有4个顶点的完全图共有

条边

1.4　图的表示方法

我们可以采用不止一种方法对图进行编码，以便在算法中使用。

在本系列图书中，我们主要采用图的“邻接列表”表示形式（见1.4.1节），但读者同时也应该熟悉“邻接矩阵”表示形式（见1.4.2节）。

1.4.1　邻接列表

图的邻接列表表示形式是我们在本系列图书中采用的主要形式。

邻接列表的组成部分

1．一个包含了图的顶点集的数组。

2．一个包含了图的边集的数组。

3．对于每条边，有一个指针指向它的每个顶点。

4．对于每个顶点，有一个指针指向它的每条关联边。

邻接列表表示形式可以简化为两个数组（或者链表）：一个用于记录顶点，另一个用于记录边。这两个数组以一种自然的方式交叉引用对方，每条边都有相关联的指针指向它的每个顶点，每个顶点都有指针指向以它为顶点的边。

对于有向图，每条边记录哪个顶点是尾顶点，哪个顶点是头顶点。每个顶点v维护两个指针数组，一个表示外向边（v是尾顶点），另一个表示入射边（v是头顶点）。

邻接列表表示形式的内存需求是怎么样的呢？

小测验1.2

图的邻接列表表示形式需要多大的空间？（用顶点数量和边的数量的函数形式表示。）

（a）Θ (n)

（b）Θ (m)

（c）Θ (m+n)

（d）Θ (n2)

（正确答案和详细解释参见1.4.4节）

1.4.2　邻接矩阵

考虑一个无向图G=(V, E)，它具有n个顶点且没有平行边，并用1,2,3,…,n标识它的顶点。G的邻接矩阵表示形式是个正方形的n×n矩阵A，相当于一个二维数组，其元素是0或1。每个元素Aij被定义为：

如果边(i, j)属于E，则Aij =1；

否则，Aij =0。

因此，邻接矩阵用一个位表示每一对顶点，标记这对顶点之间是否存在边（见图1.7）。

图1.7　图的邻接矩阵为每一对顶点维护一个位，表示是否存在一条边连接这两个顶点

我们可以很方便地在图的邻接矩阵表示形式中添加一些“花样”，提示更多的信息。

• 平行边。如果在同一对顶点之间有多条边，那么Aij可以定义为顶点i和j之间的边数。
• 权重图。类似地，如果每条边(i, j)具有权重Wij，例如表示价格或距离，那么每个元素Aij可以存储Wij。
• 有向图。对于有向图G，邻接矩阵的每个元素被定义为：

如果边(i, j)属于E，那么Aij =1；

否则，Aij =0。

现在，“边(i, j)”表示从i到j的有向边。每个无向图的邻接矩阵都是对称的，但有向图的邻接矩阵通常是不对称的。

邻接矩阵的内存需求是怎么样的呢？

小测验1.3

图的邻接矩阵需要占据多大的内存空间呢？（用顶点数量n和边的数量m的函数形式表示。）

（a）Θ (n)

（b）Θ (m)

（c）Θ (m+n)

（d）Θ (n2)

（正确答案和详细解释参见1.4.4节。）

1.4.3　图的表示形式之间的比较

图有两种不同的表示形式也是一件令人烦恼的事情。我们不禁会问：哪种形式更好呢？答案和这类问题通常的答案一样——“取决于具体情况”。首先，它取决于图的密度，也就是边的数量与顶点的数量的相对数量比。小测验1.2和小测验1.3向我们提示邻接矩阵用于表示稠密图是非常高效的，但用来表示稀疏图是极为浪费的。其次，它取决于我们要支持的操作。综合考虑之下，对于本系列图书所描述的算法和应用，邻接列表是更为合理的表示形式。

大多数与图有关的算法涉及图的探索。邻接列表非常适合进行图的探索，当我们访问一个顶点时，邻接列表立即就能告诉我们接下来可以在哪几个步骤中进行选择。[9]邻接矩阵也有一些合适的应用，但本系列图书并不会讨论这些应用。[10]

当前对快速图元的兴趣大多来自于巨大的稀疏网络。例如，我们可以考虑Web图（见1.2节），其中顶点对应于Web页面，有向边对应于超链接。对这种类型的图的大小进行精确的测量是非常困难的，但还是在现代计算机的能力范围之内。保守地估计，顶点数量的下界大约是100亿（1010）。存储和读取如此长度的数组需要巨量的计算资源，不过现代计算机还是能够胜任。但是，这种图的邻接矩阵的大小规模达到了百万的三次方的100倍（1020）。对于当前的技术而言，存储和处理如此巨量的数据是力所不及的。但是，Web图是稀疏图，从一个顶点出发的边的平均数量小于100。因此，Web图的邻接列表的内存需求大约为1012（万亿级）。这个规模对于笔记本计算机来说可能过于庞大，但对于最前沿的数据处理系统而言，还是在它的能力范围之内的。[11]

1.4.4　小测验1.2和小测验1.3的答案

小测验1.2的答案

正确答案：（c）。邻接列表表示形式所需要的空间与图的大小（即顶点的数量加上边的数量）呈线性关系，是比较理想的。[12]要理解这一点略有难度，我们逐个观察它的4个组成部分。顶点数组和边数组的长度分别是n和m，分别需要Θ (n)和Θ (m)的空间。第3个组成部分将两个指针与每条边相关联（每个顶点与一个指针关联），这2m个指针产生了额外的Θ (m)的空间需求。

第4个组成部分可能会令我们感到困惑。无论怎样，总共n个顶点中的每一个顶点均可以参与到多达n−1条的边中，即可以与其他的每个顶点形成一条边，因此看上去会导致空间需求的上界为Θ (n2)。这种平方级的上界对于极为稠密的图而言是准确的，但对于稀疏图来说却显得过大了。关键在于：对于第4个组成部分中的每个“顶点→边”指针，在第3个组成部分中都存在一个对应的“边→顶点”指针。如果边e指向顶点v，那么边e就有一个指向这个顶点v的指针。反之，顶点v也有一个指向它的关联边e的指针。我们可以得出结论，即第3个组成部分和第4个组成部分中的指针具有一对一的对应关系，因此它们需要相同数量的空间，也就是Θ (m)。最终的空间需要：

　顶点数组　　　　　　　Θ (n)

　边数组　　　　　　　　Θ (m)

　从边到顶点的指针　　　Θ (m)

+ 从顶点到关联边的指针　Θ (m)

总共　　　　　　　　　Θ (m+n)

无论图是否为连接图，以及图是否具有平行边，这个Θ (m+n)的上界均适用。[13]

小测验1.3的答案

正确答案：（d）。邻接矩阵的一种简单存储方法是一个n×n的二维位数组，这需要Θ (n2)的空间，不过还有一个较小的隐藏常量因子。对于稠密图，边的数量接近于n的平方，邻接矩阵所需要的空间接近于与图的大小呈线性关系。但是，对于边的数量更接近于与n呈线性关系的稀疏图，邻接矩阵表示形式太浪费空间了。[14]

1.5　本章要点

• 图是对象之间逐对关系的一种表示形式，例如社交网络中的朋友关系、Web页面之间的超链接关系或任务之间的依赖关系。
• 图由一组顶点和一组边组成。在无向图中，边是没有方向的；在有向图中，边是有方向的。
• 如果图中边的数量m更接近于与顶点的数量n呈线性关系，那么这种图就是稀疏图。如果图中边的数量m更接近于与顶点的数量n呈平方关系，那么这种图就是稠密图。
• 图的邻接列表表示形式维护图的顶点数组和边数组，彼此之间以一种自然的方式实现交叉引用，它所需要的空间与顶点和边的总数量呈线性关系。
• 图的邻接矩阵表示形式为每一对顶点维护1个位，用于记录它们之间是否存在一条边。这种表示形式所需要的空间与顶点的数量呈平方关系。
• 邻接列表表示形式适用于稀疏图以及那些涉及图的探索的应用。

1.6　章末习题

问题1.1　假设G=(V, E)是个无向图。顶点v∈V的度数表示E中与顶点v相关联的边的数量（即以v为终点）。对于图G的下面每个条件，是否只有稠密图满足或者只有稀疏图满足？或者有些稠密图和有些稀疏图能满足？和往常一样，

表示顶点的数量。假设n很大（例如至少为10 000）。

（a）G至少有一个顶点的度数最多为10。

（b）G的每个顶点的度数最多为10。

（c）G至少有一个顶点的度数为n−1。

（d）G的每个顶点的度数为n−1。

习题1.2　考虑一个用邻接矩阵表示的无向图G=(V, E)。对于顶点v∈V，为了确定以v为顶点的边有哪些，需要多少个操作？（用k表示这种边的数量。和往常一样，n和m分别表示顶点和边的数量。）

（a）Θ (1)

（b）Θ (k)

（c）Θ (n)

（d）Θ (m)

习题1.3　考虑一个用邻接列表表示的有向图G=(V, E)，它的每个顶点存储了一个数组，包含了每一条从它所发射的边（但不包括入射到它的边）。对于顶点v∈V，为了确定v有哪些入射边，需要多少个操作？（用k表示这种边的数量。和往常一样，n和m分别表示顶点和边的数量。）

（a）Θ (1)

（b）Θ (k)

（c）Θ (n)

（d）Θ (m)

[1]　同一样东西具有两个名称并不是一件愉快的事情，但这两个术语都是广泛使用的，因此必须同时知道这两个名称。在本系列图书中，我们一般沿用“顶点”这个术语。

[2]　有向边有时称为弧，但我们不会在本系列图书中使用这个术语。

[3]　对于有限集合S，|S|表示S中元素的数量。

[4]　可以阅读《算法详解卷1》附录A，回顾一下大O、大Ω和大Θ表示法。

[5]　如果这个图并不需要是连接的，那么最少有0条边。

[6]　如果允许平行边，那么顶点数量不少于2的图的边数可以是任意大。

[7]　如果这条边的两个顶点已经在同一个片段中，那么片段的数量就不会减少。

[8]　

的意思是“在n个中选择2个”，又称“二项式系数”。为了理解为什么从一组n个对象中选择一对不同的无序对象的方法数量是

，可以考虑选择第1个对象（从n个选项中），然后选择第2个对象（从n −1个剩余选项中）。在总共n(n−1)个结果中，每对(x, y)对象都出现了2次（一次是首先选择x，然后选择y；另一次是首先选择y，然后选择x）。因此，不同的顶点对数就是

。

[9]　如果只能使用图的邻接矩阵表示形式，那么如何才能确定一个特定的顶点相关联的边是哪几条呢？

[10]　例如，我们可以通过探索图的邻接矩阵，立即算出每对顶点的公共邻居的数量。

[11]　例如，Google原创的用于评估网页重要性的网页排名算法的本质就依赖于Web图的高效搜索。

[12]　警告：由于邻接矩阵增加了一个维度，因此其主要约束条件更大。前导的常数因子要比邻接矩阵大一个数量级。

[13]　如果是连接图，那么m≥n−1（小测验1.1的结论），因此可以用Θ (m)代替Θ (m+n)。

[14]　对稀疏矩阵（即存在大量0的矩阵）使用一些存储和操作技巧，可以减少这种浪费。例如，MATLAB和Python的SciPy程序包均支持稀疏矩阵表示形式。