鄰接矩陣表示圖-深度-廣度優(yōu)先遍歷

1、*冋題描述：建立圖的存儲結(jié)構(gòu)(圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng),學(xué)生可以任選兩種類型)，能夠輸入圖的頂點和邊的信息，并存儲到相應(yīng)存儲結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。1、鄰接矩陣表示法：設(shè)G=(V,E)是一個圖，其中V=V1,V2,V3,Vi】。G的鄰接矩陣是一個他有下述性質(zhì)的n階方陣：1,若(Vi,Vj)eE或eE：Aij=0,反之圖5-2中有向圖G1和無向圖G2的鄰接矩陣分別為Ml和M2:Ml=廠01011|1010|1001|L0000JM2=廠0111|1010|IHOI|L1010J注意無向圖的鄰接是一個對稱矩陣，例如M2。用鄰接矩陣表示法來表示一個具有n個頂點的圖時，除了用

2、鄰接矩陣中的n+n個元素存儲頂點間相鄰關(guān)系外，往往還需要另設(shè)一個向量存儲1】個頂點的信息。因此其類型定義如下：VertexTypevertexMAX_VERTEX_NUM;/頂點向量AdjMatrixarcs;/鄰接矩陣intvexnum,arcnum;/圖的當(dāng)前頂點數(shù)和弧(邊)數(shù)GraphKindkind;/圖的種類標(biāo)志若圖中每個頂點只含一個編號i(lWiWvnum)，則只需一個二維數(shù)組表示圖的鄰接矩陣。此時存儲結(jié)構(gòu)可簡單說明如下：typeadjmatrix=arrayl.vnumJ.vnumjofadj;利用鄰接矩陣很容易判定任意兩個頂點之間是否有邊(或弧)相聯(lián)，并容易求得各個頂點的度。對

3、于無向圖，頂點Vi的度是鄰接矩陣中第i行元素之和，即D(Vi)=ZAij(或EAij)j=li=l對于有向圖，頂點Vi的出度OD(Vi)為鄰接矩陣第i行元素之和，頂點Vi的入度ED(Vi)為第i列元素之和。即OD(Vi)=EAij,OD(Vi)=ZA|j,i)j=lj=l用鄰接矩陣也可以表示帶權(quán)圖，只要令Wij,若Vi,Vj或(Vi,Vj)Aij=00,否則。其中Wij為Vi,Vj或(Vi,Vj)上的權(quán)值。相應(yīng)地，網(wǎng)的鄰接矩陣表示的類型定義應(yīng)作如下的修改：aclj:weiglitype;weiglitype為權(quán)類型圖5-6列出一個網(wǎng)和它的鄰接矩陣。廠OO31OOOOn1OOOO51OO11OO

4、OOOOOOOO11OOOO6OOOO1LOO322OOJ網(wǎng)(b)鄰接矩陣圖56網(wǎng)及其鄰接矩陣對無向圖或無向網(wǎng)絡(luò)，由于其鄰接矩陣是對稱的，故可釆用壓縮存貯的方法, 僅存貯下三角或上三角中的元素(但不含對角線上的元素)即可。顯然，鄰接矩陣表示法的空間復(fù)雜度O(n2)o無向網(wǎng)鄰接矩陣的建立方法是：首先將矩陣A的每個元素都初始化成8。然后，讀入邊及權(quán)值(ij,wij),將A的相應(yīng)元素置成Wijo2、圖的遍歷：*深度優(yōu)先搜索深度優(yōu)先搜索遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設(shè)初始狀態(tài)是圖中所有的頂點未曾被訪問，則深度優(yōu)先遍歷可從圖的某個頂點V出發(fā),訪問此頂點，然后依次從V的未被訪問的鄰接點出

