题16

题16

题目

邻接多重表是 ( ) 的存储结构.
A. 无向图
B. 有向图
C. 无向图和有向图
D. 都不是

分析

为了理解邻接多重表，先要明白邻接表的结构，邻接表只存每个点和他的相邻点，但是对于无向图，每条边都是双向的，所以邻接表中每个点的相邻点都要存两次。
邻接多重表就是为了解决这个问题，它存每条边的两个端点，每个点的相邻点只存一次
也就是邻接多重表是以边为中心的
假设有一个无向图 G，包含以下顶点和边：

• 顶点集 V = {A, B, C, D}
• 边集 E = { (A,B), (A,C), (B,C), (C,D) }
  使用邻接多重表表示图 G，可以使用以下结构：

顶点节点：

节点 1：data = A, firstedge = -> 边节点 1
节点 2：data = B, firstedge = -> 边节点 2
节点 3：data = C, firstedge = -> 边节点 3
节点 4：data = D, firstedge = -> 边节点 4

边节点：

边节点 1：ivex = A, jvex = B, ilink = -> 边节点 2, jlink = -> 边节点 null
边节点 2：ivex = A, jvex = C, ilink = -> 边节点 null, jlink = -> 边节点 3
边节点 3：ivex = B, jvex = C, ilink = -> 边节点 4, jlink = -> 边节点 null
边节点 4：ivex = C, jvex = D, ilink = -> 边节点 null, jlink = -> 边节点 null

在这个例子中，每个边节点代表图 G 中的一条边，例如边节点 1 代表边 (A, B)。 ivex 和 jvex 域分别存储边的两个顶点 A 和 B。ilink 域将边节点 1 链接到下一个与顶点 A 相邻的边节点 2。 jlink 域将边节点 1 链接到下一个与顶点 B 相邻的边节点，由于没有其他边与顶点 B 相邻，因此 jlink 域指向 null。

解

A
核心关键在于，他会保存边和他的两个结点，以及对于每个结点，再存它的下一条边
邻接多重表是无向图的存储结构。