欢迎来到天天文库
浏览记录
ID:34266759
大小:917.00 KB
页数:3页
时间:2019-03-04
《邻接表和逆邻接表的教程》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、图的邻接表表示法 图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi,该方法把所有邻接于vi的顶点vj链成一个带头 结点的单链表,这个单链表就称为顶点vi的邻接表(AdjacencyList)。 1.邻接表的结点结构 (1)表结点结构 ┌────┬───┐ │adjvex│next│ └────┴───┘ 邻接表中每个表结点均有两个域: ①邻接点域adjvex 存放与vi相邻接的顶点vj的序号j。 ②链域next 将邻接表的所有表结点链在一起。 注意: 若要表示边上的信息(如权值),则在表结点中还应增加一个数据域。 (2)头结点结构 ┌─
2、───┬─────┐ │vertex│firstedge│ └────┴─────┘ 顶点vi邻接表的头结点包含两个域: ①顶点域vertex 存放顶点vi的信息 ②指针域firstedge vi的邻接表的头指针。 注意: ①为了便于随机访问任一顶点的邻接表,将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。 ②有时希望增加对图的顶点数及边数等属性的描述,可将邻接表和这些属性放在一起来描述图的存储结构。 2.无向图的邻接表 对于无向图,vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此,将邻接表的表头向量称为顶点表。将无向图的 邻接表称为边表。
3、 【例】对于无向图G5,其邻接表表示如下面所示,其中顶点v0的边表上三个表结点中的顶点序号分别为1、2和3,它们分别表示关联于v0的三条边(v0,v1),(v0,v2)和(v0,v3)。 注意: n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。 3.有向图的邻接表 对于有向图,vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此,将有向图的邻接表称为出边表。 【例】有向图G6的邻接表表示如下面(a)图所示,其中顶点v1的邻接表上两个表结点中的顶点序号分别为0和4,它们分别表示从 v1射出的两条边(简称为v1的出边):和。 注意:
4、n个顶点e条边的有向图,它的邻接表表示中有n个顶点表结点和e个边表结点。 4.有向图的逆邻接表 在有向图中,为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。 入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。 【例】G6的逆邻表如上面(b)图所示,其中v0的人边表上两个表结点1和3分别表示射人v0的两条边(简称为v0的入边):
1,v0>和。 注意:n个顶点e条边的有向图,它的接表表示中有n个顶点表结点和e个边表结点。
此文档下载收益归作者所有