大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第六章：圖-第二節(jié) 圖的存儲結(jié)構(gòu)

第二節(jié)圖的存儲結(jié)構(gòu)

當(dāng)前講授

對于具有n個頂點的圖，最常采用的存儲方法有鄰接矩陣存儲方法

與鄰接表存儲方法。

一、鄰接矩陣表示法

1、鄰接矩陣

設(shè)G=(V,E)是具有n個頂點的圖，則G的鄰接矩陣是具有如下

定義的n階方陣：

J1當(dāng),Vj)或Wi,Vp是E(G)的邊

[l]bJ=I0當(dāng)(Vi,Vj)或Wi,Vj＞不是E(G)的邊

【例】

1ooA

1io

10ii

1101

1oj

01

1100、

0010

1001

0101

00ooy

1619821A

OOOO6OO

coOO1833

618oo14

OO3314

2.采用鄰接矩陣存儲方法具有以下特點：

①無向圖的鄰接矩陣一定是一個對稱矩陣。因此，按照壓縮存儲

的思想，在具體存放鄰接矩陣時只需存放上（或者下）三角形陣的元

素即可。

②不帶權(quán)的有向圖的鄰接矩陣一般來說是一個稀疏矩陣（特別是

對于稀疏圖），于是可以采用三元組表的方法存儲鄰接矩陣。

③對于無向圖，鄰接矩陣的第i行（或者第i列）非零元素（或者

非8元素）的個數(shù)正好是第i個頂點的度D（Vi）o

（4）對于有向圖，鄰接矩陣的第i行（或者第i歹I」）非零元素（或者

非8元素）的個數(shù)正好是第i個頂點的出度OD（Vi）（或者入度ID

（V.））o

⑤對于無向圖，鄰接矩陣的所有非零元素（或者非8元素）的個數(shù)

正好是邊數(shù)的2倍。

⑥對于有向圖，鄰接矩陣的所有非零元素（或者非8元素）的個數(shù)

正好等于弧數(shù)。

⑦一個圖的鄰接矩陣表示是唯一的。

【真題選解】

（例題?填空題）若無向圖G中有n個頂點m條邊，采用鄰接矩陣

存儲，則該矩陣中非0元素的個數(shù)為O

隱藏答案

【答案】2m

【解析】對于無向圖，鄰接矩陣的所有非零元素的個數(shù)正好是邊數(shù)

的2倍。

3、鄰接矩陣表示的存儲結(jié)構(gòu)定義

#defineMaxVertexNum50〃最

大頂點數(shù)

typedefStruct

{vertexTvpevexs[MaxVertexNum];〃頂

點數(shù)組，類型假定為char型

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

鄰接矩陣，假定為int型

}MGQph;

4、建立一個無向網(wǎng)的算法

【算法描述】

VoidCreateMGraph(MGraph*G,intn,inte)

{〃采用鄰接矩陣表示法構(gòu)造無向網(wǎng)G,r、e表示圖的當(dāng)前頂點

數(shù)和邊數(shù)

inti,j,k,w;

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

入頂點數(shù)和邊數(shù)

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及邊上的權(quán)W

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

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

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

陣對稱元素權(quán)值

)

)

算法的時間復(fù)雜度0(n2)

二、鄰接表表示法

1、鄰接表

對于具有n個頂點的圖建立n個線性鏈表。每一個鏈表最前面都分

別設(shè)置一個稱之為頂點表結(jié)點，n個頂點構(gòu)成一個數(shù)組結(jié)構(gòu)。第i個鏈

表中的每一個鏈結(jié)點稱之為邊表結(jié)點。

【例】

頂點表邊表

無向圖無向圖的鄰接表

頂點表入邊表

有向圖的逆鄰接表

2、采用鄰接表存儲方法具有以下特點：

①一個圖的鄰接表表示法不唯一，這是因為鄰接表中各結(jié)點的鏈

接次序取決于建立鄰接表的算法（前插法還是后插法建鏈表）及邊的

輸入次序。

②對于無向圖，若它有n個頂點，e條邊，則其鄰接表中需要

2e+n個結(jié)點。其中有2e個邊表結(jié)點，n個頂點表結(jié)點。邊表結(jié)點的

個數(shù)一定是偶數(shù)，為邊數(shù)的2倍。

③對于有向圖，若它有n個頂點，e條邊，則其鄰接表中需要

e+n個結(jié)點。其中有e個邊表結(jié)點，n個頂點表結(jié)點。

④對于無向圖，第i個鏈表中的邊表結(jié)點的數(shù)目是第i個頂點的

度。

⑤對于有向圖，第i個鏈表中的邊表結(jié)點的數(shù)目是第i個頂點的出

度。在其逆鄰接表中，第i個鏈表中的邊表結(jié)點的數(shù)目是第i個頂點的

入度。

3、圖的鄰接表存儲結(jié)構(gòu)定義

#defineMaxVertexNum20

typedefcharVertexType;

typedefstructnode〃邊表結(jié)點類型

{intadjvexj〃頂點的序號

structnode*next;〃指向下一條邊的指

針

}EdgeNode;

typedefstructvnode〃頂點表結(jié)點

{VertexTypevertex;〃頂點域

EdgeNode*link;〃邊表頭指針

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

typedefAdjlistALGr■叩h;〃定義為圖類型

4、無向圖鄰接表的建表算法：

voidCreateGraph(ALGraphGL,intn,inte)

{〃n為頂點數(shù)，e為圖的邊數(shù)

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));

〃生成新的邊表結(jié)

點

p->adjvex=j;〃將鄰接點序號

j賦給新結(jié)點的鄰接點域

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

GL[i].link=p;〃將新結(jié)點插入

到頂點vi的邊表頭部

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

〃生成新的邊表結(jié)點

p->adj.vex=i;〃將鄰接點序號

i賦給新結(jié)點的鄰接點域