【数据结构与算法】图的存储

不念不忘少年蓝@ 2024-04-26 02:27 78阅读 0赞

> ? 本文由 [程序喵正在路上][Link 1] 原创，CSDN首发！  
> ? 系列专栏：[数据结构与算法][Link 2]  
> ? 首发时间：2022年11月13日  
> ? 欢迎关注?点赞?收藏?留言?  
> ? 一以贯之的努力 不得懈怠的人生

#### 阅读指南 ####

*  邻接矩阵法（顺序存储）
 *   *  邻接矩阵法存储带权图（网）
     *  邻接矩阵法的性能分析
     *  邻接矩阵法的性质
 *  邻接表法（顺序+链式存储）
 *   *  空间复杂度分析
     *  度、入度和出度
     *  邻接矩阵和邻接表的对比
 *  十字链表
 *  邻接多重表
 *  总结

## 邻接矩阵法（顺序存储） ##

图中点和点之间是否有连接，我们可以用一个表来表示，其中 “1” 表示两点之间有边，反之

![在这里插入图片描述][1348bd38bc3c4e1bbf224574da053d30.png]

上图很容易用代码表示出来

#define MaxVertexNum 100						//顶点数目的最大值
    typedef struct{
        
    	char Vex[MaxVertexNum];						//顶点表
    	int Edge[MaxVertexNum][MaxVertexNum];		//邻接矩阵，边表
    	int vexnum, arcnum;							//图的当前顶点数和边数/弧数
    } MGraph;

顶点的数组中我们可以存储更复杂的信息，比如一个结构体

结点数为  n n n 的图  G = ( V , E ) G = (V, E) G=(V,E) 的邻接矩阵  A A A 是  n × n n \\times n n×n 的，将  G G G 的顶点编号为  v 1 , v 2 , … , v n v\_1, v\_2, \\dots, v\_n v1,v2,…,vn， 则

KaTeX parse error: No such environment: align\* at position 8: \\begin\{̲a̲l̲i̲g̲n̲\*̲\}̲ \\begin\{split\} …

在这种情况下，我们怎么求顶点的度、入度和出度呢？

*  对于无向图，第  i i i 个结点的度  = = = 第  i i i 行（或第  i i i 列）的非零元素个数
 *  对于有向图，第  i i i 个结点的出度  = = = 第  i i i 行的非零元素个数，第  i i i 个结点的入度  = = = 第  i i i 列的非零元素个数，，第  i i i 个结点的度  = = = 第  i i i 行、第  i i i 列的非零元素个数之和

邻接矩阵法求顶点的度 / 出度 / 入度的时间复杂度均为  O ( ∣ V ∣ ) O(|V|) O(∣V∣)

### 邻接矩阵法存储带权图（网） ###

#define MaxVertexNum 100						//顶点数目的最大值
    #define INFINITY 最大的int值						//宏定义常量 “无穷”
    typedef char VertexType;						//顶点的数据类型
    typedef int EdgeType;							//带权图中边上权值的数据类型
    typedef struct{
        
    	VertexType Vex[MaxVertexNum];				//顶点
    	EdgeType Edge[MaxVertexNum][MaxVertexNum];	//边的权
    	int vexnum, arcnum;							//图的当前顶点数和弧数
    } MGraph;

### 邻接矩阵法的性能分析 ###

空间复杂度： O ( ∣ V ∣ ) O(|V|) O(∣V∣) —— 只和顶点数相关，和实际的边数无关，邻接矩阵法采用数组顺序存储的形式，适合用于存储稠密图

无向图的邻接矩阵是对称矩阵，我们可以压缩存储，也就是只存储上三角区或者下三角区

### 邻接矩阵法的性质 ###

![在这里插入图片描述][1d86789284144eae827d439d041e8e8c.png]

设图  G G G 的邻接矩阵为  A A A（矩阵元素为  0 / 1 0/1 0/1），则  A n A^n An 的元素  A n \[ i \] \[ j \] A^n\[i\]\[j\] An\[i\]\[j\] 等于由顶点  i i i 到顶点  j j j 的长度为  n n n 的路径的数目

假设  A A A 如下表所示

![在这里插入图片描述][87c8be16871a4bb29da6fac48b396762.png]