5、發(fā)深度優(yōu)先遍歷圖，直至圖中所有和V有路徑相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中的一個未被訪問的頂點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。以圖7.13(a)中無向圖G.為例，深度優(yōu)先遍歷圖的過程如圖7.13(b)所示。假設(shè)從頂點出發(fā)進(jìn)行搜索，在訪問了頂點必后，選擇鄰接點V2。因為V2未曾訪問，則從必出發(fā)進(jìn)行搜索。依次類推，接著從VoV8,V5出發(fā)進(jìn)行搜索。在訪問了V5之后，由于V5的鄰接點已都被訪問，則搜索回到Vs。由于同樣的理由，搜索繼續(xù)回到V.,V?直至仏，此時由于的另一個鄰接點為被訪問，則搜索乂從必到V$,再繼續(xù)進(jìn)行下去。由此得到頂點的訪問序列為：fV2fV

6、s-v5-v5-v7顯然，這是一個遞歸的過程。為了在遍歷過程中便于區(qū)別頂點是否己被訪問，需附設(shè)訪問標(biāo)志數(shù)組vistedo.n-l,其初值為0,但某個頂點被訪問，則其相應(yīng)的分量置為lo*廣度優(yōu)先搜索假設(shè)從圖中某頂點V出發(fā)，在訪問了V之后一次訪問V的各個未曾訪問的擴大鄰接點，然后分別從這些鄰接點出發(fā)依次訪問他們的鄰接點，并使“先被訪問的鄰接點”先于“后被訪問的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直到圖中的頂點都被訪問為止。換句話說，廣度優(yōu)先遍歷圖的過程就是以V為起始點，有遠(yuǎn)至近，依次訪問和V有路

7、徑相通且路徑長度為1、2的頂點。例如，對圖G4進(jìn)行廣度優(yōu)先搜索遍歷的過程如圖7.13（3）所示，首先訪問vl和vl的鄰接點v2和v3,然后依次訪問v2的鄰接點v4和v5及v3的鄰接點v6和說，最后訪問v4的鄰接點v8。由于這些頂點的鄰接點均己被訪問，并且圖中所有頂點都被訪問，由此完成了圖的遍歷。得到的頂點訪問序列為V5-V6-V8和深度優(yōu)先搜索類似，在遍歷的過程中也需要一個訪問標(biāo)志數(shù)組。并且，為了順次訪問路徑長度為2、3、的頂點，需附設(shè)隊列以存儲己被訪問的路徑長度為1、2的頂點。2、圖的輸出圖的鄰接矩陣是一個二維數(shù)組，運用foi語句的嵌套依次輸出。 圖的構(gòu)造流程圖1、無向圖鄰接矩陣的建立算法如

8、下：procedurebuild-giaph;建立無向圖的鄰接矩陣beginfori:=ltondoread(G.vertexi)；讀入11個頂點的信息fori:=ltondoforj:=ltoedoG.arcsij=0：將鄰接矩陣的每個元素初始化成0fork:=ltoedoe為邊的數(shù)目read(ij,w)讀入邊i和權(quán)G.arcsij:=wG.arcsij=G.arcsii置對稱弧end；該算法的執(zhí)行時間是Og+f+e),其中消耗在鄰接矩陣初始化操作上的時間是O(iF),而en2,所以上述算法的時間復(fù)雜度是O()。2、無向網(wǎng)鄰接矩陣的建立算法如下：procedurebuild-giaph;建立

9、無向網(wǎng)的鄰接矩陣beginfori:=ltondoread(G.vertexi)；讀入11個頂點的信息fori:=ltondoforj:=ltoedoG.arcsij=maxint；將鄰接矩陣的每個元素初始化成maxint,計算機內(nèi)g用最大事數(shù)maxint表示fork:=ltoedoe為邊的數(shù)目read(ij,w)讀入邊和權(quán)G.arcsij:=w;G.arcsij:=wend：該算法的執(zhí)行時間是Og+if+e),其中消耗在鄰接矩陣初始化操作上的時間是O(iF),而en2,所以上述算法的時間復(fù)雜度是O()。3、圖的深度優(yōu)先遍歷算法分析beginfori:=ltondo(visitedi)初始化標(biāo)

