图的存储结构
第2讲图的存储结构——教学讲义
本讲介绍4种较常用的存储表示法：①邻接矩阵表示法；②邻接表；③邻接多重表；④十字链表。由于每种方法各有利弊，因此可以根据实际应用问题来选择合适的存储表示方法。
①邻接矩阵表示法
图的邻接矩阵表示法（Adjacency Matrix）也称作数组表示法。它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组，这个关联关系数组被称为邻接矩阵。
若G是一具有n个顶点的无权图，G的邻接矩阵是具有如下性质的n×n矩阵A：
上图所示G1和G2的邻接矩阵如下所示。
若图G是一个有n个顶点的网，则它的邻接矩阵是具有如下性质的n×n矩阵A
A1=
图G1,G2的邻接矩阵
(a) G1是有向图(b) G2是无向图
例如：下图就是一个有向网及其邻接矩阵的示例。
邻接矩阵表示法的C 语言描述如下：
#define MAX_VERTEX_NUM 20 /*最多顶点个数*/
#define INFINITY 32768 /*表示极大值，即∞*/
/* 图的种类：DG 表示有向图, DN 表示有向网, UDG 表示无向图, UDN 表示无向网 */
typedef enum{DG, DN, UDG, UDN} GraphKind;
typedef char VertexData; /*假设顶点数据为字符型*/ typedef struct ArcNode{
AdjType adj; /* 对于无权图，用1或0表示是否相邻；
对带权图，则为权值类型 */
OtherInfo info; } ArcNode;
typedef struct{
VertexData vertex[MAX_VERTEX_NUM]; /*顶点向量*/
ArcNode arcs [MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /*邻接矩阵*/ int vexnum, arcnum; /*图的顶点数和弧数*/ GraphKind kind; /*图的种类标志*/ } AdjMatrix; /*（Adjacency Matrix Graph ）*/
邻接矩阵法的特点如下：
● 存储空间: 对于无向图而言，它的邻接矩阵是对称矩阵（因为若（v i ，v j ）
∈E （G ），则（v j ，v i ）∈E （G ）），因此可以采用特殊矩阵的压缩存储法，即只存储其下三角即可，这样，一个具有n 个顶点的无向图G ，它的邻接矩阵需要n （n -1）/2个存储空间即可。但对于有向图而言 ，其中的弧是有方向的，即若
● 便于运算: 采用邻接矩阵表示法，便于判定图中任意两个顶点之间是否
有边相连，即根据A[i ，j]=0或1来判断。另外还便于求得各个顶点的度。对于无向图而言，其邻接矩阵第i 行元素之和就是图中第i 个顶点的度：
(a)有向网N 有向网及其邻接矩阵
TD （v i ）=∑=n
j j i A 1
],[
对于有向图而言，其邻接矩阵第i 行元素之和就是图中第i 个顶点的出度：
OD （i v ）=∑=n
j j i A 1],[
对于有向图而言，其邻接矩阵第i 列元素之和就是图中第i 个顶点的入度：
ID （i v ）=∑=n
j i j A 1],[
采用邻接矩阵存储法表示图，很便于实现图的一些基本操作，如实现访问图G 中V 顶点第一个邻接点的函数FirstAdjVertex （G,v ）可按如下步骤实现：
FirstAdjVertex （G ，v ）：
⑴ 首先，由LocateVertex （G ，v ）找到v 在图中的位置，即v 在一维数组vertex 中的序号i 。
⑵ 二维数组arcs 中第i 行上第一个adj 域非零的分量所在的列号j ，便是v 的第一个邻接点在图G 中的位置。 ⑶ 取出一维数组vertex[j]中的数据信息，即与顶点v 邻接的第一个邻接点的信息。
对于稀疏图而言，不适于用邻接矩阵来存储，因为这样会造成存储空间的浪费。
用邻接矩阵法创建有向网的算法如下： 【算法描述】
int LocateVertex(AdjMatrix * G, VertexData v) /*求顶点位置函数*/ { int j=Error,k;
for(k=0;k
int CreateDN(AdjMatrix *G) /*创建一个有向网*/ { int i,j,k,weight; VertexData v1,v2;
scanf("%d,%d",&G->arcnum,&G->vexnum); /*输入图的顶点数和弧数*/ for(i=0;i
scanf("%c",&G->vertex[i]); /* 输入图的顶点*/ for(k=0;k
{ scanf("%c,%c,%d",&v1,&v2,&weight);/*输入一条弧的两个顶点及权值*/
i=LocateVex_M(G,v1); j=LocateVex_M(G,v2);
G->arcs[i][j].adj=weight; /*建立弧*/
}
return(Ok); }
该算法的时间复杂度为O （n 2+e ×n ），其中O （n 2）时间耗费在对二维数组arcs 的每个分量的arj 域初始化赋值上。O （e ×n ）的时间耗费在有向网中边权的赋值上。 ②邻接表表示法
图的邻接矩阵表示法（即图的数组表示法）虽然有其自身的优点，但对于稀疏图来讲，用邻接矩阵的表示方法会造成存储空间的很大浪费。邻接表（Adjacency List ）表示法实际上是图的一种链式存储结构。它克服了邻接矩阵的弊病，基本思想是只存有关联的信息，对于图中存在的边信息则存储，而不相邻接的顶点则不保留信息。在邻接表中，对图中的每个顶点建立一个带头结点的边链表，如第i 个单链表中的结点则表示依附于顶点v i 的边（若是有向图，则表示以v i 为弧尾的弧）。每个边链表的头结点又构成一个表头结点表。这样，一个n 个顶点的图的邻接表表示由表头结点表与边表两部分构成：
（1） 表头结点表。由所有表头结点以顺序结构（向量）的形式存储，以
便可以随机访问任一顶点的边链表。表头结点的结构如下图（a ）所示。表头结点由两部分构成，其中数据域（vexdata ）用于存储顶点的名或其它有关信息；链域（firstarc ）用于指向链表中第一个顶点（即与顶点vi 邻接的第一个邻接点）。
（2） 边表：由表示图中顶点间邻接关系的n 个边链表组成。边链表中结
点的结构如下图（b ）所示，它由三部分组成，其中邻接点域（adjvex ）用于存放与顶点v i 相邻接的顶点在图中的位置；链域（nextarc ）用于指向与顶点vi 相关联的下一条边或弧的结点；数据域（info ）用于存放与边或弧相关的信息（如赋权图中每条边或弧的权值等）。
如下图所示分别是图G1、G2邻接表表示示例，其中边表中顶点无顺序要求。
（a）G1的邻接表表示法
（b）G2的邻接表表示法
邻接表存储结构的形式化说明如下：
#define MAX_VERTEX_NUM 20 /*最多顶点个数*/
typedef enum{DG, DN, UDG, UDN} GraphKind; /*图的种类*/
typedef struct ArcNode{
int adjvex; /*该弧指向顶点的位置*/
struct ArcNode *nextarc; /*指向下一条弧的指针*/
OtherInfo info; /*与该弧相关的信息*/
} ArcNode;
typedef struct VertexNode{
VertexData data; /*顶点数据*/
ArcNode *firstarc; /*指向该顶点第一条弧的指针*/
} VertexNode;
typedef struct{
VertexNode vertex[MAX_VERTEX_NUM];
int vexnum,arcnum; /*图的顶点数和弧数*/ GraphKind kind; /*图的种类标志*/
}AdjList; /*基于邻接表的图(Adjacency List Graph)*/
■存储空间
对于有n个顶点，e条边的无向图而言，若采取邻接表作为存储结构，则需要n个表头结点和2e个表结点。很显然在边很稀疏（即e远小于n(n-1)/2时）的情况下，用邻接表存储所需的空间要比邻接矩阵所需的n(n-1)/2要节省得多。
■无向图的度
在无向图的邻接表中，顶点v i的度恰好就是第i个单链表上结点的个数。
■有向图的度
在有向图中，第i个单链表上结点的个数只是顶点v i的出度，只需通过表头向量表中找到第i个顶点的边链表的头指针，实现顺链查找即可。
如果要判定任意两个顶点(vi和vj)之间是否有边或弧相连，则需要搜索所有
的边链表，这样比较麻烦。
要求第i 个顶点的入度，必须遍历整个邻接表。在所有边链表中查找邻接点域的值为i 的结点并计数求和。由此可见，对于用邻接表方式存储的有向图，求顶点的入度并不方便，它需要扫描整个邻接表才能得到结果。
一种解决的方法是逆邻接表法，我们可以对每一顶点v i 再建立一个逆邻接表，即对每个顶点v i 建立一个所有以顶点v i 为弧头的弧的表，有向图G1的逆邻接表如下图所示。这样求顶点v i 的入度即是计算逆邻接表中第i 个顶点的边链表中结点个数。
实质上这需要将图中的一条弧分别在邻接表与逆邻接表各自的边链表中存储，下面介绍十字链表法，此方法优点是一条弧只被存放一次。 ③ 十字链表
十字链表(Orthogonal List)是有向图的另一种链式存储结构。可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。这两类结点结构如下图所示。
1 2 3 4
图G1的逆邻接表表示法
图的十字链表弧结点、顶点结点结构图
例如：有向图G1的十字链表表示如下图所示。若有向图是稀疏图，则它的邻接矩阵一定是稀疏矩阵，这时该图的十字链表表示法可以看成是其邻接矩阵的链表表示法。只是在图的十字链表表示法中，弧结点所在的链表不是循环链表且结点之间相对位置自然形成，不一定按顶点序号有序。另外，表头结点即顶点结点，它们之间并非循环链式连接，而是顺序存储。
图的十字链表结构形式化定义如下：
#define MAX_VERTEX_NUM 20 /*最多顶点个数*/
typedef enum{DG, DN, UDG, UDN} GraphKind; /*图的种类*/
typedef struct ArcNode {
int tailvex, headvex;
struct ArcNode *hlink, *tlink;
} ArcNode;
typedef struct VertexNode{
VertexData data; /*顶点信息*/
ArcNode *firstin, *firstout;
}VertexNode;
typedef struct{
VertexNode vertex[MAX_VERTEX_NUM];
int vexnum, arcnum; /*图的顶点数和弧数*/ GraphKind kind; /*图的种类*/
} OrthList; /*图的十字链表表示法(Orthogonal List)*/
下面给出建立一个有向图的十字链表的算法： 【算法描述】
void CrtOrthList （OrthList *g ）
/*从终端输入n 个顶点的信息和e 条弧的信息，以建立一个有向图的十字链表*/ {
scanf(“%d,%d”,&n,&e); /*从键盘输入图的顶点个数和弧的个数*/ g->vexnum = n; g->arcnum = e; for (i=0;i { scanf(“%c”,&(g->vertex[i].data)); g->vertex[i] .firstin=NULL; g->vertex[i] .firsout=NULL; } for (k=0;k { scanf(“%c,%c”,&vt,&vh); i=LocateVertex （g ，vt ）; j = LocateVertex （g ，vh ）; p=( ArcNode*)malloc(sizeof(ArcNode)); p->tailvex=I; p->headvex=j; p->tlink = g->vertex[i].firstout; g->vertex[i].firstout =p; p->hlink = g->vertex[j].firstin; g->vertex[j].firstin =p; 1 2 3 4 有向图G1的十字链表 } } /* CrtOrthList */ 在十字链表中既能够很容易地找到以v i为尾的弧，也能够容易地找到以v i 为头的弧，因此对于有向图，若采用十字链表作为存储结构，则很容易求出顶点v i的度。此外，为有向图建立一个邻接表的算法和建立一个十字链表的算法的时间复杂度是相同的。所以，在某些有向图的应用中，十字链表表示法更为合适。 ④邻接多重表 邻接多重表(Adjacency Multi_list)是无向图的另外一种存储结构，之所以提出邻接多重表这种存储结构是因为它能够提供更为方便的边处理信息。在无向图的邻接表表示法中，每一条边（v i，v j）在邻接表中都对应着两个结点，它们分别在第i个边链表i和第j个边链表中。这给图的某些边操作带来不便，如检测某条边是否被访问过，则需要同时找到表示该条边的两个结点，而这两个结点又分别在两个边链表中。邻接多重表是指将图中关于一条边的信息用一个结点来表示，其结点结构如下图（a）所示，图中的每一个顶点也对应一个顶点结点，其结构如下图（b）所示。 （a）邻接多重表中边结点的结构 （b）邻接多重表中顶点结点的结构 邻接多重表的结点结构 邻接多重表的结构类型说明如下： #define MAX_VERTEX_NUM 20 /*最多顶点个数*/ typedef struct EdgeNode { int mark,ivex,jvex; struct EdgeNode *ilink, *jlink; }EdgeNode; typedef struct { VertexData data; EdgeNode *firstedge; }VertexNode; typedef struct{ VertexNode vertex[MAX_VERTEX_NUM]; Int vexnum, arcnum; /*图的顶点数和弧数*/ GraphKind kind; /*图的种类*/ } AdjMultiList; /*基于图的邻接多重表表示法(Adjacency Multi_list)*/ 无向图G2的邻接多重表如下图所示。 无向图的邻接多重表表示