现在要计算  A 2 \[ 1 \] \[ 4 \] , A 2 \[ 2 \] \[ 2 \] A^2\[1\]\[4\], A^2\[2\]\[2\] A2\[1\]\[4\],A2\[2\]\[2\]，该怎么做呢？  
 A 2 \[ 1 \] \[ 4 \] = a 11 × a 14 + a 12 × a 24 + a 13 × a 34 + a 14 × a 44 = 1 A 2 \[ 2 \] \[ 2 \] = a 21 × a 12 + a 22 × a 22 + a 23 × a 32 + a 24 × a 42 = 3 A^2\[1\]\[4\] = a\_\{11\} \\times a\_\{14\} + a\_\{12\} \\times a\_\{24\} + a\_\{13\} \\times a\_\{34\} + a\_\{14\} \\times a\_\{44\} = 1 \\\\ A^2\[2\]\[2\] = a\_\{21\} \\times a\_\{12\} + a\_\{22\} \\times a\_\{22\} + a\_\{23\} \\times a\_\{32\} + a\_\{24\} \\times a\_\{42\} = 3 A2\[1\]\[4\]=a11×a14\+a12×a24\+a13×a34\+a14×a44=1A2\[2\]\[2\]=a21×a12\+a22×a22\+a23×a32\+a24×a42=3  
其中  a 11 a\_\{11\} a11 表示矩阵的第  1 1 1 行第  1 1 1 个元素，其他依此类推

我们画出  A 2 A^2 A2 的表，如下

![在这里插入图片描述][cdf02e03c3144f52a59f1d26c75438ff.png]

可以发现，我们计算出来的值就是这个表中对应位置的值

如果让你计算  A 3 \[ 1 \] \[ 4 \] A^3\[1\]\[4\] A3\[1\]\[4\] 呢？

## 邻接表法（顺序+链式存储） ##

![在这里插入图片描述][875bd028cdf948d5ae993b18798cc8f8.png]

// “边/弧”
    typedef struct ArcNode{
        
    	int adjvex;						//边/弧指向哪个结点
    	struct ArcNode *next;			//指向下一条弧的指针
    	InfoType info;					//边权值（没有可不加）
    }ArcNode;
    
    // “顶点”
    typedef struct VNode{
        
    	VertexType data;			//顶点信息
    	ArcNode *first;				//第一条边/弧
    }VNode, AdjList[MaxVertexNum];
    
    //用邻接表存储的图
    typedef struct{
        
    	AdjList vertices;
    	int vexnum, arcnum;
    }ALGraph;

当然，有向图也可以用邻接表法来表示

![在这里插入图片描述][bdece472cbf940c4963e6b3398c75cc3.png]

### 空间复杂度分析 ###

对于无向图，由于每一条边都会有一个指向的结点占空间，而且是双向的，比如  A A A 和  B B B 之间有一条边，那么  
 A A A 到  B B B 这条边就会有一个指向  B B B 的结点，同理  B B B 到  A A A 这条边就会有一个指向  A A A 的结点，由于边结点的数量是  2 ∣ E ∣ 2|E| 2∣E∣ ，所以整体的空间复杂度为  O ( ∣ V ∣ + 2 ∣ E ∣ ) O(|V| + 2|E|) O(∣V∣\+2∣E∣)

对于有向图，由于每条边都是有方向的，所以只会有一个指向结点，整体的空间复杂度即为  O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|) O(∣V∣\+∣E∣)

### 度、入度和出度 ###

那么，下面我们思考一下怎么求顶点的度、入度和出度呢？

*  对于无向图，我们只要遍历边结点的链表就能求出对应顶点的度
 *  对于有向图，通过遍历边结点的链表我们就能求出对应顶点的出度；但是要得到某个顶点的入度，就很麻烦了，我们需要遍历所有顶点相应的边结点的链表，这也是邻接表法的一个缺点

### 邻接矩阵和邻接表的对比 ###

图的邻接表表示方式并不唯一，与一个顶点有关系的边的顺序是可以颠倒排列的；但是对于前面的邻接矩阵来说，只要确定了顶点编号，那图的邻接矩阵就是唯一的

