732邻接表 当图中的边数较少时,相邻矩阵就会出现大量的零元素 ,存储这些零元素将耗费大量的存储空间。对于稀疏图 ,可以采用邻接表存储法。 邻接表( adjacency list表示法是一种链式存储结构,由 个顺序存储的顶点表和n个链接存储的边表组成 a顶点表目有两个域:顶点数据域和指向此顶点边表指针域 口边表把依附于同一个顶点ⅵ的边(即相邻矩阵中同一行的非0元 素)组织成一个单链表。边表中的每一个表目都代表一条边, 由两个主要的域组成 与顶点ⅵ邻接的另一顶点的序号 指向边表中下一个边表目的指针 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.3.2 邻接表 ◼ 当图中的边数较少时，相邻矩阵就会出现大量的零元素 ，存储这些零元素将耗费大量的存储空间。对于稀疏图 ，可以采用邻接表存储法。 ◼ 邻接表(adjacency list)表示法是一种链式存储结构，由一 个顺序存储的顶点表和n个链接存储的边表组成。 ❑ 顶点表目有两个域：顶点数据域和指向此顶点边表指针域 ❑ 边表把依附于同一个顶点vi的边（即相邻矩阵中同一行的非0元 素）组织成一个单链表。边表中的每一个表目都代表一条边， 由两个主要的域组成： • 与顶点vi邻接的另一顶点的序号 • 指向边表中下一个边表目的指针
732邻接表 顶点结点和边(或弧)结点的结构如下所示: 顶点结点 边(或弧)结点 data firestar ad]vex nextarc Info “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.3.2 邻接表 ◼ 顶点结点和边（或弧）结点的结构如下所示： data firstarc 顶点结点 adjvex nextarc 边（或弧）结点 Info
732邻接表 假设(v,v;)是无向图中的一条边,在顶点v的边表里存储有边(v v;)对应的边结点,在顶点v的边表里还需存放(v;,v)对应的 边结点。因此,对于无向图,同一条边在邻接表中出现两次。 O 0 Vo V2 23001 (a)无向图G1 b)有向图G2 V2 2 图712无向图G1的邻接表表示 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 v0 v2 v3 v1 v4 v0 v2 v1 v3 (a) 无向图G1 (b) 有向图G2 7.3.2 邻接表 假设（vi，vj）是无向图中的一条边，在顶点vi的边表里存储有边（vi ，vj）对应的边结点，在顶点vj的边表里还需存放（vj，vi）对应的 边结点。因此，对于无向图，同一条边在邻接表中出现两次。 图7.12 无向图G1的邻接表表示 V0 V2 V1 V3 V4 0 1 2 3 4 2 3 \ 3 4 \ 0 3 4 \ 0 1 2 \ 1 2 \
732邻接表 (a)无向图G1 (b)有向图G2 1“20V 1V1 ∧ V 3002 (a)有向图G2的邻接表 (b)有向图G2的逆邻接表 图713有向图G2的邻接表和逆邻接表表示 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.3.2 邻接表 V0 V2 V1 ∧ V3 0 1 2 3 1 2 \ 3 \ 0 \ （a）有向图G2的邻接表 V0 V2 V1 V3 0 1 2 3 3 \ 0 \ 0 \ 2 \ （b）有向图G2的逆邻接表 图7.13 有向图G2的邻接表和逆邻接表表示 v0 v2 v3 v1 v4 v0 v2 v1 v3 (a) 无向图G1 (b) 有向图G2
732邻接表 15 0 Vo 334 315 2|4 36 3V3 015→1「9一“26 图714带权图G4的邻接表表示 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.3.2 邻接表 V0 V2 V1 V3 0 1 2 3 1 3 0 3 1 4 0 15 3 15 \ 2 4 3 6 \ 1 9 3 9 \ 2 6 \ 图7.14 带权图G4的邻接表表示 v0 v1 v2 v3 3 4 15 6 9