Datastrucstures And Algorithms:Graphs 图的存储表示 1、邻接矩阵和加权邻接矩阵(labeled adjacency matrix) (续) 无权值的无向图的邻接矩阵 设无向图具有n个结点，则用n行n列的布尔矩阵A表示该无向图； 并且A[,]=1,如果1至j有一条无向边；A[,]=0如果1至j没有一条无向边 注意：A[,门=0。结点的度：i行或列之和。上三角矩阵或下三角矩阵。 0 表示成右图矩阵 10 0 0 0 0 0 1 11 •在物理实现时的考虑，和前一页的无向图类似。 11 ALDS
11 物料管理 ALDS 11 DataStrucstures And Algorithms:Graphs 图的存储表示 1、邻接矩阵和加权邻接矩阵（labeled adjacency matrix）（续） •无权值的无向图的邻接矩阵 设无向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该无向图； 并且 A[i,j] = 1 , 如果i 至 j 有一条无向边；A[i,j] = 0如果 i 至 j 没有一条无向边 注意： A[i,i] = 0。i结点的度: i行或i列之和。上三角矩阵或下三角矩阵。 表示成右图矩阵 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 1 1 0 A B C D E •在物理实现时的考虑，和前一页的无向图类似
Datastrucstures And Algorithms:Graphs 图的存储表示 1、邻接矩阵和加权邻接矩阵(labeled adjacency matrix) (续) ·有向图的加权邻接矩阵 设有向图具有n个结点，则用n行n列的矩阵A表示该有向图； 并且A[,j]=a,如果i至j有一条有向边且它的权值为a。A[,j]=‘空或其它 标 志；如果至j没有一条有向边。 a b b 表示成右图矩阵 a b b a 优点：判断任意两点之间是否有边方便，仅耗费O()时间。 缺点：即使<<n2条边，也需内存n2单元，太多；仅读入数据耗费 0(n2) 时间，太长。 邻接 矩阵 •在物理实现时的考虑，和前一页的无向图类似。 12 ADT ALDS
12 物料管理 ALDS 12 DataStrucstures And Algorithms:Graphs 图的存储表示 1、邻接矩阵和加权邻接矩阵（labeled adjacency matrix）（续） •有向图的加权邻接矩阵 设有向图具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该有向图； 并且 A[i,j] = a , 如果i 至 j 有一条有向边且它的权值为a。A[i,j] = ‘ 空 或其它 标 志；如果 i 至 j 没有一条有向边。 A B C D 表示成右图矩阵 a b b b a a a a b a b b 优点：判断任意两点之间是否有边方便，仅耗费 O(1) 时间。 缺点：即使 << n2 条边，也需内存 n2 单元，太多; 仅读入数据耗费 O( n2 ) 时间，太长。 •在物理实现时的考虑，和前一页的无向图类似。 邻接 矩阵 ADT
Datastrucstures And Algorithms:Graphs 图的存储表示 2、邻接表(adjacency list) ·设有向图或无向图具有个结点，则用结点表、边表表示该有向图或无向图。 ·结点表：用数组或单链表的形式存放所有的结点。如果结点数已知，则采用数 组形式，否则应采用单链表的形式。！提倡采用动态链表形式。 ·边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成 它的边结点单链表。 ·优点：内存=结点数+边数 ·缺点：确定i->j是否有边，最坏需耗费O()时间。无向图同一条边表示两次 边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。 结点表中的结点的表示： ·用数组 data:结点的数据场，保存结点的数据值。 data adj adj:结点的指针场，给出自该结点出发的 的第一条边的边结点的地址。 13 ALDS
13 物料管理 ALDS 13 DataStrucstures And Algorithms:Graphs 图的存储表示 2、邻接表（adjacency list） • 设有向图或无向图具有 n 个结点，则用 结点表、边表表示该有向图或无向图。 • 结点表：用数组或单链表的形式存放所有的结点。如果结点数n已知，则采用数 组形式，否则应采用单链表的形式。!!! 提倡采用动态链表形式。 • 边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成 它的边结点单链表。 • 优点：内存 ＝ 结点数 ＋ 边数 • 缺点：确定 i --> j 是否有边，最坏需耗费 O(n) 时间。无向图同一条边表示两次 边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。 data adj 结点表中的结点的表示： • 用数组 data:结点的数据场，保存结点的数据值。 adj: 结点的指针场，给出自该结点出发的 的第一条边的边结点的地址
Datastrucstures And Algorithms:Graphs 图的存储表示 2、邻接表(adjacency list) data:结点的数据场，保存结点的 结点表中的结点的表示：续 数据值。 ·用单链表 firstarc:结点的指针场，给出自该 结点出发的的第一条边的 data adj nextvex 边结点的地址。 nextvex:结点的指针场，给出该结 点的下一结点的地址。 边结点表中的结点的表示： cost:边结点的数据场，保存边的 权值等。 dest:边结点的指针场，给出本 cost dest link 条边依附的另一结点（非 出发结点)的地址。 link: 结点的指针场，给出自该 结点出发的的下一条边的 边结点的地址。14 ALDS
14 物料管理 ALDS 14 DataStrucstures And Algorithms:Graphs 图的存储表示 2、邻接表（adjacency list） data adj 结点表中的结点的表示：续 • 用单链表 data:结点的数据场，保存结点的 数据值。 firstarc:结点的指针场，给出自该 结点出发的的第一条边的 边结点的地址。 nextvex:结点的指针场，给出该结 点的下一结点的地址。 nextvex cost dest link 边结点表中的结点的表示： cost:边结点的数据场，保存边的 权值等。 dest:边结点的指针场，给出本 条边依附的另一结点（非 出发结点）的地址。 link: 结点的指针场，给出自该 结点出发的的下一条边的 边结点的地址
Datastrucstures And Algorithms:Graphs 图的存储表示 2、邻接表 (adjacency list) 实例： data adj dest link 向图G1 0 A null A B 1 B null 寻找进入结点的边非常困难！ 23 null null 改进：建立逆邻接表或十字链表 D dest指针场之值为相应结点 数的组元素的下标！ 无向图G2 A data adi 0 2 null dest link 1 4 null 2 null 3 D null 4 E 3 null 六条边却用了12个边结点！ 15 改进：建立邻接多重表 ALDS
15 物料管理 ALDS 15 DataStrucstures And Algorithms:Graphs 图的存储表示 2、邻接表（adjacency list） •实例： A B C D 无向图 G2 A B C D E 向图 G1 A B C D 1 2 1 3 0 1 2 3 null null null null data adj dest link A B 1 2 0 1 2 3 4 null data adj 0 3 0 4 1 4 2 3 C D E 4 1 null null null null dest 指针场之值为相应结点 数的组元素的下标!!! 六条边却用了 12 个边结点!!! 改进：建立邻接多重表 寻找进入结点的边非常困难!!! 改进：建立逆邻接表或十字链表 dest link