5.2.4 邻接多重表

邻接多重表时无向表的另一种链式存储结构。

在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边,或需要对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。

与十字链表类似,在邻接多重表中,每一条边用一个结点表示,其结构如下图:

mark

ivex

ilink

jvex

jlink

info

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

每一个顶点也用一个顶点表示,它由如下所示的两个域组成。

data

firstedge

其中,data域存储该顶点的相关信息,firstedge域指示第一条依附于该顶点的边。

在邻接多重表中,所有依附于同一顶点的边串联在同一链表中,由于每条边依附于两个顶点,则每个边结点同时链接在两个链表中。

#define MaxVertexNum 100//顶点数目的最大值

typedef struct ArcNode{//边表结点
    bool mark;//访问标记
    int ivex,jvex;//分别指向该弧的两个结点
    struct ArcNode *ilink,*jlink;//分别指向两个顶点的下一条边
    InforType info;//相关信息指针
}ArcNode;

typedef struct VNode{//顶点表结点
   VertextType data;//顶点信息
   ArcNode *firstedge;//指向第一条依附该顶点的边
}VNode;

typedef struct{
   VNode adjmulist[MaxVertexNum];//邻接表
   int vexnum ,arcnum;//图的顶点数和弧数
}AMLGraph;//AMLGraph 是以邻接表存储的图类型

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

扫码关注云+社区

领取腾讯云代金券