数据结构（廿四） -- C语言版 -- 图 - 图的存储结构 -- 十字链表、邻接多重表、边集数组

短命女 2023-03-01 13:55 31阅读 0赞

### 内容预览 ###

*  零、读前说明
 *  一、十字链表
 *  二、邻接多重表
 *  三、边集数组
 *  四、简单总结

# 零、读前说明 #

*  本文为博主学习总结篇，参考的资源均来源于网络（主要参考《数据结构》、《大话数据结构》）。
 *  本人承诺所有图片均为本人亲手所绘，文中描述语言也经过仔细斟酌，如果有侵犯的地方，请及时告知！
 *  由于本人时间、水平、精力有限，文中难免会出现不准确、甚至错误的地方，很欢迎大佬批评指正。
 *   嘻嘻。。。。 。。。。。。。。收！

**这一篇为博主学习总结，从上一篇到本篇开始编写，中间经历回老家，回来工作还债等原因导致一直没有精力做其他事务。从开始编写本博文到最终完成，由于工作原因以及个人精力、学识的原因，中间更新过程也很缓慢，不过也算坚持做完了（虽然看的人很少，点赞的更少，粉丝更不用说的少，但是还是要坚持）。总之还是那几个字：累并快乐着！**

在图中任何两个顶点之间都可能存在联系，所以图的存储结构应该需要根据具体问题的要求来进行设计。从图的逻辑结构定义来看，图中任何一个顶点都可以看成是第一个顶点。常用的存储结构有**邻接矩阵**、**邻接表**（逆邻接表）、**十字链表**、**邻接多重表**、 **边集数组**。那么本博文将带你就 “**十字链表**、**邻接多重表**、 **边集数组**” 来窥探一二。。。

前面已经说明了 **邻接表**，优非常多，但是也有缺点。但是只要有明确的缺点，那么也就有了对应的解决方法了，对于邻接表中的缺点，其对应的缺点与优化的方式如下图所示。

![20200902140037684.png][]图1 邻接表关系示意图

# 一、十字链表 #

对于 **邻接表**，在处理 **有向图** 的时候，不能兼容顶点的 **出度** 和 **入度**，想要兼容入度，需要重新在建立一个 **逆邻接表**，那么有什么办法可以将邻接表和逆邻接表结合起来吗？

那么接下面就来就需要提到我们的 **十字链表**（ **Orthogonal List** ）了。

**十字链表** 是 **有向图** 的另外一种链式存储的结构，可以看成是将 **有向图的邻接表和逆邻接表结合起来** 的一种链表。**有向图** 中的 **每一条弧对应十字链表中的弧节点**，同时有向图中的每个顶点在十字链表中对应有一个节点，叫做 **顶点节点**。

根据前面的邻接表的结构，我们在需要兼容 **出度** 和 **入度** 的时候，就需要重新定义 **顶点表节点** 结构，定义如下图所示。  
    
![20200902100534505.png_pic_center][]

图1.1 邻接表顶点表节点结构示意图

其中，图中表示信息意义描述如下。

**data**            ：顶点的信息  
    **firstIn**   ：第一个入边表的指针，第一个入弧  
    **firstOut**：第一个出边表的指针，第一个出弧

同时再次重新定义 **边表节点** 的结构，定义如下图所示。  
    
![20200902100557209.png_pic_center][]

图1.2 邻接表边表节点结构示意图

其中，图中表示信息意义描述如下。

**tailVex**   ：表示弧起点（弧尾，没有箭头的端）的顶点的下标  
    **headVex**   ：表示弧终点（弧头，有箭头的端）的顶点的下标  
    **tailLink**：弧头相同的下一条弧  
    **headLink**：弧尾相同的下一条弧

所以在上面中，**tailVex** 和 **headVex** 构成的一条边，起点和终点分别是 **tailVex**、**headVex**（弧尾指向弧头）。

那么，现在我们可以轻松加愉快的画出一个 **有向图的邻接表**，以下图为例。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70][]图1.3 有向图邻接表示意图

同样地，我们也可以很轻松加愉快的画出一个 **有向图的逆邻接表**，以下图为例。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 1][]图1.4 有向图逆邻接表示意图

