数据结构与算法——图论基础与图存储结构

左手的ㄟ右手 2022-02-28 11:40 257阅读 0赞

![640?wx\_fmt=png][640_wx_fmt_png]

## 1 前言 ##

由于后续更新「面试专场」的好几篇文章都涉及到 图 这种数据结构，因此打算先普及一下 图 的相关理论支持，如果后面的相关内容有些点不太容易理解，可以查阅此篇文章。本文不建议一口气阅读完毕，可以先浏览一遍，在后续有需要的时候进行查阅即可。

## 2 图 ##

**图**是数据结构中重要内容。相比于线性表与树，图的结构更为复杂。在线性表的存储结构中，数据直接按照前驱后继的线性组织形式排列。在树的结构中，数据节点以层的方式排列，节点与节点之间是一种层次关系。但是，在图的结构中数据之间可以有任意关系，这就使得图的数据结构相对复杂。

### 2.1 定义 ###

**定义：**图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。

例如：图 2.1 所示图

![640?wx\_fmt=png][640_wx_fmt_png 1] 图2.1

在图 2.1 中，共有 V0，V1，V2，V3 这 4 个顶点，4 个顶点之间共有 5 条边。

注：

> 当线性表没有数据节点时，线性表为空表。  
> 树中没有节点时，树为空树。  
> 但是，在图中不允许没有顶点，但是可以没有边。

### 2.2 无向边 ###

**无向边：**若顶点 x 和 y 之间的边没有方向，则称该边为无向边(x,y)，(x,y) 与 (y,x) 意义相同，表示 x 和 y 之间有连接。  
  图 2.2 所示图中的边均为无向边。

![640?wx\_fmt=png][640_wx_fmt_png 2] 图2.2

### 2.3 有向边 ###

**有向边：**若顶点 x 和 y 之间的边有方向，则称该边为有向边，与表示的意义是不同的，表示从 x 连接到 y ，x 称为尾，y 称为头。表示从 y 连接到 x ，y 称为尾， x 称为头。  
  图2.3所示图中的边为有向边。

![640?wx\_fmt=png][640_wx_fmt_png 3] 图2.3

### 2.4 无向图 ###

**无向图：**若图中任意两个顶点之间的边均是无向边，则称该图为无向图。  
图2.2所示图为无向图。

## 2.5 有向图 ##

**有向图：**若图中任意两个顶点之间的边均是有向边，则称该图为有向图。  
图2.3所示的图为有向图。

## 2.6 顶点与顶点的度 ##

![640?wx\_fmt=png][640_wx_fmt_png 4] 图2.6

顶点的度：

顶点 V 的度是和 V 相关联的边的数目，记为TD(V)。

图 2.6 所示图中，V0 顶点的度为 3 。

入度：

以顶点v为头的边的数目，记为ID(V)。

图2.6所示图中，V0的入度为1。

出度：

以顶点 v 为尾的边的数目，记为 OD(V)。

图2.6所示图中，V0的出度为2。

**顶点的度 = 入度 + 出度**。

即 TD(V) = ID(V) + OD(V)。

### 2.7 邻接 ###

**邻接**是两个顶点之间的一种关系。如果图包含（u,v），则称顶点 v 与顶点 u 邻接。在无向图中，这也暗示了顶点 u 也与顶点 v 邻接。换句话说，在无向图中邻接关系是对称的。

## 2.8 路径 ##

**路径：**在图中，依次遍历顶点序列之间的边所形成的轨迹。  
  例如：在图 2.8 中所示图中依次访问顶点 V0 、V3 和 V2 ，则构成一条路径。

![640?wx\_fmt=png][640_wx_fmt_png 5] 图 2.8

## 3 完全图 ##

**完全图：**每个顶点都与其他顶点相邻接的图。

**无向完全图：**在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。（含有n个顶点的无向完全图有(n×(n-1))/2条边）  
图 3.1 所示的图为无向完全图。

![640?wx\_fmt=png][640_wx_fmt_png 6] 图3.1

