5.3 图的存储及基本操作★3◎2
5.3 图的存储及基本操作★3◎2
相对于其他的线性数据结构,图的存储要复杂很多,因为顶点数相同的图,其边(或弧)的数量相差很大。比如一个有n个顶点e条边的图,若是以顶点为结点来存储,由于各个顶点的度数不一致,无法指定结点的指针域中需要的指针数。虽然可以定义结点的指针域存在n-1个指针,但这样存储过于复杂,存储密度过小;若以边为结点来存储,又不便于顶点遍历。所以一般情况下,图需要同时存储顶点和边的信息。
1.邻接矩阵法
邻接矩阵法又称数组表示法,是存储图的最简单方法,它的基本思想是用一个n×n的邻接矩阵表示图中的边或弧的信息,用一个n维向量来存储n个顶点的信息,其中针对“图”和“网”, 邻接矩阵有不同的解释。
(1)图的邻接矩阵
设G=(V,E)是具有n个顶点的图,其中,V是其顶点的集合,E是其边的集合,那么邻接矩阵中的每一个元素的含义定义如下:
即如果顶点vi和vj之间存在一条边或弧,定义A[i,j]为1,否则定义为0。
比如图5-1(a)中的有向图和图5-1(b)中的无向图的邻接矩阵分别如图5-2中矩阵A1和矩阵A2所示。
无向图的邻接矩阵是一个对称矩阵。
图的邻接矩阵可以很方便地应用于以下两个方面:
① 判断任意两个顶点之间是否有边相连接。
当A[i,j]取值为1时,顶点Vi和顶点Vj存在边或弧直接连接。
当A[i,j]取值为0时,顶点Vi和顶点Vj不存在边或弧直接连接。
② 获取顶点的度、入度或出度
在无向图的邻接矩阵中,第i行或第i列上的所有非0元素的个数就是顶点Vi的度。比如图5-2(b)中:
TD(V1)=3;TD(V2)=2;TD(V3)=1;TD(V4)=2。
在有向图的邻接矩阵中,第i行上的所有非0元素的个数就是顶点Vi的出度,第i列上的所有非0元素的个数就是顶点Vi的入度,两者之和就是顶点Vi的度。比如图5-2(a)中:
OD(V1)=3;ID(V1)=1;TD(V1)=4;
OD(V2)=1;ID(V2)=1;TD(V2)=2;
OD(V3)=0;ID(V3)=1;TD(V3)=1;
OD(V4)=1;ID(V4)=2;TD(V4)=3;
(2)网的邻接矩阵
网与图的区别是网的每条路径之间都带有权值,因此网的邻接矩阵当中必须能够存储此权值,定义网的邻接矩阵如下:
其中:① 边(vi,vj)或弧<vi,vj>上的权值;② ∞表示无穷大,在计算机中常常用一个大于所有边的权值的数来代替。
即如果顶点vi和vj之间存在一条边或弧,定义A[i,j]此边或弧的权值,否则定义为无穷大。
例如图5-3中(a)和(c)分别为有向网和无向网,(b)和(d)分别是其对应的邻接矩阵。
(3)邻接矩阵的存储结构表示
如下定义了一个邻接矩阵描述图的例子:
图的邻接矩阵存储法的空间复杂度为,n为图的顶点数。
2.邻接表法
邻接表是图的链式存储结构,对于图G中的每个顶点vi,邻接表法把所有邻接于vi的顶点vj链成一个带头结点的单链表,这个单链表就是顶点vi的邻接表,其头结点描述了顶点vi信息,其余结点描述了与顶点vi相连的边或弧的信息。
(1)邻接表的表结点结构
邻接表中的每个结点代表了一条边或弧,它由三个域组成,分别为:
① 邻接点域adjvex
存放与vi相邻接的顶点vj的序号j。
② 边弧相关域info
存放与边(vi,vj)或弧<vi,vj>相关的信息,比如权值等。
③ 指针域next
指向单链表中下一结点的位置,也就是存储下一条边或弧的结点位置。
(2)头结点结构
邻接表的头结点描述了顶点vi的信息,它由两个域组成,分别是:
① 顶点域data
存放顶点vi及其相关的信息。
② 指针域first
记载vi的邻接表的第一个结点的指针。
邻接表的存储结构示意如图5-4所示。
为了便于随机访问任一顶点的邻接表,一般情况需要将所有头结点顺序存储在一个向量中。
(3)无向图的邻接表
图5-3(b)的无向图邻接表如图5-5所示,其中顶点信息用其向量下标来描述,本图中增加了权值信息,如果不需要存储权值,可以不使用info域。
(4)有向图的邻接表
有向图的邻接表中存储以vi为弧尾的弧信息,图5-3(a)的有向图邻接表如图5-6所示。
(5)有向图的逆邻接表
有向图的邻接表中存储以vi为弧尾的弧信息,现定义有向图的逆邻接表为:存储每条以vi为弧头的弧信息,那么图5-3(a)的有向图的逆邻接表如图5-7所示。
(6)邻接表的存储结构表示
如下定义了一个邻接表描述图的例子:
图的邻接表存储法的空间复杂度为O(n+e),其中n为图的顶点数,e为图的边数。
3.图的两种存储结构比较
邻接矩阵和邻接表是图的两种最常用的存储结构,它们各有特点,其比较如表5-2所示,其中n是图的顶点数,e是图的边数(或弧数)。
表5-2 图的邻接矩阵存储法与邻接表存储法特点比较
邻接矩阵 |
邻 接 表 |
|
存储方式 | 顺序存储 | 链式存储 |
描述方式 | 唯一 | 不唯一,各顶点邻接表中的结点次序可以交换 |
空间复杂度 | O(n2) | O(n+e) |
附加信息 | 存储了不存在的边的信息 | 在每个表结点和头结点中附加指针域 |
求无向图顶点Vi度的算法及其时间复杂度 | 算法:统计第i行或第i列上的所有非0元素的个数 时间复杂度:O(n) |
算法:统计顶点Vi邻接表中的结点数,与图的顶点数无关 最坏时间复杂度:O(e) 最好时间复杂度:O(1) |
求有向图顶点Vi出度的算法及其时间复杂度 | 算法:统计第i行上的所有非0元素的个数 时间复杂度:O(n) |
算法:统计顶点Vi邻接表中的结点数,与图的顶点数无关 最坏时间复杂度:O(e) 最好时间复杂度:O(1) |
求有向图顶点Vi入度的算法及其时间复杂度 | 算法:统计第i列上的所有非0元素的个数 时间复杂度:O(n) |
算法1:统计顶点Vi逆邻接表中的结点数,与图的顶点数无关 最坏时间复杂度:O(e) 最好时间复杂度:O(1) 算法2:遍历弧,统计全部顶点邻接表中指向顶点Vi的结点 时间复杂度:O(n+e) |
求边的数目的算法及其时间复杂度 | 遍历整个矩阵,无向图为所有非0元素的个数的一半,有向图为所有非0元素的个数 时间复杂度O(n2) |
遍历所有顶点的邻接表 时间复杂度:O(n+e) |
判断顶点Vi和Vj之间是否存在边或弧 | 判断矩阵元素A[i,j]的取值,非0(图)或非∞(网)则表示边或弧存在 时间复杂度O(1) |
遍历顶点Vi的邻接表,无向图需要再遍历顶点Vj的邻接表 最坏时间复杂度:O(e) 最好时间复杂度:O(1) |
总的来说,邻接矩阵适用于稠密图中,而邻接表适用于稀疏图中。
5.3 图的存储及基本操作★3◎2未经允许不得转载:5.3 图的存储及基本操作★3◎2