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

    8.2 图的存储表示—邻接表

    [复制链接]

    2

    主题

    2

    帖子

    6

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    6
    基情
    4
    发表于 2016-9-9 23:28:11 | 显示全部楼层 |阅读模式
    邻接表(Adjacency List)是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G 中的每个顶点vi,将所有邻接于vi 的顶点vj 链成一个单链表,这个单链表就称为顶点vi 的邻接表,再将所有点的邻接表表头放到数组中,就构成了图的邻接表。在邻接表表示中有两种结点结构,如图8.9 所示。

    8.2 图的存储表示—邻接表

    8.2 图的存储表示—邻接表
    一种是顶点表的结点结构,它由顶点域(vertex)和指向第一条邻接边的指针域(firstedge)构成,另一种是边表(即邻接表)结点,它由邻接点域(adjvex)和指向下一条邻接边的指针域(next)构成。对于网图的边表需再增设一个存储边上信息(如权值等)的域(info),网图的边表结构如图8.10 所示。

    8.2 图的存储表示—邻接表

    8.2 图的存储表示—邻接表

    邻接表表示的形式描述如下:
    #define MaxVerNum 100 /*最大顶点数为100*/
    typedef struct node{ /*边表结点*/
    int adjvex; /*邻接点域*/
    struct node * next; /*指向下一个邻接点的指针域*/
    /*若要表示边上信息,则应增加一个数据域info*/
    }EdgeNode;
    typedef struct vnode{ /*顶点表结点*/
    VertexType vertex; /*顶点域*/
    EdgeNode * firstedge; /*边表头指针*/
    }VertexNode;
    typedef VertexNode AdjList[MaxVertexNum]; /*AdjList 是邻接表类型*/
    typedef struct{
    AdjList adjlist; /*邻接表*/
    int n,e; /*顶点数和边数*/
    }ALGraph; /*ALGraph 是以邻接表方式存储的图类型*/
    建立一个有向图的邻接表存储的算法如下:
    void CreateALGraph(ALGraph *G)
    {/*建立有向图的邻接表存储*/
    int i,j,k;
    EdgeNode * s;
    printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");
    scanf("%d,%d",&(G->n),&(G->e)); /*读入顶点数和边数*/
    printf("请输入顶点信息(输入格式为:顶点号<CR>):\n");
    for (i=0;i<G->n;i++) /*建立有n 个顶点的顶点表*/
    {scanf("\n%c",&(G->adjlist.vertex)); /*读入顶点信息*/
    G->adjlist.firstedge=NULL; /*顶点的边表头指针设为空*/
    }
    printf("请输入边的信息(输入格式为:i,j):\n");
    for (k=0;k<G->e;k++) /*建立边表*/
    {scanf("\n%d,%d",&i,&j); /*读入边<Vi,Vj>的顶点对应序号*/
    s=(EdgeNode*)malloc(sizeof(EdgeNode)); /*生成新边表结点s*/
    s->adjvex=j; /*邻接点序号为j*/
    s->next=G->adjlist.firstedge; /*将新边表结点s 插入到顶点Vi 的边表头部*/
    G->adjlist.firstedge=s;
    }
    }/*CreateALGraph*/
    算法8.2

    若无向图中有n 个顶点、e 条边,则它的邻接表需n 个头结点和2e 个表结点。显然,在边稀疏(e<<n(n-1)/2)的情况下,用邻接表表示图比邻接矩阵节省存储空间,当和边相关的信息较多时更是如此。

    在无向图的邻接表中,顶点vi 的度恰为第i 个链表中的结点数;而在有向图中,第i个链表中的结点个数只是顶点vi 的出度,为求入度,必须遍历整个邻接表。在所有链表中其邻接点域的值为i 的结点的个数是顶点vi 的入度。有时,为了便于确定顶点的入度或以顶点vi 为头的弧,可以建立一个有向图的逆邻接表,即对每个顶点vi 建立一个链接以vi为头的弧的链表。例如图8.12 所示为有向图G2(图8.2)的邻接表和逆邻接表。

    8.2 图的存储表示—邻接表

    8.2 图的存储表示—邻接表
    在建立邻接表或逆邻接表时,若输入的顶点信息即为顶点的编号,则建立邻接表的复杂度为O(n+e),否则,需要通过查找才能得到顶点在图中位置,则时间复杂度为O(n·e)。

    在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点,但要判定任意两个顶点(vi 和vj)之间是否有边或弧相连,则需搜索第i 个或第j 个链表,因此,不及邻接矩阵方便。
    回复

    使用道具 举报

    0

    主题

    2

    帖子

    2

    积分

    新手上路

    Rank: 1

    积分
    2
    基情
    0
    发表于 2017-6-26 21:11:47 | 显示全部楼层
    没来得急看,应该不错,先帮你顶












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

    联系QQ:188662616   微信号:188662616


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

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

    联系QQ:188662616 微信号:188662616

    四平专业代发帖子,蕲春网络推广,固镇论坛发帖,白城产品推广,奉化外链代发,合水软文代发,西峡网络营销,孟津网络推广策划方案|宁德手工代发外链|临泽博客论坛推广|新平代发帖子包收录|彭泽如何进行网络推广|昌江广告公司|封丘代发论文广告|宝鸡网络推广知识|罗定店铺推广|乌兰营销外包 。
    回复 支持 反对

    使用道具 举报

    0

    主题

    3

    帖子

    3

    积分

    新手上路

    Rank: 1

    积分
    3
    基情
    0
    发表于 2017-6-30 00:22:06 | 显示全部楼层

    国外uu,国产uu最新地址开放注册了,网站难找



    iuuvip.com
    回复 支持 反对

    使用道具 举报

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

    本版积分规则

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

    GMT+8, 2017-8-23 18:02 , Processed in 0.280800 second(s), 12 queries , File On.

    Powered by 深嵌论坛 X3.3

    © 2001-2013 Comsenz Inc.

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