**有向完全图：**在有向图中，如果任意两个顶点之间都存在方向互为相反的两条边，则称该图为有向完全图。（含有 n 个顶点的有向完全图有 n×(n-1) 条边）

图3.2所示的图为有向完全图。

![640?wx\_fmt=png][640_wx_fmt_png 7] 图3.2

## 4 连通图 ##

在无向图 G 中，如果从顶点 v 到顶点 v' 有路径，则称 v 和 v' 是连通的。 如果对于图中任意两个顶点 vi 、vj ∈E， vi，和vj都是连通的，则称 G 是**连通图**，否则图为**非连通图**。  
  例如：图4.1所示图，图中顶点A、B、C、D是连通的，但是其中任一顶点与顶点E或者顶点F之间没有路径，因此图4.1中所示的图为非连通图。

![640?wx\_fmt=png][640_wx_fmt_png 8] 图4.1

若添加顶点B与顶点F之间的邻接边，则图变为连通图，如图4.2所示：

![640?wx\_fmt=png][640_wx_fmt_png 9] 图4.2

## 5 数组存储 ##

**图的数组存储**方式也称为**邻接矩阵存储**。图中的数据信息包括：顶点信息和描述顶点之间关系的边的信息，将这两种信息存储在数组中即为图的数组存储。  
  首先，创建顶点数组，顶点数组中存储的是图的顶点信息，采用一维数组的方式即可存储所有的顶点信息。存储图中边的信息时，由于边是描述顶点与顶点之间关系的信息，因此需要采用二维数组进行存储。

**定义：**设图 G 有 n 个顶点，则邻接矩阵是一个n X n的方阵A，定义为：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg] 图 5  
其中，或者(Vi , Vj,)表示顶点 Vi 与顶点 Vj 邻接。wi,j表示边的权重值。

例如：下图所示的无向图，采用数组存储形式如下。

![640?wx\_fmt=png][640_wx_fmt_png 10] 图5.1

注：图中的数组存储方式简化了边的权值为 1 。

**无向图的数组存储主要有以下特性：**

> （1）顶点数组长度为图的顶点数目n。边数组为n X n的二维数组。  
> （2）边数组中，A\[i\]\[j\] =1代表顶点i与顶点j邻接，A\[i\]\[j\] = 0代表顶点i与顶点j不邻接。  
> （3）在无向图中。由于边是无向边，因此顶点的邻接关系是对称的，边数组为对称二维数组。  
> （4）顶点与自身之间并未邻接关系，因此边数组的对角线上的元素均为0。  
> （5）顶点的度即为顶点所在的行或者列1的数目。例如：顶点V2的度为3，则V2所在行和列中的1的数目为3。

当图为有向图时，图的数组存储方式要发生变化。  
例如：图5.2所示的有向图，采用数组存储形式如下。

![640?wx\_fmt=png][640_wx_fmt_png 11] 图5.2

**有向图的数组存储主要有以下特性：**

> （1）顶点数组长度为图的顶点数目n。边数组为n X n的二维数组。  
> （2）边数组中，数组元素为1，即A\[i\]\[j\] = 1,代表第i个顶点与第j个顶点邻接，且i为尾，j为头。 A\[i\]\[j\] = 0代表顶点与顶点不邻接。  
> （3）在有向图中，由于边存在方向性，因此数组不一定为对称数组。  
> （4）对角线上元素为0。  
> （5）第i行中，1的数目代表第i个顶点的出度。例如：顶点V1的出度为2，则顶点V1所在行的1的数目为2。  
> （6）第j列中，1的数目代表第j个顶点的入度。例如：V3的入度为1，则V3所在列中1的数目为1。

**数组存储方式优点：**  
  数组存储方式容易实现图的操作。例如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。  
