请选择 进入手机版 | 继续访问电脑版
    查看: 597|回复: 0

    8.2 图的存储表示—邻接多重表

    [复制链接]

    1015

    主题

    1073

    帖子

    3705

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    3705
    基情
    1841
    发表于 2016-9-9 23:28:18 | 显示全部楼层 |阅读模式
    邻接多重表(Adjacency Multilist)主要用于存储无向图。因为,如果用邻接表存储无向图,每条边的两个边结点分别在以该边所依附的两个顶点为头结点的链表中,这给图的某些操作带来不便。例如,对已访问过的边做标记,或者要删除图中某一条边等,都需要找到表示同一条边的两个结点。因此,在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。

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

    8.2 图的存储表示—邻接多重表

    8.2 图的存储表示—邻接多重表

    8.2 图的存储表示—邻接多重表

    8.2 图的存储表示—邻接多重表

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

    8.2 图的存储表示—邻接多重表

    8.2 图的存储表示—邻接多重表

    例如,图8.16 所示为无向图8.1 的邻接多重表。在邻接多重表中,所有依附于同一顶点的边串联在同一链表中,由于每条边依附于两个顶点,则每个边结点同时链接在两个链表中。可见,对无向图而言,其邻接多重表和邻接表的差别,仅仅在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。因此,除了在边结点中增加一个标志域外,邻接多重表所需的存储量和邻接表相同。在邻接多重表上,各种基本操作的实现亦和邻接表相似。邻接多重表存储表示的形式描述如下:
    #define MAX_VERTEX_NUM 20
    typedef emnu{ unvisited,visited} VisitIf;
    typedef struct EBox{
    VisitIf mark: /*访问标记*/
    int ivex,jvex; /*该边依附的两个顶点的位置*/
    struct EBox ilink, jlink; /*分别指向依附这两个顶点的下一条边*/
    InfoType info; /*该边信息指针*/
    }EBox;
    typedef struct VexBox{
    VertexType data;
    EBox fistedge; /*指向第一条依附该顶点的边*/
    }VexBox;
    typedef struct{
    VexBox adjmulist[MAX_VERTEX_NUM];
    int vexnum,edgenum; /*无向图的当前顶点数和边数*/
    }AMLGraph;


    上一篇:8.2 图的存储表示—十字链表
    下一篇:8.3 图的遍历
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|小黑屋|网站地图|DZ商业模板|VR福利资源|嵌入式Linux论坛 ( 粤ICP备15085165号-2

    GMT+8, 2017-1-19 23:01 , Processed in 0.731236 second(s), 52 queries .

    Powered by 深嵌论坛 X3.2

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表