圖的幾種存儲(chǔ)結(jié)構(gòu)比較分析

圖的幾種存儲(chǔ)結(jié)構(gòu)比較研究

班級(jí)：軟件工程六班

姓名：馬盛國(guó)

學(xué)號(hào)：140120010168圖的幾種主要存儲(chǔ)結(jié)構(gòu)

1.鄰接矩陣2.鄰接表3.十字鏈表4.鄰接多重表

1.鄰接矩陣

對(duì)于無(wú)向圖，(vi,vj)和(vj,vi)表示同一條邊，因此，在鄰接矩陣中aij=aji。對(duì)有向圖，弧<vi,vj>和<vj,vi>表示方向不同的兩條弧，所以aij≠aji。

在圖的頂點(diǎn)確定的情況下，其鄰接矩陣表示是唯一的。鄰接矩陣(AdjacencyMatrix)是表示圖中頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G＝(V,E)是具有n個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣An×n：

無(wú)向圖的鄰接矩陣是以主對(duì)角線對(duì)稱的，第i行(列)1的個(gè)數(shù)就是頂點(diǎn)vi

的度。即上圖中：D(1)=2 D(2)=3 D(3)=2 D(4)=3 D(5)=2

有向圖的鄰接矩陣可能是不對(duì)稱的。在有向圖中：▲第i

行中1的個(gè)數(shù)就是頂點(diǎn)i

的出度?！趈列中1的個(gè)數(shù)就是頂點(diǎn)j

的入度?！邢驁D中各頂點(diǎn)的入度之和等于出度之和。ID(vi)=

OD(vi)=

上圖中：D(1)=OD(1)+ID(1)=3D(2)=OD(2)+ID(2)=3 D(3)=OD(3)+ID(3)=3D(4)=OD(4)+ID(4)=3 ■帶權(quán)值的鄰接矩陣總結(jié)：（1）因?yàn)椴豢紤]頂點(diǎn)到自身的邊或弧，所以鄰接矩陣的對(duì)角線必為0；（2）無(wú)向圖的鄰接矩陣為對(duì)稱矩陣，所以可用特殊矩陣壓縮方式存儲(chǔ)；（3）無(wú)向圖的頂點(diǎn)的度為鄰接矩陣中該頂點(diǎn)對(duì)應(yīng)的行(列)中非零元個(gè)數(shù)；（5）有向圖的鄰接矩陣不一定為對(duì)稱矩陣;（6）有向圖中頂點(diǎn)的入度為該頂點(diǎn)對(duì)應(yīng)列中非零元的個(gè)數(shù)，出度為該頂點(diǎn)對(duì)應(yīng)行中為非零元的個(gè)數(shù)。鄰接矩陣表示法中圖的類型定義：#defineMAXSIZE100/*圖的頂點(diǎn)個(gè)數(shù)*/typedefstruc{intno;//頂點(diǎn)編號(hào)

infotypeinfo;//頂點(diǎn)其它信息}vertextype;//頂點(diǎn)類型typedefstruct//圖的定義{vertextypevexs[MAXSIZE]；/*頂點(diǎn)信息表*/intedges[MAXSIZE][MAXSIZE];/*鄰接矩陣*/intn；/*頂點(diǎn)數(shù)*/inte；/*邊數(shù)*/}mgraph；21435無(wú)向圖t->n=5t->e=6mgraph*t;BADCE有向圖mgraph*t;t->n=5t->e=6注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假設(shè)的最大頂點(diǎn)數(shù)Typedefenum{DG,DN,AG,AN}GraphKind;

//有向/無(wú)向圖，有向/無(wú)向網(wǎng)Typedefstruct