**数组存储方式缺点：**  
  采用数组存储方式，图若有n个顶点则需要n2个单元存储边(弧)，空间存储效率为O(n2)。 当顶点数目较多，边数目较少时，此时图为稀疏图，这时尤其浪费空间。  
  例如：图5.3所示的图，图中有 9 个顶点，边数为10，需要 9X9 的二维数组，而实际存储边信息空间只有10，造成空间浪费。

![640?wx\_fmt=png][640_wx_fmt_png 12] 图5.3

图5.3所示无向图的存储数组：

![640?wx\_fmt=png][640_wx_fmt_png 13]

## 6 邻接表 ##

当使用数组存储时，主要有以下三个问题：

> （1）对于一个图，若图中的顶点数目过大，则无法使用邻接矩阵进行存储。因为在分配数组内存时可能会导致内存分配失败。  
> （2）对于某些稀疏图（即顶点数目多，边数目少），创建的数组大小很大，而真正存储的有用信息又很少，这就造成了空间上的浪费。  
> （3）有时两个点之间不止存在有一条边，这是用邻接矩阵就无法同时表示两条以上的边。

针对以上情况，提出了一种特殊的图存储方式，让每个节点拥有的数组大小刚好就等于它所连接的边数，由此建立一种邻接表的存储方式。

**邻接表存储**方法是一种数组存储和链式存储相结合的存储方法。在邻接表中，对图中的每个顶点建立一个单链表，第 i 个单链表中的结点依附于顶点 Vi 的边（对有向图是以顶点Vi为尾的弧）。链表中的节点称为表节点，共有 3个域，具体结构见下图：

![640?wx\_fmt=png][640_wx_fmt_png 14] 图 6  
**表结点**由三个域组成，adjvex存储与Vi邻接的点在图中的位置，nextarc存储下一条边或弧的结点，data存储与边或弧相关的信息如权值。

除表节点外，需要在数组中存储**头节点**，**头结点**由两个域组成，分别指向链表中第一个顶点和存储Vi的名或其他信息。具体结构如下图：

![640?wx\_fmt=png][640_wx_fmt_png 15] 图 6.0

其中，data域中存储顶点相关信息，firstarc指向链表的第一个节点。  
**无向图采用邻接表方式存储**  
例如：图6.1所示的无向图采用邻接表存储。

![640?wx\_fmt=png][640_wx_fmt_png 16] 图6.1 无向图

采用邻接表方式存储图 6.1 中的无向图，绘图过程中忽略边节点的info信息，头结点中的 data 域存储顶点名称。以V1顶点为例，V1顶点的邻接顶点为V2、V3、V4，则可以创建3个表节点，表节点中adjvex分别存储V2、V3、V4的索引1、2、3，按照此方式，得到的邻接表为：

![640?wx\_fmt=png][640_wx_fmt_png 17] 图 6.2

**无向图的邻接表存储特性：**

> （1）数组中头节点的数目为图的顶点数目。  
> （2）链表的长度即为顶点的度。例如：V1顶点的度为3，则以V1为头节点的链表中表节点的数目为3。

**有向图采用邻接表方式存储**  
例如：图 6.3 所示的有向图采用邻接表存储。

![640?wx\_fmt=png][640_wx_fmt_png 18] 图 6.3

采用邻接表方式存储图6.3中的有向图，绘图过程中忽略边节点的info信息，头结点中的data域存储顶点名称。以V1顶点为例，V1顶点的邻接顶点为V2、V3、V4，但是以V1顶点为尾的边只有两条，即和因此，创建2个表节点。表节点中adjvex分别存储V3、V4的索引2、3，按照此方式，得到的邻接表为：

![640?wx\_fmt=png][640_wx_fmt_png 19] 图 6.4  
**有向图的邻接表存储特性：**

> （1）数组中表节点的数目为图的顶点数目。  
> （2）链表的长度即为顶点的出度。例如V1的出度为2，V1为头节点的链表中，表节点的数目为2。  
> （3）顶点Vi的入度为邻接表中所有adjvex值域为i的表结点数目。例如：顶点V3的入度为4，则链表中所有adjvex值域为2的表结点数目为4。

