邻接多重表是一种用于存储无向图的链式存储结构。它解决了使用邻接表存储无向图时出现的同一条边需要存储两次的问题。十字链表存有向图。
存储结构
邻接多重表是无向图的另一种链式存储结构。
在邻接表中，求出度比较方便，但求入度不方便，同时逆邻接表求入度方便但求出度不方便。因此邻接多重表是结合二者的改进版。
与十字链表类似，在邻接多重表中，每一条边用一个结点表示，其结构如下图：
| mark | ivex | ilink | jvex | jlink | info |
|---|
- 表头结点即顶点结点，与邻接表一样是顺序存储。
- 对于每个顶点结点之后是与之相关联的边结点（与该顶点结点相连的边），而邻接表则是一些与顶点结点相连接的点。
- 从每个顶点结点开始有一条链表，这条链表将所有与该顶点相连的边都连接了起来。
- 邻接多重表中边结点的个数就是无向图中边的数量，又因为无向图中的边必然连接两个顶点，所以便边结点结构中的ilink和jlink会连接两个不同的链表。
Example
代码实现
typedef struct Ebox
{
VisitIf mark; // 访问标记
int ivex, jvex;//该边依附的两个顶点的位置
struct EBox *ilink, *jlink;
InfoType *info; // 该边信息指针
} EBox;
typedef struct VexBox
{
VertexType data;
EBox *firstedge; // 指向第一条依附该顶点的边
} VexBox;
typedef struct // 邻接多重表
{
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum, edgenum;
} AMLGraph;