详情
算法详解系列图书共有4卷，本书是第2卷—图算法和数据结构。本书共有6章，主要介绍了3个主题，分别是图的搜索和应用、最短路径以及数据结构。附录简单回顾了渐进性表示法。本书的每一章均有小测验、章末习题，这为读者的自我检查以及进一步学习提供了方便。
本书提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维和计算思维的IT专业人士，以及正在准备面试的应聘者和面试官阅读参考。
书名：算法详解（卷2）——图算法和数据结构
ISBN：978-7-115-52603-8
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 [美] 蒂姆·拉夫加登（Tim Roughgarden）
译 徐 波
责任编辑 武晓燕
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
Simplified Chinese translation copyright ©2020 by Posts and Telecommunications Press.
ALL RIGHTS RESERVED.
Algorithms Illuminated Part 2: Graph Algorithms And Data Structures, by Tim Roughgarden, ISBN 9780999282922.
Copyright © 2018 by Tim Roughgarden.
本书中文简体版由Tim Roughgarden授权人民邮电出版社有限公司出版。未经出版者书面许可，对本书的任何部分不得以任何方式或任何手段复制和传播。
版权所有，侵权必究。
算法详解系列图书共有4卷，本书是第2卷—图算法和数据结构。本书共有6章，主要介绍了3个主题，分别是图的搜索和应用、最短路径以及数据结构。附录简单回顾了渐进性表示法。本书的每一章均有小测验、章末习题，这为读者的自我检查以及进一步学习提供了方便。
本书提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维和计算思维的IT专业人士，以及正在准备面试的应聘者和面试官阅读参考。
本书是在我的在线算法课程基础之上编写的，是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平台。另外，还有一些资源可以帮助读者根据自己的意愿提升对在线课程的体验。
如果没有过去几年里我的算法课程中数以千计的参与者的热情和渴望，“算法详解”系列图书就不可能面世。这些课程既包括斯坦福大学的课程，又包括在线平台的课程。我特别感谢那些为本书的早期草稿提供详细反馈的人：Tonya Blust、Yuan Cao、Jim Humelsine、Vladimir Kokshenev、Bayram Kuliyev、Patrick Monkelban和Daniel Zingaro。
我非常希望得到来自读者的建议和修正意见，读者可通过上面所提到的讨论组与我进行交流。
蒂姆·拉夫加登
英国伦敦，2018年7月
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，点击“提交勘误”，输入勘误信息，点击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（直接访问www.epubit.com/selfpublish/submission即可）。
如果您是学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
异步社区
微信服务号
本章将会简单地介绍图的概念、图的用途以及计算机程序中常见的图表示形式。接下来的两章将深入讨论一些著名的与图有关的实用算法。
提到“图”这个词，我们很自然就会联想到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条边的图（无向图的边和有向图的
边分别是无序的顶点对和有序的顶点对）
图是一个基本概念，广泛存在于计算机科学、生物学、社会学和经济学等领域。下面是图的无数应用中的一些例子。
道路网。当手机的导航软件计算行驶路线时，它在一个表示道路网络的图中进行搜索，图中的顶点表示道路的交汇处，图中的每条边表示一条单独的道路。
万维网（World Wide Web）。万维网可以用有向图来建模，其中的顶点对应于单个的Web页面，边对应于超链接，边的方向是从包含超链接的页面到目标页面。
社交网络。社交网络也可以用图来表示，其中顶点对应于个人，边对应于某种类型的关系。例如，一条边可以表示它的两个顶点为朋友关系，或者表示其中一个顶点是另一个顶点的关注者。在当前流行的社交网络中，哪些建模为无向图更为自然？哪些建模为有向图更为自然？两者都有一些有趣的例子。
优先级约束。图对于那些缺少明显的网络结构的问题也是非常适用的。假设我们必须完成一组受到优先级约束的任务，例如把自己看成大学一年级的新生，计划按照某种顺序学习几门课程。解决这种问题的一种方法是把本书2.5节描述的拓扑排序算法应用于下面这种图：每个顶点表示专业要求的一门课程，从课程A到课程B的有向边表示学完课程A是学习课程B的先决条件。
与卷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.1中，我们已经看到了图的边数是如何根据顶点的数量变化的。现在，我们可以讨论稀疏图和稠密图之间的区别。它们的区别是非常重要的，因为有些数据结构和算法更适用于稀疏图，而另一些则更适用于稠密图。
我们把小测验1.1的答案转换为渐进性表示法[4]。首先，如果一个具有n个顶点的无向图是连接的，那么边的数量m至少与n呈线性关系（也就是说，m=Ω (n)）。[5]其次，如果这个图没有平行边，那么m=O(n2)。[6]我们可以总结为：一个不存在平行边的连接无向图的边数是在顶点数的线性关系与平方关系之间。
通俗地说，如果边的数量大致与顶点的数量呈线性关系，那么这个图就是稀疏图；如果边的数量大致与顶点的数量呈平方关系，那么这个图就是稠密图。例如，具有n个顶点和O(n log n)条边的图一般被认为是稀疏图，而边的数量为Ω (n2/log n)的图一般被认为是稠密图。边的数量约等于n3/2的“部分稀疏”图既可以认为是稀疏图，又可以认为是稠密图，取决于具体的应用。
正确答案：（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节），但读者同时也应该熟悉“邻接矩阵”表示形式（见1.4.2节）。
图的邻接列表表示形式是我们在本系列图书中采用的主要形式。
邻接列表的组成部分
1．一个包含图的顶点集的数组。
2．一个包含图的边集的数组。
3．对于每条边，有一个指针指向它的每个顶点。
4．对于每个顶点，有一个指针指向它的每条关联边。
邻接列表表示形式可以简化为两个数组（或者链表）：一个用于记录顶点，另一个用于记录边。这两个数组以一种自然的方式交叉引用对方，每条边都有相关联的指针指向它的每个顶点，每个顶点都有指针指向以它为顶点的边。
对于有向图，每条边记录哪个顶点是尾顶点，哪个顶点是头顶点。每个顶点v维护两个指针数组，一个表示外向边（v是尾顶点），另一个表示入射边（v是头顶点）。
邻接列表表示形式的内存需求是怎么样的呢？
小测验1.2
图的邻接列表表示形式需要多大的空间？（用顶点数量和边的数量的函数形式表示。）
（a）Θ (n)
（b）Θ (m)
（c）Θ (m+n)
（d）Θ (n2)
（正确答案和详细解释参见1.4.4节。）
考虑一个无向图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 图的邻接矩阵为每一对顶点维护一位， 表示是否存在一条边连接这两个顶点
我们可以很方便地在图的邻接矩阵表示形式中添加一些“花样”，提示更多的信息。
如果边(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.2和小测验1.3向我们提示邻接矩阵用于表示稠密图是非常高效的，但用来表示稀疏图是极为浪费的。其次，它取决于我们要支持的操作。综合考虑之下，对于本系列图书所描述的算法和应用，邻接列表是更为合理的表示形式。
大多数与图有关的算法涉及图的探索。邻接列表非常适合进行图的探索，当我们访问一个顶点时，邻接列表立即就能告诉我们接下来可以在哪几个步骤中进行选择。[9]邻接矩阵也有一些合适的应用，但本系列图书并不会讨论这些应用。[10]
当前对快速图元的兴趣大多来自于巨大的稀疏网络。例如，我们可以考虑Web图（见1.2节），其中顶点对应于Web页面，有向边对应于超链接。对这种类型的图的大小进行精确的测量是非常困难的，但还是在现代计算机的能力范围之内。保守地估计，顶点数量的下界大约是100亿（1010）。存储和读取如此长度的数组需要巨量的计算资源，不过现代计算机还是能够胜任。但是，这种图的邻接矩阵的大小规模达到了百万的三次方的100倍（1020）。对于当前的技术而言，存储和处理如此巨量的数据是力所不及的。但是，Web图是稀疏图，从一个顶点出发的边的平均数量小于100。因此，Web图的邻接列表的内存需求大约为1012（万亿级）。这个规模对于笔记本计算机来说可能过于庞大，但对于最前沿的数据处理系统而言，还是在它的能力范围之内的。[11]
正确答案：（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]
正确答案：（d）。邻接矩阵的一种简单存储方法是一个n×n的二维位数组，这需要Θ (n2)的空间，不过还有一个较小的隐藏常量因子。对于稠密图，边的数量接近于n的平方，邻接矩阵所需要的空间大致与图的大小呈线性关系。但是，对于边的数量大致与n呈线性关系的稀疏图，邻接矩阵表示形式太浪费空间了。[14]
问题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程序包均支持稀疏矩阵表示形式。
