邻接表和逆邻接表的教程

《邻接表和逆邻接表的教程》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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个边表结点。