扫码获取更多资源

●邻接多重表

当用邻接表存储无向图时，每条边(Vj, Vj)有两个结点，分别在以V,和V,为头结点的单 链表中，这种重复存储给图的某些操作带来不便。例如，对已访问过的边做标记，或者要删 除图中某一条边，等等，都需要找到表示同一条边的两个表结点。因此，在进行这类操作的 无向图中采用邻接多重表作为存储结构更为适宜。

邻接多重表(Adjacency Multilist)是无向图的另一种存储表示，其结构和有向图十字链 表类似。在邻接多重表中，对应于无向图中每一条边有一个结点，对应于每个顶点也有一个 结点，如图7-20所示。其中，头结点由两个域组成，顶点域(vex)存放顶点信息，指针域 (firstedge)指向第一条依附于该顶点的边；表结点由六个域组成，标志域(mark)标记该边 是否被搜索过，两个位置域(ivex和jvex)分别指示该边所依附的两个顶点在图中的位置，两 个链域(ilink和jlink)分别指向下一条依附于ivex和jvex的边，权域(weight)存放网中边 的权值(图无此域)。

图7-21给出了无向图及其邻接多重表存储结构。

邻接多重表的类型定义

邻接多重表的特点

在邻接多重表中，所有依附于同一个顶点的边串联在同一个链表中，由于每条边依附于 两个顶点，则每个表示边的表结点同时连接在两个链表中。对无向图而言，其邻接多重表和 邻接表的差别仅仅在于：同一条边在邻接表中用两个结点表示，而在邻接多重表中只用一 个结点。因此，除了在表结点中增加一个标志域以外，邻接多重表所需要的存储量和邻接表 相同。在邻接多重表上，各种基本操作的实现也和邻接表相似。

联系我们：