clwn.net
当前位置:首页 >> 邻接表 >>

邻接表

邻接表是图的一种链式存储结构.对图的每个顶点建立一个单链表(n个顶点建立n个单链表),第i个单链表中的结点包含顶点Vi的所有邻接顶点.

注意:n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点.(换句话说,每条边(i,j)在邻接表 中出现两次:一次在关于i的邻接表中,另一次在关于j的邻接表中) 对于有向图,vi的邻接表中每个表结点都对应于以vi为始点

第一步:观察图有多少顶点,这里,ABCDE有5个,就划5个顶点的,数组,并在旁边编号01234.第二步:从上到下,依次观察ABCDE这5个结点,首先A结点,它发出2条边B,D,所以把它的指针首先随便指向一个B或者D的编号,这里指向D,因为D的编号是3,然后指向另外的没有指向的编号B,就是了.最后没有边的,指向就是空指针.第三步:依次按照A点的方法,写出BCDE点的指向的边的编号,没有就用空表示.理解的关键.邻接表数据的那个顶点和后面指向的编号的结点,这两个点的意思和写法不同,数组的表示的存储的具体的结点信息,后边的表示它发出的邻近结点的编号,没有其他的结点信息.

由图可知共有5个元素.1 2 3 4 5.先列出5*5的空矩阵,标上行、列.先从1出发,在空矩阵中,遇到自己写0,即a(1,1)写0. 1连接着2、3、4,a(1,2),a(1,3)写,a(1,4)写1.没有连5,a(1,5)写0.其他各行类推. (列\行) 1 2 3 4 5 1(0 1 1 1 0) 2(1 0 1 0 1) 3(1 1 0 1 1) 4(1 0 1 0 1) 5(0 1 1 1 0)

稀疏图.矩阵表示法较合适于表示稠密图,而邻接表方式因为链表的关系适用于结点间关联较少的.

1.可以.2.如果a->b和b->a均在邻接表里成对存在,则是无向图的邻接表,否则是有向图的邻接表.a和b是图中顶点.

邻接表有多种实现方式,比如最简单的动态链表,对于一个无向图,为每个节点建一个动态链表,储存的只是这个节点每个相邻的点,而在邻接矩阵中,对于每个节点需要把它与其他所有点的关系都表示出来(相邻为1,不相邻为0),空间复杂度明显是邻接矩阵大,至于查询两者各有千秋,如果只是查询两个点之间是否相邻,邻接矩阵当然更快,但如果是做dfs的话,找当前节点相邻的点,如果用邻接矩阵的话每次都要从1扫到n,如果用邻接表的话每次只需把当前节点邻接表后的点都取出来即可.

发给你邮箱里了,给分!!!!!

另外,由于这是稀疏图,我们用邻接表来存储,则空间复杂度仅为O(NM),同样可以承受

网站首页 | 网站地图
All rights reserved Powered by www.clwn.net
copyright ©right 2010-2021。
内容来自网络,如有侵犯请联系客服。zhit325@qq.com