**注：图采用邻接表的方式表示时，其表示方式是不唯一的。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。**

## 7 逆邻接表 ##

在邻接表中，可以轻易的得出顶点的出度，但是想要得到顶点的入度，则需要遍历整个链表。为了便于确定顶点的入度，可以建立有向图的逆邻接表。逆邻接表的建立与邻接表相反。  
  **采用逆邻接表的方式存储图3.2所示的无向图。以V3顶点为例，V3顶点的邻接顶点为V1、V2、V4、V5，以V3顶点为头的边有4条，即、、、因此，创建4个表节点。表节点中adjvex分别存储V0、V1、V3、V4的索引0、1、3、4，按照此方式，得到的逆邻接表为：**

![640?wx\_fmt=png][640_wx_fmt_png 20] 图 7

## 8 十字链表 ##

对于有向图而言，邻接链表的缺陷是要查询某个顶点的入度时需要遍历整个链表，而逆邻接链表在查询某个顶点的出度时要遍历整个链表。为了解决这些问题，十字链表将邻接链表和逆邻接链表综合了起来，而得到的一种十字链表。在十字链表中，每一条边对应一种边节点，每一个顶点对应为顶点节点。

**顶点节点**  
顶点节点即为头节点，由3个域构成，具体形式如下：

![640?wx\_fmt=png][640_wx_fmt_png 21] 图 8  
其中，data域存储与顶点相关的信息，firstin和firstout分别指向以此顶点为头或尾的第一个边节点。  
**边节点**  
在边节点为链表节点，共有 5 个域，具体形式如下：  
![640?wx\_fmt=png][640_wx_fmt_png 22] img  
其中，尾域tailvex和头域headvex分别指向尾和头的顶点在图中的位置。链域hlink指向头相同的下一条边，链域tlink指向尾相同的下一条边。info 存储此条边的相关信息。  
例如：图8.1所示的有向图，采用十字链表存储图方式。  
![640?wx\_fmt=png][640_wx_fmt_png 23] 图8.1 有向图

采用十字链表的方式存储图8.1中的有向图，绘图过程忽略边节点中的info信息，表头节点中的data域存储顶点名称。以V1顶点为例，顶点节点的data域存储V1顶点名，firstin存储以V1顶点为头第一个边节点，以V1顶点为头边为，firstout存储以以V1顶点为尾第一个边节点，对应边为。按照此规则，得到的十字链表存储为：

![640?wx\_fmt=png][640_wx_fmt_png 24] img  
**注：采用十字链表存储时，表头节点仍然使用数组存储，采用下标索引方式获取。**

## 9 邻接多重表 ##

对于无向图而言，其每条边在邻接链表中都需要两个结点来表示，而邻接多重表正是对其进行优化，让同一条边只用一个结点表示即可。邻接多重表仿照了十字链表的思想，对邻接链表的边表结点进行了改进。

重新定义的边结点结构如下图：

![640?wx\_fmt=png][640_wx_fmt_png 25] img  
其中，ivex和jvex是指某条边依附的两个顶点在顶点表中的下标。 ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。info存储边的相关信息。

重新定义的顶点结构如下图：

![640?wx\_fmt=png][640_wx_fmt_png 26] 图 9  
其中，data存储顶点的相关信息，firstedge指向第一条依附于该顶点的边。  
例如：图9.1所示的无向图，采用邻接多重表存储图。  
![640?wx\_fmt=png][640_wx_fmt_png 27] 图9.1 无向图

图 9.1 所示的无向图，采用邻接多重表存储，以 V0 为例，顶点节点的data域存储V0名称，firstedge 指向(V0 , V1)边，边节点中的ilink指向依附V0顶点的下一条边(V0 , V3)，jlink指向依附V1顶点的下一条边(V1 , V2)，按照此方式建立邻接多重表：

![640?wx\_fmt=png][640_wx_fmt_png 28]

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 1]

[昨天，终于拿到了腾讯 offer][offer]