ArcCell{//?。ㄟ叄┙Y(jié)點(diǎn)的定義

VRTypeadj;//頂點(diǎn)間關(guān)系，無(wú)權(quán)圖取1或0；有權(quán)圖取權(quán)值類型

InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{//圖的定義VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)表，用一維向量即可AdjMatrixarcs;//鄰接矩陣IntVernum,arcnum;//頂點(diǎn)總數(shù)，?。ㄟ叄┛倲?shù)GraphKindkind;//圖的種類標(biāo)志}Mgraph;

圖的鄰接矩陣存儲(chǔ)表示（參見教材P161）對(duì)于n個(gè)頂點(diǎn)的圖或網(wǎng)，空間效率=O(n2)StatusCreateUDN(Mgraph&G){//無(wú)向網(wǎng)的構(gòu)造，用鄰接矩陣表示scanf(&G.vexnum,&G.arcnum,&IncInfo);//輸入總頂點(diǎn)數(shù)，總弧數(shù)和信息for(i=0;i<G.vexnum,;++i)scanf(&G.vexs[i]);//輸入頂點(diǎn)值，存入一維向量中for(i=0;i<G.vexnum;++i)//對(duì)鄰接矩陣n*n個(gè)單元初始化，adj=∞,info=NULLfor(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};for(k=0;k<G.arcnum;++k){

//給鄰接矩陣有關(guān)單元賦初值(循環(huán)次數(shù)＝弧數(shù)

scanf(&v1,&v2,&w);

//輸入弧的兩頂點(diǎn)以及對(duì)應(yīng)權(quán)值

i=LocateVex(G,v1);j=LocateVex(G,v2);

//找到兩頂點(diǎn)在矩陣中的位置(n次?

G.arcs[i][j].adj=w;

//輸入對(duì)應(yīng)權(quán)值

If(IncInfo)Input(*G.arcs[i][j].info);

//如果弧有信息則填入

G.arcs[i][j]=G.arcs[j][i]；

//無(wú)向網(wǎng)是對(duì)稱矩陣

}returnOK;}//CreateUDN

例：用鄰接矩陣生成無(wú)向網(wǎng)的算法對(duì)于n個(gè)頂點(diǎn)e條弧的網(wǎng)，建網(wǎng)時(shí)間效率=O(n2+n+e*n)7.2.2鄰接表

鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接表中為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，用單鏈表中的一個(gè)結(jié)點(diǎn)表示依附于該頂點(diǎn)的一條邊（或表示以該頂點(diǎn)為弧尾的一條?。?，稱為邊（或?。┙Y(jié)點(diǎn)。

因此鄰接表是由單鏈表的表頭形成的頂點(diǎn)表和單鏈表其余結(jié)點(diǎn)形成的邊表兩部分組成。圖的鄰接表表表示不唯一。

圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特征：（1）為每個(gè)頂點(diǎn)建立一個(gè)單鏈表；（2）第i個(gè)單鏈表中包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。

無(wú)向圖的鄰接表(不帶權(quán))表結(jié)點(diǎn)表頭結(jié)點(diǎn)datafirstareadjvexnextare

每個(gè)鏈表的前邊附設(shè)一個(gè)表頭結(jié)點(diǎn)。把同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，鏈表的每一個(gè)結(jié)點(diǎn)代表一條邊，叫做表結(jié)點(diǎn)。假設(shè)數(shù)組下標(biāo)自1開始1234

有向圖的鄰接表和逆鄰接表2^13^V1V2V3^2^1^2^V1V2V3G鄰接表逆鄰接表v1v2v3123123在有向圖的鄰接表中，第i

個(gè)邊鏈表鏈接的邊都是頂點(diǎn)i

發(fā)出的邊。也叫做出邊表。在有向圖的逆鄰接表中，第i

個(gè)邊鏈表鏈接的邊都是進(jìn)入頂點(diǎn)i

的邊。也叫做入邊表。鄰接表的類型定義說(shuō)明：在鄰接表的邊鏈表中，各個(gè)表結(jié)點(diǎn)的鏈入順序任意，視表結(jié)點(diǎn)輸入次序而定(不唯一)。設(shè)圖中有

n

個(gè)頂點(diǎn)，e

條邊，則用鄰接表表示無(wú)向圖時(shí)，需要

n個(gè)表頭結(jié)點(diǎn)，2e個(gè)表結(jié)點(diǎn)；用鄰接表表示有向圖時(shí)，若不考慮逆鄰接表，只需n個(gè)表頭結(jié)點(diǎn)，e個(gè)表結(jié)點(diǎn)。帶權(quán)圖的邊表結(jié)點(diǎn)中還應(yīng)保存該邊上的權(quán)值

info。網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表邊表結(jié)點(diǎn)adjvexinfonextareadjvex：頂點(diǎn)號(hào)info：邊上所帶的權(quán)nextare：指針圖的鄰接表存儲(chǔ)表示#defineMAX_VERTEX_NUM20//假設(shè)的最大頂點(diǎn)數(shù)TypedefstructArcNode{

intadjvex;//該弧所指向的頂點(diǎn)位置

structArcNode*nextarcs;//指向下一條弧的指針

InfoArc*info;//該弧相關(guān)信息的指針}ArcNode；TypedefstructVNode{

//頂點(diǎn)結(jié)構(gòu)

VertexTypedata;//頂點(diǎn)信息

ArcNode*firstarc;//指向依附該頂點(diǎn)的第一條弧的指針}VNode,AdjList[MAX_VERTEX_NUM];

Typedefstruct{//圖結(jié)構(gòu)

AdjListvertics;//應(yīng)包含鄰接表

intvexnum,arcnum;//應(yīng)包含頂點(diǎn)總數(shù)和弧總數(shù)

intkind;//還應(yīng)說(shuō)明圖的種類（用標(biāo)志）}ALGraph;

//圖結(jié)構(gòu)空間效率為O(n+2e)或O(n+e)時(shí)間效率為O(n+e)

它是有向圖的另一種鏈?zhǔn)浇Y(jié)構(gòu)。

思路：將鄰接矩陣用鏈表存儲(chǔ)，是鄰接表、逆鄰接表的結(jié)合。1、每條弧對(duì)應(yīng)一個(gè)結(jié)點(diǎn)(稱為弧結(jié)點(diǎn)，設(shè)5個(gè)域）2、每個(gè)頂點(diǎn)也對(duì)應(yīng)一個(gè)結(jié)點(diǎn)（稱為頂點(diǎn)結(jié)點(diǎn)，設(shè)3個(gè)域）tailvexheadvexHlinktlinkinfo頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)三、十字鏈表tailvex:

弧尾頂點(diǎn)位置headvex:

弧頭頂點(diǎn)位置hlink:

弧頭相同的下一弧位置tlink:

弧尾相同的下一弧位置info:

弧信息n個(gè)頂點(diǎn)—用順序存儲(chǔ)結(jié)構(gòu)data:存儲(chǔ)頂點(diǎn)信息。Firstin:

以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn)。Firstout:

以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn)。dataFirstinFirstout——適用于有向圖#defineMAX_VERTEX_NUM20TypedefstructArcBox{//弧結(jié)點(diǎn)結(jié)構(gòu)

inttailvex,headvex;structArcBox*hlink,*tlink;InfoType*info;}ArcBox；TypedefstructVexNode{//頂點(diǎn)結(jié)構(gòu)

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;Typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//表頭向量

intvexnum,arcnum;}OLGraph;//圖結(jié)構(gòu)十字鏈表存儲(chǔ)結(jié)構(gòu)描述：0v11v22v33v4v1v2v3v4010^2202^^3例：畫出有向圖的十字鏈表。十字鏈表優(yōu)點(diǎn)：容易操作，如求頂點(diǎn)的入度、出度等?？臻g復(fù)雜度與鄰接表相同；建立的時(shí)間復(fù)雜度與鄰接表相同。3^03^^13^^2^數(shù)組下標(biāo)不屬結(jié)點(diǎn)分量這是無(wú)向圖的另一種存儲(chǔ)結(jié)構(gòu)，當(dāng)對(duì)邊操作時(shí)，無(wú)向圖應(yīng)采用此種結(jié)構(gòu)存儲(chǔ)。

1、每條邊只對(duì)應(yīng)一個(gè)結(jié)點(diǎn)（稱為邊結(jié)點(diǎn)），設(shè)立6個(gè)域；2、每個(gè)頂點(diǎn)也對(duì)應(yīng)一個(gè)結(jié)點(diǎn)（頂點(diǎn)結(jié)點(diǎn)），設(shè)立2個(gè)域；markivexilinkjvexjlinkinfo邊結(jié)點(diǎn)四、鄰接多重表