前面我们提到，十字链表可以直接简单的认为就是：**邻接表 + 逆邻接表 = 十字链表**。那么，对于上面提到的这个有向图，将其 **邻接表** 和 **逆邻接表** 叠加到一起，则可以得到其 **十字链表**。如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 2][]图1.5 有向图逆邻接表示意图

综上所述，对于十字链表，可完美的解决了关于邻接表或者逆邻接表的明显的缺点，主要为：

1、对于频繁的操作出度（只有出度则优先选择邻接表），同时频繁的操作入度（只有入度则选择逆邻接表）的情况。  
  2、对于频繁的操作一个顶点是否为另一个顶点连接点（优先选择邻接表），同时频繁的操作一个顶点是否为另一个顶点逆邻接点（优先选择逆邻接表）的情况。

# 二、邻接多重表 #

上面已经提到，对于无向图的邻接表中，每一条边都 **存储了两次**。那如果要对边进行删除或者插入的操作的话，那就需要操作两次。再者在插入或者删除边的过程中，还需要将邻接表中的链表进行插入或者删除的操作，并且都是操作两次。

那么，对于无向图的邻接表的 **边** 的操作中，同样的操作需要操作两次，耗时费力。所以相对于对有向图的优化的形式，接下面就来就需要提到我们的 **邻接多重表**（ **adjacent multiList** ）了。

所说，对于无向图也进行同样的优化，那么就需要对 **边表结构** 进行改进，重新定义的边表结构如下图所示。

![20200903095008775.png_pic_center][]

图2.1 无向图邻接多重表边表结构示意图

其中，图中表示信息意义描述如下。

**iVex**      ：此条边所依附的两个顶点中的其中一个在顶点表数组中的下标  
    **iLink**   ：指向依附于顶点 **iVex** 的下一条边  
    **jVex**      ：此条边所依附的两个顶点中的另外一个在顶点表数组中的下标  
    **jLink**   ：指向依附于顶点 **jVex** 的下一条边  
    **weight**：边的权值（或边的其他信息）

**顶点表节点** 还是采用和邻接表一致的形式。如下图所示。  
    
![20200903095037746.png_pic_center][]

图2.2 无向图邻接多重表顶点表节点示意图

其中，图中表示信息意义描述如下。

**Data**               ：顶点的信息  
    **firstEdge**：指向第一个依附于此顶点的边  
    **count**            ：顶点的个数，按需增加

邻接多重表是基于顶点的角度出发，查找与该顶点的有关系的边，我们清楚，两个点确定一条线，此线，即为该两个顶点的边了。那么下面用几张图片来说明邻接多重表。

如下图所示，首先从图中可以看出来，总共有 **5** 个顶点，分别是  V 0 V\_0 V0、 V 1 V\_1 V1、 V 2 V\_2 V2、 V 3 V\_3 V3、 V 4 V\_4 V4， **6** 条边，分别是  ( V 0 , V 1 ) (V\_0, V\_1) (V0,V1)、 ( V 1 , V 2 ) (V\_1, V\_2) (V1,V2)、 ( V 2 , V 3 ) (V\_2, V\_3) (V2,V3)、 ( V 3 , V 4 ) (V\_3, V\_4) (V3,V4)、 ( V 4 , V 0 ) (V\_4, V\_0) (V4,V0)、 ( V 0 , V 2 ) (V\_0, V\_2) (V0,V2)，因为表示的 **无向图**，所以 **iVex** 和 **jVex** **调换翻转过来是无所谓** 的，为了更直观的表示顶点和边的关系，采用相对应的方式进行表示，所以可以简单的表示为下图这样。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 3][]图2.3 无向图邻接多重表示意图

接下来，为了方便表示，以 **顶点为根据地，依次查找以此顶点为依附的边，然后再依次查找每个顶点。**

1、以顶点  V 0 V\_0 V0 为根据点，然后依次找到所有以顶点  V 0 V\_0 V0 为依附的边，总共有 **3** 条边，分别为  ( V 0 , V 1 ) (V\_0,V\_1) (V0,V1)、 ( V 0 , V 2 ) (V\_0,V\_2) (V0,V2)、 ( V 0 , V 4 ) (V\_0,V\_4) (V0,V4) ，然后依次连接起来，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 4][]图2.4 顶点v0的邻接多重表示意图

