Question

图 - 图的存储结构 - 邻接表表示法（一）

Answer 1

　　图的邻接表表示法

　　图的邻接表表示法类似于树的孩子链表表示法 对于图G中的每个顶点v i 该方法把所有邻接于v i 的顶点v j 链成一个带头

　　结点的单链表 这个单链表就称为顶点v i 的邻接表(Adjacency List)

　　 邻接表的结点结构

　　( )表结点结构

　　┌────┬───┐

　　│adjvex │next │

　　└────┴───┘

　　邻接表中每个表结点均有两个域:

　　① 邻接点域adjvex

　　存放与vi相邻接的顶点v j 的序号j

　　② 链域next

　　将邻接表的所有表结点链在一起

　　注意

　　若要表示边上的信息(如权值) 则在表结点中还应增加一个数据域

　　( )头结点结构

　　┌────┬─────┐

　　│vertex │firstedge │

　　└────┴─────┘

　　顶点v i 邻接表的头结点包含两个域

　　① 顶点域vertex

　　存放顶点v i 的信息

　　② 指针域firstedge

　　v i 的邻接表的头指针

　　注意

　　① 为了便于随机访问任一顶点的邻接表 将所有头结点顺序存储在一个向量中就构成了图的邻接表表示

　　② 有时希望增加对图的顶点数及边数等属性的描述 可将邻接表和这些属性放在一起来描述图的存储结构

　　 无向图的邻接表

　　对于无向图 v i 的邻接表中每个表结点都对应于与v i 相关联的一条边 因此 将邻接表的表头向量称为顶点表 将无向图的

　　邻接表称为边表

　　【例】对于无向图G 其邻接表表示如下面所示 其中顶点v 的边表上三个表结点中的顶点序号分别为 和 它们分别表示

　　关联于v 的三条边(v v ) (v v )和(v v )

　　

　　注意

　　n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和 e个边表结点

　　 有向图的邻接表

　　对于有向图 v i 的邻接表中每个表结点都对应于以v i 为始点射出的一条边 因此 将有向图的邻接表称为出边表

　　【例】有向图G 的邻接表表示如下面(a)图所示 其中顶点v 的邻接表上两个表结点中的顶点序号分别为 和 它们分别表示从

　　v 射出的两条边(简称为v 的出边) 和

　　

　　注意

　　n个顶点e条边的有向图 它的邻接表表示中有n个顶点表结点和e个边表结点

　　 有向图的逆邻接表

　　在有向图中 为图中每个顶点v i 建立一个入边表的方法称逆邻接表表示法

　　入边表中的每个表结点均对应一条以v i 为终点(即射入v i )的边

　　【例】G 的逆邻表如上面(b)图所示 其中v 的人边表上两个表结点 和 分别表示射人v 的两条边(简称为v 的入边) <v p=""> </v>

　　1 ，v 0 >和 。Tw.wingWIt

　　注意：

　　n个顶点e条边的有向图，它的接表表示中有n个顶点表结点和e个边表结点。

lishixinzhi/Article/program/sjjg/201311/23847