【数据结构】图论存储结构深度解析：邻接多重表如何实现无向图O(1)删边？邻接矩阵/链表/十字链对比

导读

大家好，很高兴又和大家见面啦！！！

经过前面的内容，我们已经学习了图的三种存储结构：

• 邻接矩阵
• 邻接表
• 十字链表

在今天的内容中我们将会介绍图的第四种存储结构以及图的一些基本操作。下面我们直接进入今天的内容；

一、有向图的存储结构

在有向图中，我们可以通过3种存储结构来存储有向图的顶点与弧的信息，并且这三种存储结构各有其优缺点：

• 邻接矩阵
  • 优点：能高效查找两个顶点之间的边，适合存储稠密图
  • 不足：会浪费大量的存储空间
• 邻接表
  • 优点：通过链式存储大大节省了存储空间，适合存储稀疏图
  • 不足：边的查找效率低下
• 十字链表
  • 优点：提高了弧的查找效率，节省了存储空间
  • 不足：十字链表只能存储有向图

相较于邻接矩阵与邻接表，十字链表不仅提高了弧的查找效率，还节省了存储空间。

但是十字链表法并不能像邻接矩阵和邻接表一样不仅可以存储有向图，还可以存储无向图，十字链表法只能够存储有向图。

那对于无向图而言，有没有一种存储结构既能够提高边的查找效率，又能够节省存储空间呢？

二、邻接多重表

在邻接表中，容易求得顶点和边的各种信息，但求两个顶点之间是否存在边儿执行删除边等操作时，需要分别在两个顶点的边表中遍历，效率低。

邻接多重表（Adjacency Multilist​​）是无向图的一种链式存储结构。与十字链表类似，在邻接多重表中，每条边用一个结点表示，其结构如下所示：

graph TB
a[ivex]
b[ilink]
c[jvex]
d[jlink]
e[info]

其中：

• ivex与jvex中存储的是该边依附的两个顶点编号；
• ilink 指向的时依附于顶点 i 的下一条边
• jlink 指向的时依附于顶点 j 的下一条边
• info 中存放的时该边的相关信息，如边的权值

每个顶点也用一个结点表示，它由两个域组成：

• data 域存放该顶点的相关信息
• firstedge 域指向的时依附于该顶点的第一条边

邻接多重表.jpg

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，因为每条边依附于两个顶点，所以每个边结点同时链接在两个链表中。

在无向图中，其邻接表与邻接多重表的差别在于——同一条边在两个表中的结点数量不同：

• 邻接表中，同一条边用两个结点表示
• 邻接多重表中，只用一个结点表示

三、存储结构

邻接多重表的存储结构中，同样需要定义两种结点类型：

#define MAXSIZE 5
typedef int Edge_ElemType;				// 边信息数据类型
typedef int Vert_ElemType;				// 顶点信息数据类型
typedef struct Edge_Node {
	int ivex;							// 顶点i的编号
	int jvex;							// 顶点j的编号
	struct Edge_Node* ilink, * jlink;	// 依附于顶点i与顶点j的边
	Edge_ElemType info;					// 边的信息
}ENode;									// 边结点
typedef struct VertexNode {
	Vert_ElemType data;					// 顶点信息
	ENode* firstedge;					// 依附于顶点的第一条边的结点
}VNode;									// 顶点结点
typedef struct Adjacency_Multilist​​ {
	VNode vert_list[MAXSIZE];			// 顶点表
	int edge_num;						// 边的数量
	int vert_num;						// 顶点数量
}AMGraph;								// 邻接多重表

当图中的边没有权值时，可以省略边结点中的info域；

四、算法评价

邻接多重表的算法评价同样以邻接多重表的遍历进行评价；

4.1 时间复杂度

在邻接多重表中，遍历所有顶点就是遍历一个顺序表，对于顶点数为 |V| 的图，其时间复杂度为 O(|V|)；

遍历所有边只需要将每一条边都遍历一次，对于边数为 |E| 的图，其时间复杂度为 |E|；

整个图的遍历对应的时间复杂度为 T(N) = O(|V| + |E|)；

4.2 空间复杂度

在邻接多重表中，对于顶点数为 |V| ，边数为 |E| 的图而言，其需要的空间复杂度为 T(N) = O(|V| + |E|)；

五、四种存储方式的总结

下面我们会从五个维度来探讨这四种存储方式：

5.1 空间复杂度

在邻接矩阵中，对于结点数为 n 的图，不管是有向图还是无向图都需要申请 n^2 的空间，因此其空间复杂度均为 n^2 ；

在邻接表中，对于结点数为 |V| 和边数为 |E| 的图，在有向图和无向图中，其空间复杂度并不相同：

• 有向图中，需要申请 |V| 个结点空间和 |E| 个边空间，因此对应的空间复杂度为：O(|V| + |E|)；
• 无向图中，需要申请 |V| 个结点空间和 2 * |E| 个边空间，因此对应的空间复杂度为：O(|V| + 2|E|)；

