6.2 图的存储结构
6.2 图的存储结构
在图中，由于任意顶点之间都可能存在联系，所以图的结构比较复杂，是一种多对多的非线性结构，所以无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序存储结构，但可以借助数组来表示元素之间的关系。同时，用链式存储结构来表示图也是可行的，但由于图中各顶点的度可以各不相同，若采用同构的节点结构来表示图会造成存储单元的浪费，所以需要根据图的具体情况和要进行的操作来分别存储图中的顶点和它们之间的关系。
6.2.1 邻接矩阵
邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，顶点序号依次为0，1，……，n-1，则G的邻接矩阵是具有如下定义的n阶方阵A：
1 对于无向图，(vi,vj)或(vj,vi)?E(G)；对于有向图，<vi,vj>?E(G)
A[i][j]=
0 其他情况
若G是网，则邻接矩阵可定义为：
wij 若(vi,vj)或<vi,vj>?E(G)
A[i][j]=
0或∞其他情况
例如，图6-1（a）的图G1对应的邻接矩阵为A1，图6-1（b）的图G2对应的邻接矩阵为A2，A1和A2邻接矩阵如图6-7所示。
图6-7 两个邻接矩阵
一般来说，邻接矩阵所占空间与边数无关（不考虑压缩存储），适合于存储稠密图。
为了反映一个图的全面信息，通常采用以下类型定义：
#define MAXVEX /*图中最大顶点个数*/
typedef char VertexType[3]; /*定义VertexType为char数组类型*/
typedef struct vertex
{
int adjvex; /*顶点编号*/
VertexType data; /*顶点的信息*/
} VType; /*顶点类型*/
typedef struct graph
{
int n,e; /*n为实际顶点数，e为实际边数*/
VType vexs[MAXVEX]; /*顶点集合*/
int edges[MAXVEX][MAXVEX]; /*边的集合*/
} AdjMatix; /*图的邻接矩阵类型*/
其中，VType类型定义一个顶点的基本数据，AdjMatix是定义一个图邻接矩阵的类型，包含该图的所有顶点和边。
以下算法CreateMatix()采用交互方式产生一个网（带权有向图）的邻接矩阵表示，DispMatix()输出图的邻接矩阵表示。
int CreateMatix(AdjMatix &g)
{
int i,j,k,b,e;
int w;
printf("顶点数(n)和边数(e):");
scanf("%d%d",&g.n,&g.e);
for(i=0;i<g.n;i++)
{
printf("序号为%d的顶点信息:",i);
scanf("%s",g.vexs[i].data);
g.vexs[i].adjvex=i; /*顶点编号为i*/
}
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
g.edges[i][j]=0;
for (k=0;k<g.e;k++)
{
printf("序号为%d的边=>",k);
printf("起点号 终点号 权值:");
scanf("%d%d%d",&b,&t,&w);
if(b<g.n && t<g.n && w>0)
g.edges[b][t]=w;
else
{
printf("输入错误!\n");
return(0);
}
}
return(1);
}
void DispMatix(AdjMatix g)
{
int i,j;
printf("\n图的邻接矩阵:\n");
for(i=0;i<g.n;i++)
{
for(j=0;j<g.n;j++)
printf("%3d",g.edges[i][j]);
printf("\n");
}
}
在上述函数设计好后，编写以下程序调用这些函数：
void main()
{
AdjMatix g;
CreateMatix(g);
DispMatix(g);
}
本程序的一次执行结果如下（其中↙表示回车键，下同）：
顶点数(n)和边数(e): 5 7↙
序号为0的顶点信息: a↙
序号为1的顶点信息: b↙
序号为2的顶点信息: c↙
序号为3的顶点信息: d↙
序号为4的顶点信息: e↙
序号为0的边=> 起点号 终点号 权值: 0 1 1↙
序号为1的边=> 起点号 终点号 权值: 0 2 2↙
序号为2的边=> 起点号 终点号 权值: 0 3 6↙
序号为3的边=> 起点号 终点号 权值: 1 3 4↙
序号为4的边=> 起点号 终点号 权值: 1 4 5↙
序号为5的边=> 起点号 终点号 权值: 2 4 3↙
序号为6的边=> 起点号 终点号 权值: 4 3 7↙
图的邻接矩阵:
0 1 2 6 0
0 0 0 4 5
0 0 0 0 3
0 0 0 0 0
0 0 0 7 0
6.2.2 邻接表
邻接表是图的一种链接存储结构。在邻接表中，对图中每个顶点建立一个带头节点的单链表，所有的头节点构成一个数组，第i个单链表中的节点表示依附于顶点vi的边。单链表中每个节点由两个域组成：顶点域adjvex，用以指示该邻接点在头节点数组中的序号（下标）；链域next，用以指向依附于顶点vi的下一条边所对应的节点。如果用邻接表存放网中的信息，则还需要在节点中增加一个存放权值的域（value）。
例如，图6-1中的两个图用邻接表表示如图6-8所示。
（a）G1对应的邻接表
（b）G2对应的邻接表
图6-8 G1和G2对应的邻接表
一般来说，邻接表所占空间与边数有关，适合于存储稀疏图。
注意：一个图的邻接表表示不唯一。这是因为，邻接表表示中各边表节点的链接次序取决于建立邻接表的算法以及边的输入次序。也就是说，在邻接表的每个线性链表中，各节点的顺序是任意的。在后面建立邻接表的算法中，为了简单方便，对于一个顶点，把后面指定的相邻顶点插入到链表的最前面。
一个图的邻接表存储结构的类型定义如下：
typedef char VertexType[3];
typedef struct edgenode
{
int adjvex; /*邻接点序号*/
int value; /*边的权值*/
struct edgenode *next; /*下一条边的顶点*/
} ArcNode; /*每个顶点建立的单链表中节点的类型*/
typedef struct vexnode
{
VertexType data; /*节点信息*/
ArcNode *firstarc; /*指向第一条边节点*/
} VHeadNode; /*单链表的头节点类型*/
typedef struct
{
int n,e; /*n为实际顶点数，e为实际边数*/
VHeadNode adjlist[MAXVEX]; /*单链表头节点数组*/
} AdjList /*图的邻接表类型*/
以下算法CreateAdjList( )采用交互方式建立一个有向图的邻接表表示，DispAdjList( )输出一个图的邻接表表示。
int CreateAdjList(AdjList *&G) /*建立有向图的邻接表*/
{
int i,b,t,w;
ArcNode *p;
G=(AdjList *)malloc(sizeof(AdjList));
printf("顶点数(n),边数(e):");
scanf("%d%d",&G->n,&G->e);
for(i=0;i<G->n;i++)
{
printf("序号为%d的顶点信息:", i);
scanf("%s",G->adjlist[i].data);
G->adjlist[i].firstarc=NULL;
}
for(i=0;i<G->e;i++)
{
printf("序号为边=>",i);
printf("起点号 终点号 权值:");
scanf("%d%d%d",&b,&t,&w);
if(b<G->n && t<G->n && w>0)
{
p=(ArcNode *)malloc(sizeof(ArcNode)); /*建立*p节点*/
p->value=w;p->adjvex=t;
p->next=G->adjlist[b].firstarc;/**p插入adjlist[b]单链表之首*/
G->adjlist[b].firstarc=p;
}
else
{
printf("输入错误!\n");
return(0);
}
}
return(1);
}
void DispAdjList(AdjList *G)
{
int i;
ArcNode *p;
printf("图的邻接表表示如下:\n");
for(i=0;i<G->n;i++)
{
printf(" [%d,%3s]=>",i,G->adjlist[i].data);
p=G->adjlist[i].firstarc;
while(p!=NULL)
{
printf("(%d,%d)->",p->adjvex,p->value);
p=p->next;
}
printf("∧\n");
}
}
在上述函数设计好后，编写以下程序调用这些函数：
void main()
{
AdjList *G;
CreateAdjList(G);
DispAdjList(G);
}
本程序的一次执行结果如下：
顶点数(n),边数(e): 5 7↙
序号为0的顶点信息: a↙
序号为1的顶点信息: b↙
序号为2的顶点信息: c↙
序号为3的顶点信息: d↙
序号为4的顶点信息: e↙
序号为边=> 起点号 终点号 权值: 0 1 1↙
序号为边=> 起点号 终点号 权值: 0 2 2↙
序号为边=> 起点号 终点号 权值: 0 3 6↙
序号为边=> 起点号 终点号 权值: 1 3 4↙
序号为边=> 起点号 终点号 权值: 1 4 5↙
序号为边=> 起点号 终点号 权值: 2 4 3↙
序号为边=> 起点号 终点号 权值: 4 3 7↙
图的邻接表表示如下:
[0, a]=>(3,6)->(2,2)->(1,1)->∧
[1, b]=>(4,5)->(3,4)->∧
[2, c]=>(4,3)->∧
[3, d]=>∧
[4, e]=>(3,7)->∧