圖的幾種存儲結構比較研究

班級：軟件工程六班

姓名：馬盛國

學號：140120010168圖的幾種主要存儲結構

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

1.鄰接矩陣

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

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

無向圖的鄰接矩陣是以主對角線對稱的，第i行(列)1的個數就是頂點vi

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

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

行中1的個數就是頂點i

的出度。▲第j列中1的個數就是頂點j

的入度。▲有向圖中各頂點的入度之和等于出度之和。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 ■帶權值的鄰接矩陣總結：（1）因為不考慮頂點到自身的邊或弧，所以鄰接矩陣的對角線必為0；（2）無向圖的鄰接矩陣為對稱矩陣，所以可用特殊矩陣壓縮方式存儲；（3）無向圖的頂點的度為鄰接矩陣中該頂點對應的行(列)中非零元個數；（5）有向圖的鄰接矩陣不一定為對稱矩陣;（6）有向圖中頂點的入度為該頂點對應列中非零元的個數，出度為該頂點對應行中為非零元的個數。鄰接矩陣表示法中圖的類型定義：#defineMAXSIZE100/*圖的頂點個數*/typedefstruc{intno;//頂點編號

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

//有向/無向圖，有向/無向網Typedefstruct

ArcCell{//弧（邊）結點的定義

VRTypeadj;//頂點間關系，無權圖取1或0；有權圖取權值類型

InfoType*info;//該弧相關信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{//圖的定義VertexTypevexs[MAX_VERTEX_NUM];//頂點表，用一維向量即可AdjMatrixarcs;//鄰接矩陣IntVernum,arcnum;//頂點總數，弧（邊）總數GraphKindkind;//圖的種類標志}Mgraph;

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

//給鄰接矩陣有關單元賦初值(循環次數＝弧數

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

//輸入弧的兩頂點以及對應權值

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

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

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

//輸入對應權值

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

//如果弧有信息則填入

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

//無向網是對稱矩陣

}returnOK;}//CreateUDN

例：用鄰接矩陣生成無向網的算法對于n個頂點e條弧的網，建網時間效率=O(n2+n+e*n)7.2.2鄰接表

鄰接表是圖的一種鏈式存儲結構。在鄰接表中為圖中每個頂點建立一個單鏈表，用單鏈表中的一個結點表示依附于該頂點的一條邊（或表示以該頂點為弧尾的一條弧），稱為邊（或弧）結點。

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

圖的鏈式存儲結構特征：（1）為每個頂點建立一個單鏈表；（2）第i個單鏈表中包含頂點Vi的所有鄰接頂點。

無向圖的鄰接表(不帶權)表結點表頭結點datafirstareadjvexnextare

每個鏈表的前邊附設一個表頭結點。把同一個頂點發出的邊鏈接在同一個邊鏈表中，鏈表的每一個結點代表一條邊，叫做表結點。假設數組下標自1開始1234

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

個邊鏈表鏈接的邊都是頂點i

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

個邊鏈表鏈接的邊都是進入頂點i

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

n

個頂點，e

條邊，則用鄰接表表示無向圖時，需要

n個表頭結點，2e個表結點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需n個表頭結點，e個表結點。帶權圖的邊表結點中還應保存該邊上的權值

info。網絡(帶權圖)的鄰接表邊表結點adjvexinfonextareadjvex：頂點號info：邊上所帶的權nextare：指針圖的鄰接表存儲表示#defineMAX_VERTEX_NUM20//假設的最大頂點數TypedefstructArcNode{

intadjvex;//該弧所指向的頂點位置

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

InfoArc*info;//該弧相關信息的指針}ArcNode；TypedefstructVNode{

//頂點結構

VertexTypedata;//頂點信息

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

Typedefstruct{//圖結構

AdjListvertics;//應包含鄰接表

intvexnum,arcnum;//應包含頂點總數和弧總數

intkind;//還應說明圖的種類（用標志）}ALGraph;

//圖結構空間效率為O(n+2e)或O(n+e)時間效率為O(n+e)

它是有向圖的另一種鏈式結構。

思路：將鄰接矩陣用鏈表存儲，是鄰接表、逆鄰接表的結合。1、每條弧對應一個結點(稱為弧結點，設5個域）2、每個頂點也對應一個結點（稱為頂點結點，設3個域）tailvexheadvexHlinktlinkinfo頂點結點弧結點三、十字鏈表tailvex:

弧尾頂點位置headvex:

弧頭頂點位置hlink:

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

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

弧信息n個頂點—用順序存儲結構data:存儲頂點信息。Firstin:

以頂點為弧頭的第一條弧結點。Firstout:

以頂點為弧尾的第一條弧結點。dataFirstinFirstout——適用于有向圖#defineMAX_VERTEX_NUM20TypedefstructArcBox{//弧結點結構

inttailvex,headvex;structArcBox*hlink,*tlink;InfoType*info;}ArcBox；TypedefstructVexNode{//頂點結構

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

intvexnum,arcnum;}OLGraph;//圖結構十字鏈表存儲結構描述：0v11v22v33v4v1v2v3v4010^2202^^3例：畫出有向圖的十字鏈表。十字鏈表優點：容易操作，如求頂點的入度、出度等。空間復雜度與鄰接表相同；建立的時間復雜度與鄰接表相同。3^03^^13^^2^數組下標不屬結點分量這是無向圖的另一種存儲結構，當對邊操作時，無向圖應采用此種結構存儲。

1、每條邊只對應一個結點（稱為邊結點），設立6個域；2、每個頂點也對應一個結點（頂點結點），設立2個域；markivexilinkjvexjlinkinfo邊結點四、鄰接多重表