在十字链表中，对于结点数为 |V| 和边数为 |E| 的图，需要申请同等数量的结点空间和边空间，其对应的空间复杂度为：O(|V| + |E|)；

在邻接多重表中，对于结点数为 |V| 和边数为 |E| 的图，需要申请同等数量的结点空间和边空间，其对应的空间复杂度为：O(|V| + |E|)；

5.2 找相邻边

在邻接矩阵中，当我们要查找一个顶点的相邻边时，我们只需要遍历该顶点对应的行或者列。在邻接矩阵中，行数与列数都是图的顶点数 |V| ，因此对应的时间复杂度为 O(|V|) ；

在邻接表中，当我们要查找一个顶点的相邻边时，对于有向图与无向图而言，其查找邻边的时间复杂度也是有所区别：

• 无向图中，邻接表查找邻边时，只需要遍历该结点所指向的边表即可
• 有向图中，邻接表查找邻边时，对于出度与入度的时间复杂度也是有区别：
  • 出度：查找一个顶点的出度，只需要遍历该结点所指向的边表即可
  • 入度：查找一个顶点的入度，需要遍历整个邻接表

在十字链表中，当我们要查找一个顶点的相邻边时，就是查找该顶点的出度与入度，这时只需要分别遍历该结点的出度表与入度表即可

在邻接多重表中，当我们要查找一个顶点的相邻边时，只需要遍历对应的结点所邻接的边表即可

5.3 删除边或结点

在邻接矩阵中：

• 当我们要删除一条边时，只需要修改对应边在矩阵中的值即可
• 当我们要删除一个顶点时，需要移动大量的数据

在邻接表中：

• 有向图：
  • 删除边：只需要删除对应的边结点即可
  • 删除顶点：需要删除与该结点相邻的所有边结点以及该顶点
• 无向图：
  • 删除边：需要删除其依附的两个顶点所对应的边表中的边结点
  • 删除顶点：需要删除与该结点相邻的所有边结点以及该顶点

在十字链表和邻接多重表中：

• 删除边：我们只需要删除其对应的边结点即可
• 删除顶点：需要删除与该顶点相邻的所有边结点以及该顶点信息

不难发现，在图中，当我们要删除一个顶点时，实际上就是需要查找该顶点相邻边并进行删除，因此其删除操作是基于查找操作实现；

5.4 适用于

邻接矩阵由于需要消耗大量的空间用于存储边，因此适用于存储稠密图；

在邻接表中，由于边表是通过链表实现，能够节省存储空间，因此对于稀疏图而言，更加适合用邻接表进行存储；

在十字链表中，只能够存储有向图

在邻接多重表中，只能够存储无向图

5.5 表示方式

邻接矩阵是由各个顶点组成的矩阵，因此，其表示方式是唯一的；

在邻接表、十字链表以及邻接多重表中，由于边表的信息是通过链表进行的存储，因此其边表的表示方式并不唯一；

六、图的基本操作

图的基本操作时独立于图的存储结构的。而对于不同的存储方式，操作算法的具体实现会有着不同的性能。在设计具体算法的实现时，应考虑采用何种存储方式的算法效率会更高。

图的基本操作主要包括：

• Adjacent(G, x, y): 判断图G是否存在边<x, y>或(x, y)；
• Neighbors(G, x): 列出图G中与结点x邻接的边
• InsertVertex(G, x): 在图G中插入顶点x
• DeleteVertex(G, x): 在图G中删除顶点x
• AddEdge(G, x, y): 若无向边(x, y)或有向边<x, y>不存在，则向图G中添加改边
• RemoveEdge(G, x, y): 若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边
• FirstNeighbors(G, x): 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1
• NextNeighbors(G, x, y): 假设图G中顶点 y 是顶点 x 的一个邻接点，返回除 y 外顶点 x 的下一个邻接点的顶点号，若 y 是 x 的最后一个邻接点，则返回-1
• Get_edge_value(G, x, y): 获取图G中边(x, y) 或 <x, y> 对应的权值
• Set_edge_value(G, x, y, v): 设置图G中边(x, y) 或 <x, y> 对应的权值

此外，还有图的遍历算法：按照某种方式访问图中的每个顶点，且仅访问一次。图的遍历算法有两种：

• 深度优先遍历（Depth-First-Search, DFS）
• 广度优先遍历（Breadth-First-Search, BFS）

具体内容会在下一个篇章中进行介绍。

结语

邻接多重表以“单边双链”的革新设计，将无向图的存储效率推向新高度——空间占用减半、删边操作跃升至​​O(1)​​，完美解决了邻接表的冗余与低效痛点。

从邻接矩阵的刚性布局到链式结构的动态灵动，每一种存储方案都是空间与时间的精妙权衡，而​​邻接多重表无疑是高频删边场景的无向图终极答案​​。

​​但存储结构只是图算法的起点​​，真正的挑战在于如何基于这些结构实现高效操作。​​下一篇将深入图的广度优先遍历（BFS）​​，解析其在邻接矩阵、邻接表及邻接多重表中的性能差异，并揭秘如何通过存储优化让BFS在千万级节点图中依然游刃有余！