10、志數(shù)組wliile(in)for：i=ltondo按要求訪問鄰接點end當(dāng)用二維數(shù)組表示鄰接矩陣作圖的存儲結(jié)構(gòu)時，查找每個頂點的鄰接點所需時間為O(iF),其中n為圖中頂點數(shù)。4、圖的廣度優(yōu)先遍歷算法分析beginfori:=ltondo(visitedi)初始化標(biāo)志數(shù)組wliile(in)for：i=1tondoififend二維數(shù)組表示鄰接矩陣作圖的存儲結(jié)構(gòu)，其中n為圖中頂點數(shù)，查找每個頂點的鄰接點所需時間為O(iF)。#include#inc1ude#include#include#includetidefineERROR0tidefineOK1tidefineMAX_VERTEX_NU

11、M20定義最大值tidefineINFINITY32768定義極大值tidefineMAX_INF020typedefintVrType;/定義新的類型typedefintInfoType;typedefcharVertexType;typedefenumDG,DN,UDG,UDNjGraphKind;/有向圖，有向網(wǎng)，無向圖,無向網(wǎng)typedefstruetArcCell/鄰接矩陣表示法的各個數(shù)據(jù)結(jié)構(gòu)VrTypeadj;/頂點關(guān)系類型。對無權(quán)圖，用或表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。InfoType*info;/該弧相關(guān)信息的指針ArcCell,AdjMatrixMAX_VERTEX_NU

12、MMAX_VERTEX_NUM;typedefstruetVertexTypevertexMAX_VERTEX_NUM:/頂點向量AdjMatrixarcs;/鄰接矩陣intvexnum,arcnum;/圖的當(dāng)前頂點數(shù)和弧(邊)數(shù)GraphKindkind;/圖的種類標(biāo)志MGraph;typedefstruet/設(shè)置棧intelemiMAXVERTEXNUM;inttop;SeqStack;intLocateVertex(MGraphG,VertexTypev):voidCreateUDG(MGraph&G);voidCreateUDN(MGraph&G);voidDepthFirstSear

13、chi(MGraphG):voidBreadthFirstSearchi(MGraphG):intCreateGraph(MGraph&G):voidDisplay(MGraphG):/*Graphcpp*/intLocateVertex(MGraphG,VertexTypev)/用于返回輸弧端點所表示的數(shù)值intj=0,k;for(k=0:kGvexnum;+k)if(Gvertexk=v)j=k:break:return(j);voidCreateUDG(MGraph&G)/采用數(shù)組(鄰接矩陣)表示法，構(gòu)造無向圖irrti,j,k,Incinfo:i,j,k為計數(shù)器,Incinfo為標(biāo)志符

14、charch;/用于吃掉多余的字符VertexTypevl,v2;用于放置輸入的弧的兩個頂點printf(“請輸入無向圖G的頂點數(shù)，邊數(shù)，弧是否含相關(guān)信息(是：，否：)：n);scanf(d,%d,&G.vexnum,&Garcnum,&Inclnfo);ch二getcharO;用于吃掉回年printf(”請輸入%d個頂點的値(1個字符，空格隔開)：n,G.vexnum);for(i=0;iG.vexnum;+i)/構(gòu)造頂點向量scanf(c,&GvertexEi);ch二getchar();printf(請輸入%1條邊的頂點頂點(以空格作為間隔):n,G.arcnum);for(i二0;iG

15、.vexnum;+i)/初始化鄰接矩陣for(j=0;jGvexnum;+j)Garcsijadj二0;G.二NULL;/adj,infofor(k=0;kGarcnum;+k)scanf(“c%c，&vl,&v2);sch=getchar():/ch吃掉回車符i=LocateVertex(G,vl);j=LocateVertex(G,v2);if(IncInfo)scanf(%d,&G.);G.arcsij.adj=G.arcsji.adj=l:/置的對稱弧/CreateUDGvoidCreateUDN(MGraph&G)/采用數(shù)組(鄰接矩陣)表示

