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

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

    [复制链接]

    2

    主题

    2

    帖子

    6

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    6
    基情
    4
    发表于 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;
    回复

    使用道具 举报

    0

    主题

    1

    帖子

    1

    积分

    新手上路

    Rank: 1

    积分
    1
    基情
    0
    发表于 2017-6-26 17:51:04 | 显示全部楼层
    看过必回,人品超好!












    现实竞争如此激烈,如何在同行中胜出?
    帮您抓住无限商机——海量投放广告,让有需求的客户主动找到您!

    联系QQ:188662616   微信号:188662616


    一直被同行模仿,从来没有被超越!

    智友网络推广是一家专业从事网络营销推广和软件开发销售的专业技术团队,真正的网络营销业内人士;8年来,我们一直从事网络推广,从未间断过,因为专业,才值得依赖;我们有一支高素质的团队,为客户和合作伙伴提供一个最好支持和机会的平台。对于发展期的我们,创新和独特是我们的优势,我们期待更多的合作伙伴认识我们、了解我们,与我们共同发展;
    【联系我们】

    联系QQ:188662616 微信号:188662616

    献县专业代发帖子,远发网络推广,土默特左旗论坛发帖,长沙产品推广,瓦房店外链代发,景谷软文代发,柘荣网络营销,灵川网络推广策划方案|沙湾手工代发外链|即墨博客论坛推广|贞丰代发帖子包收录|随州如何进行网络推广|沙市广告公司|禹城代发论文广告|保山网络推广知识|安龙店铺推广|巩县营销外包 。
    回复 支持 反对

    使用道具 举报

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

    本版积分规则

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

    GMT+8, 2017-8-23 18:14 , Processed in 0.265201 second(s), 13 queries , File On.

    Powered by 深嵌论坛 X3.3

    © 2001-2013 Comsenz Inc.

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