1、*冋題描述：建立圖的存儲(chǔ)結(jié)構(gòu)(圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng),學(xué)生可以任選兩種類型)，能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。1、鄰接矩陣表示法：設(shè)G=(V,E)是一個(gè)圖，其中V=V1,V2,V3,Vi】。G的鄰接矩陣是一個(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注意無向圖的鄰接是一個(gè)對(duì)稱矩陣，例如M2。用鄰接矩陣表示法來表示一個(gè)具有n個(gè)頂點(diǎn)的圖時(shí)，除了用

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

3、于無向圖，頂點(diǎn)Vi的度是鄰接矩陣中第i行元素之和，即D(Vi)=ZAij(或EAij)j=li=l對(duì)于有向圖，頂點(diǎn)Vi的出度OD(Vi)為鄰接矩陣第i行元素之和，頂點(diǎn)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列出一個(gè)網(wǎng)和它的鄰接矩陣。廠OO31OOOOn1OOOO51OO11OO

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

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

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

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

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

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

10、志數(shù)組wliile(in)for：i=ltondo按要求訪問鄰接點(diǎn)end當(dāng)用二維數(shù)組表示鄰接矩陣作圖的存儲(chǔ)結(jié)構(gòu)時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(iF),其中n為圖中頂點(diǎn)數(shù)。4、圖的廣度優(yōu)先遍歷算法分析beginfori:=ltondo(visitedi)初始化標(biāo)志數(shù)組wliile(in)for：i=1tondoififend二維數(shù)組表示鄰接矩陣作圖的存儲(chǔ)結(jié)構(gòu)，其中n為圖中頂點(diǎn)數(shù)，查找每個(gè)頂點(diǎn)的鄰接點(diǎ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/鄰接矩陣表示法的各個(gè)數(shù)據(jù)結(jié)構(gòu)VrTypeadj;/頂點(diǎn)關(guān)系類型。對(duì)無權(quán)圖，用或表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。InfoType*info;/該弧相關(guān)信息的指針ArcCell,AdjMatrixMAX_VERTEX_NU

12、MMAX_VERTEX_NUM;typedefstruetVertexTypevertexMAX_VERTEX_NUM:/頂點(diǎn)向量AdjMatrixarcs;/鄰接矩陣intvexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(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)/用于返回輸弧端點(diǎn)所表示的數(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為計(jì)數(shù)器,Incinfo為標(biāo)志符

14、charch;/用于吃掉多余的字符VertexTypevl,v2;用于放置輸入的弧的兩個(gè)頂點(diǎn)printf(“請(qǐng)輸入無向圖G的頂點(diǎn)數(shù)，邊數(shù)，弧是否含相關(guān)信息(是：，否：)：n);scanf(d,%d,&G.vexnum,&Garcnum,&Inclnfo);ch二getcharO;用于吃掉回年printf(”請(qǐng)輸入%d個(gè)頂點(diǎn)的値(1個(gè)字符，空格隔開)：n,G.vexnum);for(i=0;iG.vexnum;+i)/構(gòu)造頂點(diǎn)向量scanf(c,&GvertexEi);ch二getchar();printf(請(qǐng)輸入%1條邊的頂點(diǎn)頂點(diǎn)(以空格作為間隔):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:/置的對(duì)稱弧/CreateUDGvoidCreateUDN(MGraph&G)/采用數(shù)組(鄰接矩陣)表示

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

17、;ch=getchar();printf(請(qǐng)輸入%4條邊的頂點(diǎn)頂點(diǎn)(以空格作為間隔):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請(qǐng)輸入該邊的權(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;/置的對(duì)稱弧 /CreateUDNvoidDepthFirstSearchi(MGraphG)/無向圖、無向網(wǎng)深度優(yōu)先遍歷inti,j,k,visited20,t=l,a=l:/i,j,k為計(jì)數(shù)器，visited20為標(biāo)志符用于表示是否己經(jīng)訪問過SeqStackp;for(i=0;iG.vexnum;卄i)/初始化標(biāo)志符visitedEi=0;visited0=l;/規(guī)定以第一個(gè)字符開始遍歷printf(”深度優(yōu)先遍歷開始：n)；k=0;i=0;printf(

19、%cG.vertex0);while(iG.vexnum)/不斷以行循環(huán)在遇到符合條件時(shí)打印，每打印出一個(gè)就讓t加，把合適的值用棧來表示，把指針指向新的項(xiàng)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)在某一行無法找到合適值時(shí)，輸出棧內(nèi)的值，返回上一行重新開始循環(huán)i=p.elemip.top;p.top；k-；if(t=G.v

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

21、不斷以彳亍循環(huán)在遇到符合條件時(shí)打印,每打印出一個(gè)就讓t加，把指針指向新的項(xiàng)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請(qǐng)輸入要構(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