[几道和「二叉树」有关的算法面试题][Link 2]

[几道和散列（哈希）表有关的面试题][Link 3]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 4]

[几道和「堆栈、队列」有关的面试算法题][Link 5]

[链表算法面试问题？看我就够了！][Link 6]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

欢迎关注![640?wx\_fmt=png][640_wx_fmt_png 29]

[640_wx_fmt_png]: /images/20220228/7851c9f818c74f45aeff48e761251cd4.png
[640_wx_fmt_png 1]: /images/20220228/ba7d2249c6e04136a662f936b282f5e9.png
[640_wx_fmt_png 2]: /images/20220228/ed2a64a6524a476693ce2cc9c89b1939.png
[640_wx_fmt_png 3]: /images/20220228/8ec2ebce711d4cb68406d3b72ab5aa1f.png
[640_wx_fmt_png 4]: /images/20220228/4e38c4b3ad5a457b9708b94b589b0c49.png
[640_wx_fmt_png 5]: /images/20220228/fc8a43fc54844d4ba16dc179cd45f412.png
[640_wx_fmt_png 6]: /images/20220228/f5f6e65f87a34dcfbe65b21c1036dfae.png
[640_wx_fmt_png 7]: /images/20220228/61e357e29e8c4e7695d59f63535de5c7.png
[640_wx_fmt_png 8]: /images/20220228/bed8e98178d74fb592430c93b083dbba.png
[640_wx_fmt_png 9]: /images/20220228/a1d198e15ef44ac0bfed967a1992c0e0.png
[640_wx_fmt_jpeg]: /images/20220228/b9e289aaeeba49f49767200ddd9c386c.png
[640_wx_fmt_png 10]: /images/20220228/ae50c75b254146bb915df3f454aa58fb.png
[640_wx_fmt_png 11]: /images/20220228/9d72805fafa54f19824fddb575e8cf75.png
[640_wx_fmt_png 12]: /images/20220228/0f7d617b5a214470b3805c2497532300.png
[640_wx_fmt_png 13]: /images/20220228/0000640b05c342f49bac9277ff616100.png
[640_wx_fmt_png 14]: /images/20220228/4b1b1697941b4292a747860ffc7f58b1.png
[640_wx_fmt_png 15]: /images/20220228/934adc27148647c781c7d696477469ac.png
[640_wx_fmt_png 16]: /images/20220228/913712820b754e2b9d443657c5146b76.png
[640_wx_fmt_png 17]: /images/20220228/b6dcfc5e07f54e5d9d8989fe8105afda.png
[640_wx_fmt_png 18]: /images/20220228/a39c605559dc4a8da866be83370cee69.png
[640_wx_fmt_png 19]: /images/20220228/2be6ddb517034e5ea3fe5aae1c875df8.png
[640_wx_fmt_png 20]: /images/20220228/ef893a8f20f44d42925f793f96e5a114.png
[640_wx_fmt_png 21]: /images/20220228/f2514ee995054cd88bedb79ca8543400.png
[640_wx_fmt_png 22]: /images/20220228/cfc1ed691abf4da2b7e9e2c69d75dd86.png
[640_wx_fmt_png 23]: /images/20220228/2401ca01a4d14c95974f385ed10a2441.png
[640_wx_fmt_png 24]: /images/20220228/fabf899bdd2640ab9085110ba449aa6b.png
[640_wx_fmt_png 25]: /images/20220228/89d100a424ae415d9995bce407537289.png
[640_wx_fmt_png 26]: /images/20220228/602081682d974d94b144a67eca7949f9.png
[640_wx_fmt_png 27]: /images/20220228/7c6fe1d3bd9c46f395bf7dd70fd414a1.png
[640_wx_fmt_png 28]: /images/20220228/d7e560a5018a4daeb7634269a29332a9.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 1]: /images/20220228/01757cf802244611b21462d4df6991d6.png
[640_wx_fmt_png 29]: /images/20220228/f0803add6f25495da9efcf7137c2b5c0.png