16、法，構(gòu)造無向網(wǎng)inti,j,k,w,IncInfo;/i,j,k為計數(shù)器，w用于放置權(quán)值,Incinfo為標(biāo)志符charch;/用于吃掉多余的字符VertexTypevl,v2;用于放置輸入的弧的兩個頂點printf(”請輸入無向圖G的頂點數(shù)，邊數(shù)，弧是否含相關(guān)信息(是：，否：)：”)；scanf(%d,%d,%d,&G.vexnum,&G.arcnum,felnclnfo);ch二getcharO;用于吃掉IhL車printf(”請輸入%d個頂點的値(1個字符，空格隔開)：n,G.vexnum);for(i=0;iG.vexnum;+i)/構(gòu)造頂點向量scanf(%c,&G.vertexi)

17、;ch=getchar();printf(請輸入%4條邊的頂點頂點(以空格作為間隔):n,G.arcnum);for(i=0;iG.vexnum.:+i)/初始化鄰接矩陣for(j=0;jG.vexnum;+j)G.arcsij.adj=0;G.二NULL;/adj,infofor(k=0;kG.arcnum;+k)scanf(%c%c,&vl,&v2);ch=getchar():/ch吃掉回車符printf請輸入該邊的權(quán)值:”)；scanf(%d,&w);ch二getchar();i=LocateVertex(G,vl);j=LocateVertex(G,v2);G.a

18、rcsij.adj二w;if(IncInfo)scanf(%d,&G.);G.arcstij=G.arcstji;/置的對稱弧 /CreateUDNvoidDepthFirstSearchi(MGraphG)/無向圖、無向網(wǎng)深度優(yōu)先遍歷inti,j,k,visited20,t=l,a=l:/i,j,k為計數(shù)器，visited20為標(biāo)志符用于表示是否己經(jīng)訪問過SeqStackp;for(i=0;iG.vexnum;卄i)/初始化標(biāo)志符visitedEi=0;visited0=l;/規(guī)定以第一個字符開始遍歷printf(”深度優(yōu)先遍歷開始：n)；k=0;i=0;printf(

19、%cG.vertex0);while(iG.vexnum)/不斷以行循環(huán)在遇到符合條件時打印，每打印出一個就讓t加，把合適的值用棧來表示，把指針指向新的項for(j=0;jG.vexnum;+j)if(G.arcstij.adj!=0&G.arcstij.adj!=INFINITY&visitedj=0)printf(%cG.vertexj);visitedj=1;p.elemik=i;p.top=k:k+;i+:a+;t+;break;if(j=G.vexnum)/當(dāng)在某一行無法找到合適值時，輸出棧內(nèi)的值，返回上一行重新開始循環(huán)i=p.elemip.top;p.top；k-；if(t=G.v

20、exnum)break;/當(dāng)全部的定點都打印出來了就退出循環(huán)printf(n);voidBreadthFirstSearchl(MGraphG)/無向圖、無向網(wǎng)廣度優(yōu)先遍歷inti,j,k,visited20,t=l;/i,j為計數(shù)器，visited20為標(biāo)志符用于表示是否己經(jīng)訪問過SeqStackp;for(i=0;iG.vexnum:卄i)/初始化標(biāo)志符visitedi=0;visited0=l;/規(guī)定以第一個字符開始遍歷printfCr度優(yōu)先遍歷開始：n)；k=0;i=0;printf(%cG.vertex0);while(iG.vexnum)for(j=0:jG.vexnum;+j)/

21、不斷以彳亍循環(huán)在遇到符合條件時打印,每打印出一個就讓t加，把指針指向新的項if(G.arcstij.adj!=0&G.arcstij.adj!=INFINITY&visitedj=0)printf(%cG.vertexj);visitedj=1;p.elemik=i;p.top=k;k+:t+;i+；/換行，重新開始循環(huán)if(t二二G.vexnum)break;printf(n);intCreateGraph(MGraph&G)/構(gòu)造圖printf(/z請輸入要構(gòu)造的圖的類型(有向圖:0,有向網(wǎng)：1,無向圖:2,無向網(wǎng)：3):n)；scanf(%d,&G.kind);switch(G.kind)case2:CreateUDG(G);break;case3:CreateUDN(G);break;defauIt:returnERROR:/CreateGraphvoidDisplay(MGra