邻接多重表、十字链表
标签: 数据结构
学习人数: 6694


全屏播放
赞赏支持

邻接多重

邻接多重表(Adjacency Multilist)主要用于存储无向图。因为,如果用邻接表存储无向图,每条边的两个边结点分别在以该边所依附的两个顶点为头结点的链表中,这给图的某些操作带来不便。例如,对已访问过的边做标记,或者要删除图中某一条边等,都需要找到表示同一条边的两个结点。因此,在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。

 

邻接多重表的存储结构和十字链表类似,也是由顶点表和边表组成,每一条边用一个结点表示,其顶点表结点结构和边表结点结构如图所示。

其中,顶点表由两个域组成,vertex 域存储和该顶点相关的信息firstedge 域指示第一条依附于该顶点的边;边表结点由六个域组成,mark 为标记域,可用以标记该条边是否被搜索过;ivex 和jvex 为该边依附的两个顶点在图中的位置;ilink 指向下一条依附于顶点ivex的边;jlink 指向下一条依附于顶点jvex 的边,info 为指向和边相关的各种信息的指针域。

 

例如,上图所示为无向图的邻接多重表...

登录查看完整内容


课后作业

掌握本节内容


登录后发布评论

暂无评论,来抢沙发