2、再以顶点  V 1 V\_1 V1 为根据点，然后依次找到所有以顶点  V 1 V\_1 V1 为依附的边，总共有 **2** 条边，分别为  ( V 1 , V 0 ) (V\_1,V\_0) (V1,V0)、 ( V 1 , V 2 ) (V\_1,V\_2) (V1,V2) ，在这里，边  ( V 1 , V 0 ) (V\_1,V\_0) (V1,V0)（等同于  ( V 0 , V 1 ) (V\_0,V\_1) (V0,V1)）已经在顶点  V 0 V\_0 V0 的时候处理了，所以直接连接，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 5][]图2.5 顶点v1的邻接多重表示意图

。。。。。。。。。。。。。。。。

3、再以顶点  V 4 V\_4 V4 为根据点，然后依次找到所有以顶点  V 4 V\_4 V4 为依附的边，总共有 **2** 条边，分别为  ( V 4 , V 0 ) (V\_4,V\_0) (V4,V0)、 ( V 4 , V 3 ) (V\_4,V\_3) (V4,V3)，在这里，边  ( V 4 , V 0 ) (V\_4,V\_0) (V4,V0) 和  ( V 4 , V 3 ) (V\_4,V\_3) (V4,V3) 都已经在顶点  V 0 V\_0 V0 和  V 3 V\_3 V3 的时候处理过了，所以直接连接，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 6][]图2.6 无向图邻接多重表示意图

综上所述，对于邻接多重表，可完美的解决了关于邻接表或者逆邻接表的明显的缺点，主要为：

1、对于频繁的操作顶点的度的情况。  
  2、对于频繁的操作边的情况。

# 三、边集数组 #

边集数组（**edgeset array**） 是利用 **一维数组** 来存储图中所有边的表示方法。一般情况下由两个一维数组组成。它适用于一些以 **边为主** 的操作。

其中一个数组存储顶点的信息，基本上包括 **data**，**count** 等信息。如下图表示。  
    
![20200903141604231.png_pic_center][]

图3.1 边集数组顶点结构示意图

另一个数组存储边的信息，此数组基本上包括边的 **起始顶点在顶点数组中的下标**（**begin**），**终点在顶点数组中的点的下标**（**end**），**边的权值**（**weight** 如果存在）。可以用一个结构体来表示边，数组中存储此结构体。其结构如下图所示。  
    
![20200903141621231.png_pic_center][]

图3.2 边集数组边结构示意图

当然，这里存储边的信息也可以使用三个独立的一维数组，分别用来存储 **起点下标**、**终点下标**，**权值** 等信息。但是需要做好彼此的对应的关系接口。

下面有一张图简单的表示有向图的边集数组表示形式。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 7][]图3.3 有向图边集数组示意图

然后关于无向图，在用边集数组表示的过程中， 需要将每一条边都存储两次，因为对于无向图，每一条边的任何一端均可以起始端，也可以是终止端。并且在图开始的部分已经提出过，**将一个无向图可以转换为一个有向图，只需要将无向图的每一条边用有向图中两条相反方向的边表示**。所以无向图的边集数组如下图表示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 8][]图3.4 无向图边集数组示意图

综上所述，边集数组在进行无向图的操作中，同样需要将边操作两次。

# 四、简单总结 #

至此，我们已经介绍完了五中常用的图的存储结构了，分别为：**邻接矩阵**、**邻接表**（**逆邻接表**）、**十字链表**、**邻接多重表**、 **边集数组**。各种存储方式均有比较显著的特点，有点，同样也有明显的缺点。那么在实际使用中，我们 **需要按照相对应的需求选择合适的存储结构**，选择对了往往能达到事半功倍的效果。那么应该如何选择，各种存储结构究竟有什么样的优点、缺点、针对什么样的使用场景，我们就用下表来为你说明。

表4.1 对比表

