邻接多重表是一种用于存储无向图的链式存储结构，其核心思想是通过共享边信息来优化邻接表的存储效率。以下是对其关键特性的详细解析：

一、基本结构

顶点表

存储图中所有顶点的信息，每个顶点对应一个节点，包含顶点数据和指向边表节点的指针（firstedge）。

边表

每条边由一个节点表示，该节点包含两个顶点的下标（iVex和jVex），以及两个指针：

ilink：指向依附于顶点iVex的下一条边

jlink：指向依附于顶点jVex的下一条边

二、与邻接表的区别

邻接多重表通过以下方式改进邻接表：

边信息共享 ：同一条边（vi, vj）在邻接表中需要存储两个节点（分别对应vi和vj的链表），而在邻接多重表中仅存储一个节点，从而减少存储空间。

操作效率提升 ：删除或标记边时，无需在两个链表中分别查找，只需修改一个节点的指针。

三、优势与适用场景

效率优势

存储效率 ：减少边信息的重复存储，降低空间复杂度。

操作效率 ：删除、标记已访问边等操作时间复杂度从O（2）降低到O（1）。

适用场景

需频繁对边进行操作（如标记、删除）的无向图。

顶点数较大但边数较少的稀疏图。

四、结构示意图

顶点表: V0 → 边表1 → V1 → 边表2 → V2 → ...

边表节点结构:

data: 边信息（如权重）

iVex: 顶点索引 → 下一条边指针

jVex: 顶点索引 → 下一条边指针

五、示例

假设有无向图V0-V1-V2，边（V0,V1）和（V1,V2）：

在邻接表中需存储两个节点，分别位于V0和V1的链表中。

在邻接多重表中仅存储一个节点，通过iVex和jVex分别指向V0和V1的链表，避免重复存储。

通过上述结构设计，邻接多重表在存储无向图时既保留了邻接表的灵活性，又克服了其边信息重复存储的缺点，是图论中一种高效且实用的存储结构。