North China Electric Power University I 二邻接表存储方法 核心思想对具有n个顶点的图建立m个线性链表存储该图 1每一个链表前面设置一个头结点用来存放一个顶点的 数据信息称之为顶点结点其结构为 vertex link 其中, vertex域存放某个顶点的数据信息; ink坷存放某个链表中第一个结点的地址 n个头结点之间为一数组结构 2.第i个链表中的每一个链结点(称之为边结忘)表示以第i 个顶点为出发点的一条边边结点的构造为 adjvex weightnext 其中, next l为指针城 weight域为权值域(若图不带权,则无此城 adjvex域存放以第i个顶点为出发点的一条边 的另—端点在头结点数组中的位置 华电计算机系
North China Electric Power University 二.邻接表存储方法 核心思想:对具有n个顶点的图建立n个线性链表存储该图. 1. 每一个链表前面设置一个头结点,用来存放一个顶点的 数据信息,称之为顶点结点.其结构为: vertex link 其中,vertex 域存放某个顶点的数据信息; link 域存放某个链表中第一个结点的地址. 2. 第i 个链表中的每一个链结点(称之为边结点)表示以第i 个顶点为出发点的一条边;边结点的构造为 adjvex weight next 其中,next 域为指针域; weight 域为权值域(若图不带权,则无此域); adjvex 域存放以第i 个顶点为出发点的一条边 的另一端点在头结点数组中的位置. n个头结点之间为一数组结构. 华电计算机系
North China Electric Power University I 4 3 2 4∧ -23 2 6郾37人 3V 318 叠(1无向图的第个链表中边结点 营)的个数是个顶点度数 (2)有向图的第i个链表中边结点 的个数是第i个顶点的出度。 华电计算机系
North China Electric Power University 1 2 3 4 v1 v2 v3 v4 4 7 8 1 6 2 3 3 ^ ^ ^ ^ (1).无向图的第i 个链表中边结点 的个数是第i 个顶点度数. (2).有向图的第i 个链表中边结点 的个数是第i 个顶点的出度。 特 点 ^ ^ ^ ^ 1 2 3 4 v1 v3 v2 v4 2 3 3 4 3 2 1 4 1 4 1 2 华电计算机系 v1 v2 v3 v4 v1 v2 v3 v4 6 4 7 8
North China Electric Power University I 邻接表的类型定义 Type edgeptr=Tedgenode; edgenode=record navex:In; weight: real; next:edgeptr; end: vexnoderecord vertex: vertype, link: edgeptr; end: adj_ list=Arraylln of vexnode;
Type edgeptr=edgenode; edgenode=record adjvex:1..n; weight:real; next:edgeptr; end; vexnode=record vertex:vertype; link:edgeptr; end; adj_list=Array[1..n] of vexnode; 邻接表的类型定义 North China Electric Power University
North China Electric Power University I 关于逆邻接表 7 48 4 三有向图的十字链表存储方法 (略) 四无向图的多重邻接表存储方法 (略) 华电计算机系
North China Electric Power University 1 2 3 4 v1 v2 v3 v4 6 1 4 2 ^ ^ 2 7 4 8 ^ ^ 三.有向图的十字链表存储方法 (略) 四.无向图的多重邻接表存储方法 (略) 关于逆邻接表 华电计算机系 v1 v2 v3 v4 6 4 7 8