大学《数据结构》第六章：图-第二节 图的存储结构

第二节图的存储结构

当前讲授

对于具有n个顶点的图，最常采用的存储方法有邻接矩阵存储方法

与邻接表存储方法。

一、邻接矩阵表示法

1、邻接矩阵

设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下

定义的n阶方阵：

J1当,Vj)或Wi,Vp是E(G)的边

[l]bJ=I0当(Vi,Vj)或Wi,Vj＞不是E(G)的边

【例】

1ooA

1io

10ii

1101

1oj

01

1100、

0010

1001

0101

00ooy

1619821A

OOOO6OO

coOO1833

618oo14

OO3314

2.采用邻接矩阵存储方法具有以下特点：

①无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储

的思想，在具体存放邻接矩阵时只需存放上（或者下）三角形阵的元

素即可。

②不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵（特别是

对于稀疏图），于是可以采用三元组表的方法存储邻接矩阵。

③对于无向图，邻接矩阵的第i行（或者第i列）非零元素（或者

非8元素）的个数正好是第i个顶点的度D（Vi）o

（4）对于有向图，邻接矩阵的第i行（或者第i歹I」）非零元素（或者

非8元素）的个数正好是第i个顶点的出度OD（Vi）（或者入度ID

（V.））o

⑤对于无向图，邻接矩阵的所有非零元素（或者非8元素）的个数

正好是边数的2倍。

⑥对于有向图，邻接矩阵的所有非零元素（或者非8元素）的个数

正好等于弧数。

⑦一个图的邻接矩阵表示是唯一的。

【真题选解】

（例题•填空题）若无向图G中有n个顶点m条边，采用邻接矩阵

存储，则该矩阵中非0元素的个数为O

隐藏答案

【答案】2m

【解析】对于无向图，邻接矩阵的所有非零元素的个数正好是边数

的2倍。

3、邻接矩阵表示的存储结构定义

#defineMaxVertexNum50〃最

大顶点数

typedefStruct

{vertexTvpevexs[MaxVertexNum];〃顶

点数组，类型假定为char型

Adjmstrixarcs[MaxVertexNum][Max\/ertexNum];//

邻接矩阵，假定为int型

}MGQph;

4、建立一个无向网的算法

【算法描述】

VoidCreateMGraph(MGraph*G,intn,inte)

{〃采用邻接矩阵表示法构造无向网G,r、e表示图的当前顶点

数和边数

inti,j,k,w;

scanf("%d,%d",&n,&e);〃读

入顶点数和边数

for(i=0;i<n;i++)〃输

入顶点信息

scanf("%c",&G->vexs[i]);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

G->arcs[i][j]=INT_MAX;〃初始

化邻接矩阵元素为无穷大,一般填32767

for(k=0;k<e;k++)〃读入

e条边，建立邻接矩阵

〃读入一

条边的两端顶点序号i、j及边上的权W

{scanf("%d,%d,%d",&i,&j,&w);

G->arcs[i][j]=w;

G->arcs[j][i]=w;〃置矩

阵对称元素权值

)

)

算法的时间复杂度0(n2)

二、邻接表表示法

1、邻接表

对于具有n个顶点的图建立n个线性链表。每一个链表最前面都分

别设置一个称之为顶点表结点，n个顶点构成一个数组结构。第i个链

表中的每一个链结点称之为边表结点。

【例】

顶点表边表

无向图无向图的邻接表

顶点表入边表

有向图的逆邻接表

2、采用邻接表存储方法具有以下特点：

①一个图的邻接表表示法不唯一，这是因为邻接表中各结点的链

接次序取决于建立邻接表的算法（前插法还是后插法建链表）及边的

输入次序。

②对于无向图，若它有n个顶点，e条边，则其邻接表中需要

2e+n个结点。其中有2e个边表结点，n个顶点表结点。边表结点的

个数一定是偶数，为边数的2倍。

③对于有向图，若它有n个顶点，e条边，则其邻接表中需要

e+n个结点。其中有e个边表结点，n个顶点表结点。

④对于无向图，第i个链表中的边表结点的数目是第i个顶点的

度。

⑤对于有向图，第i个链表中的边表结点的数目是第i个顶点的出

度。在其逆邻接表中，第i个链表中的边表结点的数目是第i个顶点的

入度。

3、图的邻接表存储结构定义

#defineMaxVertexNum20

typedefcharVertexType;

typedefstructnode〃边表结点类型

{intadjvexj〃顶点的序号

structnode*next;〃指向下一条边的指

针

}EdgeNode;

typedefstructvnode〃顶点表结点

{VertexTypevertex;〃顶点域

EdgeNode*link;〃边表头指针

}VNode,Adjlist[MaxVertexNum]；〃邻接表

typedefAdjlistALGr■叩h;〃定义为图类型

4、无向图邻接表的建表算法：

voidCreateGraph(ALGraphGL,intn,inte)

{〃n为顶点数，e为图的边数

inti,j,k;EdgeNode*p;

for(i=0;i<n;i++)〃建立顶点表

{GL[i].vertex=getchar();〃读入顶点信

息

GL[i].link=NULL;〃边表头指针

置空

)

for(k=0;k<e;k++)〃采用头插法

建立每个顶点的邻接表

{scanf("%d,%d",&i,&j);〃读入边

(vi,vj)的顶点序号

p=(EdgeNode*)malloc(sizeof(EdgeNode));

〃生成新的边表结

点

p->adjvex=j;〃将邻接点序号

j赋给新结点的邻接点域

p->next=GL[i].link;

GL[i].link=p;〃将新结点插入

到顶点vi的边表头部

p=(EdgeNode*)malloc(sizeof(EdgeNode));

〃生成新的边表结点

p->adj.vex=i;〃将邻接点序号

i赋给新结点的邻接点域