<table> 
 <thead> 
 <tr> 
 <th align="center">结构</th> 
 <th align="left">优点</th> 
 <th align="left">缺点</th> 
 <th align="left">适用情况</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">邻接矩阵</td> 
 <td align="left">1、通用性强 2、方便计算任意顶点的度（有向图中出度、入度） 3、容易判断任意两个顶点之间是否存在边 4、方便计算任意顶点的所有“邻接点”</td> 
 <td align="left">1、占用空间大 2、对于稀疏图，空间利用率低 3、对于有向图，空间利用率低</td> 
 <td align="left">1、稠密图 2、无向图</td> 
 </tr> 
 <tr> 
 <td align="center">邻 接 表</td> 
 <td align="left">1、方便查找任意顶点的所有“邻接点” 2、对于稀疏图，节约空间 3、对于无向图，方便计算任意顶点的度 4、对于有向图，方便计算任意顶点的“出度”</td> 
 <td align="left">1、不易判断任意两个顶点之间是否存在边 2、需要 N N N个头指针 + 2 E +2E +2E 个节点 3、对于无向图，每条边都存储两次 4、对于有向图，不易计算顶点的“入度” 5、不具有唯一（边表的顺序是任意的）</td> 
 <td align="left">1、稀疏图 2、有向图（不要求出度或者入度）</td> 
 </tr> 
 <tr> 
 <td align="center">十字链表</td> 
 <td align="left">1、改进有向图的邻接表中不能兼顾“出度”和“入度”的缺点 2、高效的存取</td> 
 <td align="left">1、不易判断任意两个顶点之间是否存在边 2、需要 N N N个头指针 + 2 E +2E +2E 个节点 3、结构复杂</td> 
 <td align="left">1、稀疏图 2、有向图，顶点操作频繁</td> 
 </tr> 
 <tr> 
 <td align="center">邻接多重表</td> 
 <td align="left">1、改进无向图的邻接表中边操作重复的缺点 </td> 
 <td align="left">1、不易判断任意两个顶点之间是否存在边 2、需要 N N N个头指针 + 2 E +2E +2E 个节点</td> 
 <td align="left">1、稀疏图 2、无向图，对边操作频繁</td> 
 </tr> 
 <tr> 
 <td align="center">边集数组</td> 
 <td align="left">1、结构简单（一维数组） 2、对于有向图的操作简单、方便</td> 
 <td align="left">对于无向图，每条边都存储两次</td> 
 <td align="left">1、稀疏图 2、对边依次进行处理的场合</td> 
 </tr> 
 </tbody> 
</table>

好啦，废话不多说，总结写作不易，如果你喜欢这篇文章或者对你有用，请动动你发财的小手手帮忙**点个赞**，当然**关注一波**那就更好了，就到这儿了，么么哒(\* ￣3)(ε￣ \*)。

![202008020056342.png][] ![20200903212041471.gif][]

上一篇：[数据结构（廿三） – C语言版 – 图 - 图的存储结构 – 邻接表、逆邻接表][_ C_ _ _ - _ _]  
下一篇：[数据结构（廿五） – C语言版 – 图 - 图的遍历 – 邻接矩阵 - 深度/广度优先遍历/搜索（DFS、BFS）][_ C_ _ _ - _ _ _ - _DFS_BFS]

[20200902140037684.png]: /images/20230208/07b70bdcbe1b4f8589e1307430aa4e60.png
[20200902100534505.png_pic_center]: https://img-blog.csdnimg.cn/20200902100534505.png#pic_center
[20200902100557209.png_pic_center]: https://img-blog.csdnimg.cn/20200902100557209.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200902112130488.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200902112257876.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200902112405376.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[20200903095008775.png_pic_center]: https://img-blog.csdnimg.cn/20200903095008775.png#pic_center
[20200903095037746.png_pic_center]: https://img-blog.csdnimg.cn/20200903095037746.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200903095219431.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200903101154759.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200903095426465.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200903095623824.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[20200903141604231.png_pic_center]: https://img-blog.csdnimg.cn/20200903141604231.png#pic_center
[20200903141621231.png_pic_center]: https://img-blog.csdnimg.cn/20200903141621231.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200903141716564.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200903141819409.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[202008020056342.png]: https://img-blog.csdnimg.cn/202008020056342.png
[20200903212041471.gif]: https://img-blog.csdnimg.cn/20200903212041471.gif
[_ C_ _ _ - _ _]: https://blog.csdn.net/zhemingbuhao/article/details/107555871
[_ C_ _ _ - _ _ _ - _DFS_BFS]: https://blog.csdn.net/zhemingbuhao/article/details/108393792