第二節圖的存儲結構

當前講授

對于具有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賦給新結點的鄰接點域