<table> 
 <thead> 
 <tr> 
 <th>对比角度</th> 
 <th>邻接矩阵</th> 
 <th>邻接表</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>空间复杂度</td> 
 <td> O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)</td> 
 <td>无向图 O ( ∣ V ∣ + 2 ∣ E ∣ ) O(|V| + 2|E|) O(∣V∣+2∣E∣)；有向图 O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|) O(∣V∣+∣E∣)</td> 
 </tr> 
 <tr> 
 <td>适合用于</td> 
 <td>存储稠密图</td> 
 <td>存储稀疏图</td> 
 </tr> 
 <tr> 
 <td>表示方式</td> 
 <td>唯一</td> 
 <td>不唯一</td> 
 </tr> 
 <tr> 
 <td>计算度 / 出度 / 入度</td> 
 <td>必须遍历对应行或列</td> 
 <td>计算有向图的度、入度不方便，其余很方便</td> 
 </tr> 
 <tr> 
 <td>找相邻的边</td> 
 <td>必须遍历对应行或列</td> 
 <td>找有向图的入边不方便，其余很方便</td> 
 </tr> 
 </tbody> 
</table>

## 十字链表 ##

我们需要定义两个结构：弧结点和顶点结点

![在这里插入图片描述][89bd0b630a154cd9b7361f4344303138.png]

空间复杂度为： O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|) O(∣V∣\+∣E∣)

如何找到指定顶点的所有出边？ —— 顺着绿色线路找  
如何找到指定顶点的所有入边？ —— 顺着橙色线路找

注意：十字链表只用于存储有向图

## 邻接多重表 ##

![在这里插入图片描述][ac08f2fca4db4a2fb8255da8a0c4c8e8.png]

空间复杂度为： O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|) O(∣V∣\+∣E∣)

删除边、删除节点等操作很方便

注意：邻接多重表只用于存储无向图

## 总结 ##

<table> 
 <thead> 
 <tr> 
 <th>角度</th> 
 <th>邻接矩阵</th> 
 <th>邻接表</th> 
 <th>十字链表</th> 
 <th>邻接多重表</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>空间复杂度</td> 
 <td> O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)</td> 
 <td>无向图 O ( ∣ V ∣ + 2 ∣ E ∣ ) O(|V| + 2|E|) O(∣V∣+2∣E∣)；有向图 O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|) O(∣V∣+∣E∣)</td> 
 <td> O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|) O(∣V∣+∣E∣)</td> 
 <td> O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|) O(∣V∣+∣E∣)</td> 
 </tr> 
 <tr> 
 <td>找相邻边</td> 
 <td>遍历对应行或列，时间复杂度为 O ( ∣ V ∣ ) O(|V|) O(∣V∣)</td> 
 <td>找有向图的入边必须遍历整个邻接表</td> 
 <td>很方便</td> 
 <td>很方便</td> 
 </tr> 
 <tr> 
 <td>删除边或顶点</td> 
 <td>删除边很方便，删除顶点需要移动大量数据</td> 
 <td>无向图中删除边或顶点都不方便</td> 
 <td>很方便</td> 
 <td>很方便</td> 
 </tr> 
 <tr> 
 <td>适用于</td> 
 <td>存储稠密图</td> 
 <td>存储稀疏图或其他</td> 
 <td>只能存储有向图</td> 
 <td>只能存储无向图</td> 
 </tr> 
 <tr> 
 <td>表示方式</td> 
 <td>唯一</td> 
 <td>不唯一</td> 
 <td>不唯一</td> 
 <td>不唯一</td> 
 </tr> 
 </tbody> 
</table>

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_11984530.html?spm=1001.2014.3001.5482
[1348bd38bc3c4e1bbf224574da053d30.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/63f82ab0a7274126a368d54167ca2bea.png
[1d86789284144eae827d439d041e8e8c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/af2414c2659e4b698f2ac87b76efeae6.png
[87c8be16871a4bb29da6fac48b396762.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/e0436d11a868459c82fcf70a32e8b676.png
[cdf02e03c3144f52a59f1d26c75438ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/490f4d28525849a4a50a599c236a7cc6.png
[875bd028cdf948d5ae993b18798cc8f8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f6ae7936a24f4fb4aab001b5f30fd690.png
[bdece472cbf940c4963e6b3398c75cc3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/3d45d8d3dc824e1eb31ae1bcbd8f342e.png
[89bd0b630a154cd9b7361f4344303138.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/fc415da35dbb47f98323b1b0cb17123a.png
[ac08f2fca4db4a2fb8255da8a0c4c8e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/86aa595a0f0748ecaa8f21b7448b0ce4.png