有向图的数组存储主要有以下特性:
(1)顶点数组长度为图的顶点数目n。边数组为n X n的二维数组。(2)边数组中,数组元素为1,即A[i][j] = 1,代表第i个顶点与第j个顶点邻接,且i为尾,j为头。 A[i][j] = 0代表顶点与顶点不邻接。(3)在有向图中,由于边存在方向性,因此数组不一定为对称数组。(4)对角线上元素为0。(5)第i行中,1的数目代表第i个顶点的出度。例如:顶点V1的出度为2,则顶点V1所在行的1的数目为2。(6)第j列中,1的数目代表第j个顶点的入度。例如:V3的入度为1,则V3所在列中1的数目为1。
数组存储方式优点:
数组存储方式容易实现图的操作。例如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。
数组存储方式缺点:
采用数组存储方式,图若有n个顶点则需要n2个单元存储边(弧),空间存储效率为O(n2)。 当顶点数目较多,边数目较少时,此时图为稀疏图,这时尤其浪费空间。
例如:图5.3所示的图,图中有 9 个顶点,边数为10,需要 9X9 的二维数组,而实际存储边信息空间只有10,造成空间浪费。
图5.3所示无向图的存储数组:
6 邻接表
当使用数组存储时,主要有以下三个问题:
(1)对于一个图,若图中的顶点数目过大,则无法使用邻接矩阵进行存储。因为在分配数组内存时可能会导致内存分配失败。(2)对于某些稀疏图(即顶点数目多,边数目少),创建的数组大小很大,而真正存储的有用信息又很少,这就造成了空间上的浪费。 (3)有时两个点之间不止存在有一条边,这是用邻接矩阵就无法同时表示两条以上的边。
针对以上情况,提出了一种特殊的图存储方式,让每个节点拥有的数组大小刚好就等于它所连接的边数,由此建立一种邻接表的存储方式。
邻接表存储方法是一种数组存储和链式存储相结合的存储方法。在邻接表中,对图中的每个顶点建立一个单链表,第 i 个单链表中的结点依附于顶点 Vi 的边(对有向图是以顶点Vi为尾的弧)。链表中的节点称为表节点,共有 3个域,具体结构见下图:
除表节点外,需要在数组中存储头节点,头结点由两个域组成,分别指向链表中第一个顶点和存储Vi的名或其他信息。具体结构如下图: