图——基础(一) | Thomas He’s Blog

type

status

date

slug

summary

1. 基本术语

从算法的角度来看，图是用来表示一组对象，以及这组对象两两之间的关系的。

因此，图有两个组成部分：对象，以及对象之间的关系。我们把对象称之为顶点（vertex），对象之间的关系称之为边（edge）。我们经常会用表示顶点的集合，表示边的集合，表达式的含义是：图拥有顶点集和边集。

图有两种，一种是有向图，一种是无向图。这两种图都很重要，它们的应用非常普遍；因此，有向图和无向图我们都必须掌握。在无向图中，每条边对应一对无序的顶点，其中顶点称为这条边的端点（endpoint）。在无向图中，边和边是没有区别的。在有向图中，每条边对应一对有序的顶点，这条边从顶点（尾端，tail）指向顶点（头端，head）。

2. 图的一些应用

图是一个很基础的概念，它广泛存在于计算机科学、生物学、社会学和经济学等领域。下面是无数应用中的一小撮…

交通道路网。顶点表示道路的交汇处，边表示道路。

万维网（The World Wide Web）。万维网可以用有向图来表示。顶点表示 Web 页面；边表示超链接，从包含超链接的 Web 页面指向链接的 Web 页面。

社交网络。社交网络也可以用图表示。其中顶点对应于个人，边对应于某种类型的关系。例如，一条边可以表示它的两个端点为朋友关系，或者表示其中一个端点是另一个端点的关注者。

优先级约束。图也可以用来表示优先级约束。例如，把自己想成大学一年级的新生，我们必须按某种顺序修完大学所有的课程。这个问题在算法中，叫做拓扑排序。我们可以把顶点看作是课程，边表示课程是课程的前提。

3. 图的大小

学习算法的时候，我们需要分析算法的时间复杂度。当算法涉及到图时，算法的时间复杂度往往和图的大小相关。这一小节，我们就来明确“图的大小”是什么含义。

图的大小由两个参数控制：顶点的数目和边的数目。

📌

对于具有顶点集和边集的图 : 1) 表示顶点的数目。 2) 表示边的数目。

边的数目和顶点的数目之间存在依赖关系。对于这个问题，我们假设每对顶点之间最多只有一条边，不允许出现“平行边”。我们还假设图是“连接的”（后面我们会正式定义这个概念）；连接的图就是指图是“一整块的”，没有办法在不切断任何一条边的情况下把图分割为两个部分。

⏰

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

3.1 稀疏图和稠密图

从上面的小测试可以发现，当顶点数目一定时，边的数目可以变换很大。现在，我们可以讨论稀疏图和稠密图之间的区别了。它们的区别非常重要，因为有些数据结构和算法更适用于稀疏图，而另一些则更适用于稠密图。

通俗地说，如果边的数目与顶点的数目大致呈线性关系，那么这个图就是稀疏图；如果边的数目与顶点的数目呈平方关系，那么这个图就是稠密图。例如，具有个顶点和条边的图一般被认为是稀疏图，而边的数目为的图一般被认为是稠密图。

4. 图的表示

图的表示有多种。在这一系列文章中，我们最常用的是邻接列表的方式；当然我们也会介绍邻接矩阵的方式。

4.1 邻接列表（Adjacency Lists）

邻接列表是我们最常用的表示方式，它一般应用于稀疏图中。

📌

邻接列表的组成部分 1. 包含顶点的数组。 2. 包含边的数组。 3. 每一条边，都有指向它两个端点的指针。 4. 每一个顶点，都有一个指针指向它每一条关联的边。

在 C++ 中，无向图的邻接列表表示方式，如下所示：

邻接列表的方式，最终可以简化成两个数组（也可以是链表，如果你喜欢的话）：一个包含所有的顶点，另一个包含所有的边。这两个数组以一种自然的方式交叉引用对方，每条边都有两个指针指向它的两个端点；每个顶点都有指针指向和它关联的边。

有向图的邻接列表表示方式，大同小异：

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

⏰

Quiz 图的邻接列表表示形式需要多大的内存空间？（其中，） a) b) c) d)

4.2 邻接矩阵（Adjacency Matrix）

考虑有个顶点，且没有平行边的无向图，并用对它的顶点编号。那么图的邻接矩阵表示形式就是一个正方形的矩阵（可以用二维数组表示），其元素是或。每个元素被定义为：

因此，邻接矩阵用一位表示每一对顶点，标记这对顶点之间是否存在一条边。

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

平行边。如果同一对顶点之间有多条边，那么可以定义为顶点和之间的边数。

权重图。类似地，如果每条边具有权重 —— 例如表示价格或距离，那么可以用来表示权重。

有向图。对于有向图，邻接矩阵的元素被定义为：

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

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

⏰

Quiz 图的邻接矩阵表示形式需要多大的内存空间？（其中，） a) b) c) d)

4.3 邻接列表 VS. 邻接矩阵

图有两种不同的表示形式也是一件令人烦恼的事情。我们不禁会问：哪种形式更好呢？答案通常是“取决于具体的情况”。

首先，它取决于图的密度。上面的两个小测试向我们提示了：邻接矩阵用于表示稠密图是非常高效的，但用来表示稀疏图却是极为浪费的。

其次，它取决于我们要进行的操作。大多数与图有关的算法都会涉及到图的搜索。邻接列表的方式非常适合图的搜索，当我们访问一个顶点时，邻接列表立即就能告诉我们接下来可以在哪几个选项中进行选择。

❓

在邻接矩阵中，如果才能知道与某个顶点相关联的边有哪些？

归纳总结

图是用来表示一组对象，以及这组对象两两之间关系的。例如社交网络中的朋友关系、Web页面之间的超链接关系或任务之间的依赖关系。

图由一组顶点和一组边组成。在无向图中，边是没有方向的；在有向图中，边是有方向的。

如果图中边的数目大致与顶点的数目呈线性关系，那么这种图就是稀疏图。如果图中边的数目大致与顶点的数目呈平方关系，那么这种图就是稠密图。

邻接列表维护着顶点数组和边数组，它们之间以一种自然的方式实现交叉引用，邻接列表所需要的空间与顶点和边的数目呈线性关系。

邻接矩阵为每一对顶点维护 1 个比特位，用于记录它们之间是否存在一条边。这种表示形式所需要的空间与顶点的数量呈平方关系。

邻接列表适用于稀疏图以及那些涉及图的搜索的应用。

参考文献

Algorithms Illuminated Part 2: Graph Algorithms and Data Structures

💡

欢迎您在底部评论区留言，我们一起交流学习~