Algorithms and Datastrucstures: Graphs 图的存储结构 2、邻接表( adjacency list) 设有向图或无向图具有n个结点,则用结点表、边表表示该有向图或无向图。 ·结点表:用数组或单链表的形式存放所有的结点。如果结点数n已知,则采用数 组形式,否则采用单链表的形式更好。 边表(边结点表):每条边用一个结点进行表示。同一个结点的所有的边形成 它的边结点单链表。 优点:内存=结点数+边数 缺点:确定ⅰ->j是否有边,最坏需耗费o(n)时间。无向图同一条边表示两次 边表空间浪费一倍。有向图中寻找进入某结点的边,非常困难。 结点表中的结点的表示: ·用数组 data:结点的数据场,保存结点的数据值。 data firstarc firstarc:结点的指针场,给出自该结点出发的 的第一条边的边结点的地址。 ALDS
11 物料管理 ALDS 11 Algorithms and DataStrucstures:Graphs 图的存储结构 2、邻接表（adjacency list） • 设有向图或无向图具有 n 个结点，则用 结点表、边表表示该有向图或无向图。 • 结点表：用数组或单链表的形式存放所有的结点。如果结点数n已知，则采用数 组形式，否则采用单链表的形式更好。 • 边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成 它的边结点单链表。 • 优点：内存 ＝ 结点数 ＋ 边数 • 缺点：确定 i --> j 是否有边，最坏需耗费 O(n) 时间。无向图同一条边表示两次 边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。 data firstarc 结点表中的结点的表示： • 用数组 data:结点的数据场，保存结点的数据值。 firstarc:结点的指针场，给出自该结点出发的 的第一条边的边结点的地址
Algorithms and Datastrucstures Graphs 图的存储结构 2、邻接表( adjacency list) data:结点的数据场,保存结点的 结点表中的结点的表示:续 数据值。 用单链表 firstarc:结点的指针场,给出自该 结点出发的的第一条边的 data firestar nextvex 边结点的地址。 nextvex:结点的指针场,给出该结 点的下一结点的地址。 边结点表中的结点的表示: info:边结点的数据场,保存边的 权值等。 adjvex:边结点的指针场,给出本 InTo adivex nextarc 条边依附的另一结点(非 出发结点)的地址。 nextarc:结点的指针场,给出自该 结点出发的的下一条边的 边结点的地址 12 ALDS
12 物料管理 ALDS 12 Algorithms and DataStrucstures:Graphs 图的存储结构 2、邻接表（adjacency list） data firstarc 结点表中的结点的表示：续 • 用单链表 data:结点的数据场，保存结点的 数据值。 firstarc:结点的指针场，给出自该 结点出发的的第一条边的 边结点的地址。 nextvex:结点的指针场，给出该结 点的下一结点的地址。 nextvex info adjvex nextarc 边结点表中的结点的表示： info:边结点的数据场，保存边的 权值等。 adjvex:边结点的指针场，给出本 条边依附的另一结点（非 出发结点）的地址。 nextarc:结点的指针场，给出自该 结点出发的的下一条边的 边结点的地址
Algorithms and Datastrucstures: Graphs 图的存储结构 2、邻接表( adjacency list) 实例: data firstarc adjvex nextvex 向图G1 2|B 寻找进入结点的边非常困难!! 4|b 亻「凡改进:建立逆邻接表或十字链表 Adjvex指针场之值为相应结点 数的组元素的下标!! 无向图G2 data firstarc adivex nextvex B 4 5 5 5 5E D 六条边却用了12个边结点!! 13 改进:建立邻接多重表 ALDS
13 物料管理 ALDS 13 Algorithms and DataStrucstures:Graphs 图的存储结构 2、邻接表（adjacency list） •实例： A B C D 无向图 G2 A B C D E 向图 G1 A B C D 2 3 1 4 1 2 3 4 null null null null data firstarc adjvex nextvex A B 2 3 1 2 3 4 5 null data firstarc 1 4 1 5 2 5 2 3 C D E 5 4 null null null null Adjvex 指针场之值为相应结点 数的组元素的下标!!! 六条边却用了 12 个边结点!!! 改进：建立邻接多重表 寻找进入结点的边非常困难!!! 改进：建立逆邻接表或十字链表 adjvex nextvex
Algorithms and Datastrucstures: Graphs 图的存储结构 2、邻接表( adjacency list) 逆邻接表实例: 有向图G 3 null] 2[B null 3 ALDS
14 物料管理 ALDS 14 Algorithms and DataStrucstures:Graphs 图的存储结构 2、邻接表（adjacency list） •逆邻接表实例： A B C D 有向图 G1 A B 4 3 1 2 3 4 null 1 1 3 C D null null null
Algorithms and Datastrucstures: Graphs 图的存储结构 3、十字链表 data:结点的数据场,保存结点的 结点表中的结点的表示: 数据值 firstin:结点的指针场,给出自该 结点出发的的第一条边的 边结点的地址 data firstin firstout firstout:结点的指针场,给出进入该 结点的第一条边的边结点的地 址 边结点表中的结点的表示: info:边结点的数据场,保存边的 info tailvex headvex hlink tlink 权值等。 tailvex:本条边的出发结点 hlink:终止结点相同的边 的地址。 中的下一条边的地址 headvex:本条边的终止结点tnk:出发结点相同的边 的地址。 中的下一条边的地址。 15 ALDS
15 物料管理 ALDS 15 Algorithms and DataStrucstures:Graphs 图的存储结构 3、十字链表 data firstin firstout info tailvex headvex •边结点表中的结点的表示： •结点表中的结点的表示： data:结点的数据场，保存结点的 数据值。 firstin: 结点的指针场，给出自该 结点出发的的第一条边的 边结点的地址。 firstout:结点的指针场，给出进入该 结点的第一条边的 边结点的地 址。 info:边结点的数据场，保存边的 权值等。 hlink tlink tailvex: 本条边的出发结点 的地址。 headvex:本条边的终止结点 的地址。 hlink:终止结点相同的边 中的下一条边的地址。 tlink:出发结点相同的边 中的下一条边的地址