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 图的邻接矩阵存储法与邻接表存储法特点比较

　　总的来说，邻接矩阵适用于稠密图中，而邻接表适用于稀疏图中。