资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授,：刘斌,图的邻接表表示,常州信息职业技术学院,02,教,学,目标,1,2,3,邻接表,相关概念,03,图的邻接表表示,邻接表的特点,三、链表的插入,04,邻接表的相关概念,0.4,1,图的邻接表（,Adjacency List,）,对于图,G,中的每个顶点,vi,，把所有邻接于,vi,的顶点,vj,链成一个带头结点的单链表，这个单链表称为顶点,vi,的,邻接表,。,2,邻接表的结点结构,（,1,）结点结构,邻接表中每个结点均有两个域,邻接点域,adjvex,，用于存放与,vi,相邻接的顶点,vj,的序号,j,；,指针域,next,，用于指向下一个结点链。,注意：,若要表示边上的信息（如权值），则在邻接表结点中还应增加一个数据域。,边表结点结构,指针域,邻接点域,05,邻接表的相关概念,0.4,（,2,）头结点结构,顶点,vi,邻接表的头结点包含两个域,顶点域,vertex,，用于存放顶点,vi,的信息；,指针域,firstedge,，作为,vi,邻接表的头指针。,3,无向图的邻接表,对于无向图，顶点,vi,的邻接表中每个结点都对应与,vi,相邻接的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。,顶点表结点结构,指针域,顶点域,06,图的邻接表表示,0.4,【,示例,】,V0,V3,V1,V2,vertex,firstedge,0,1,2,3,v0,v1,v2,v3,0,1,1,0,3,2,1,3,07,图的邻接表表示,0.4,4,有向图的邻接表,对于有向图，顶点,vi,的邻接表中每个结点都对应以,vi,为始点射出的一条边。因此，将有,向图的邻接表称为出边表。,【示例】,V0,V3,V1,V2,vertex,firstedge,0,1,2,3,v0,v1,v2,v3,2,1,1,3,3,07,图的邻接表表示,0.4,5,有向图的逆邻接表,在有向图中，顶点,vi,的逆邻接表中每个结点都对应以,vi,为终点射入的一条边。因此，将有向图的逆邻接表称为入边表。,【示例】,vertex,firstedge,0,1,2,3,v0,v1,v2,v3,0,1,0,1,3,V0,V3,V1,V2,三、链表的插入,08,图的邻接表表示,3.1,1,2,6,图的邻接表表示,（,1,）用邻接表（边表）表示顶,点间的邻接关系；,（,2,）用一个顺序表（顶点表）来,存储顶点信息。,09,图的邻接表表示,0.4,1,2,4,5,3,7,邻接表的特点,图的邻接表不仅能表示顶点之间的邻接关系，还能表示图的其它特性。,（,1,）存储唯一性：邻接表的存储表示不唯一，边表结点的次序不同得到不同的存储。,（,2,）顶点的个数：顶点表含元素的个数表示该图顶点的个数。,（,3,）边的个数：无向图每个顶点边表结点个数的和的一半表示该无向图边的个数；有向图每个顶点边表结点个数的和表示该有向图边的个数。,（,4,）顶点的度：无向图顶点,v,边表结点的个数表示顶点,v,的度。有向图顶点,vi,边表结点的个数表示顶点,vi,的出度，其它顶点边表中值为,i,的结点个数的和表示顶点,vi,的入度。,（,5,）两顶点的邻接性：无向图第,i,个（第,j,个）顶点的边表有值为,j,（,i,）的结点表示顶点,vi,与顶点,vj,相邻接；有向图第,i,个顶点的边表有值为,j,的结点表示顶点,vi,邻接到顶点,vj,。,THANKS,2016.9.18,
展开阅读全文