圖的遍歷和生成樹求解實(shí)現(xiàn)的課程結(jié)構(gòu)設(shè)計(jì)

1、圖的遍歷和生成樹求解實(shí)現(xiàn)的課程結(jié)構(gòu)設(shè)計(jì)問題描述：圖的遍歷和生成樹求解實(shí)現(xiàn)圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素（及其孩子結(jié)點(diǎn)）相關(guān)但只能和上一層中一個(gè)元素（即雙親結(jié)點(diǎn)）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。生成樹求解主要利用普利姆和克雷斯特算法求解最小生成樹，只有強(qiáng)連通圖才有生成樹?；竟δ?）先任意創(chuàng)建一個(gè)圖；2）圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)3）最小生成樹（兩

2、個(gè)算法）的實(shí)現(xiàn)，求連通分量的實(shí)現(xiàn)4）要求用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲實(shí)現(xiàn)輸入輸出輸入數(shù)據(jù)類型為整型和字符型，輸出為整型和字符二、概要設(shè)計(jì)1.設(shè)計(jì)思路：a圖的鄰接矩陣存儲：根據(jù)所建無向圖的結(jié)點(diǎn)數(shù)n,建立n*n的矩陣，其中元素全是無窮大（int_max），再將邊的信息存到數(shù)組中。其中無權(quán)圖的邊用1表示，無邊用0表示；有全圖的邊為權(quán)值表示，無邊用表示。圖的鄰接表存儲：將信息通過鄰接矩陣轉(zhuǎn)換到鄰接表中，即將鄰接矩陣的每一行都轉(zhuǎn)成鏈表的形式將有邊的結(jié)點(diǎn)進(jìn)行存儲。圖的廣度優(yōu)先遍歷：假設(shè)從圖中的某個(gè)頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問V的各個(gè)未曾訪問過的鄰接點(diǎn)，然后再訪問此鄰接點(diǎn)的未被訪問的鄰接點(diǎn)，并使“

3、先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時(shí)圖中還有未被訪問的，則另選未被訪問的重復(fù)以上步驟，是一個(gè)非遞歸過程。圖的深度優(yōu)先遍歷：假設(shè)從圖中某頂點(diǎn)V出發(fā)，依依次訪問V的鄰接頂點(diǎn)，然后再繼續(xù)訪問這個(gè)鄰接點(diǎn)的系一個(gè)鄰接點(diǎn)，如此重復(fù)，直至所有的點(diǎn)都被訪問，這是個(gè)遞歸的過程。圖的連通分量：這是對一個(gè)非強(qiáng)連通圖的遍歷，從多個(gè)結(jié)點(diǎn)出發(fā)進(jìn)行搜索，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪問序列恰為其連通分量的頂點(diǎn)集。本程序利用的圖的深度優(yōu)先遍歷算法。2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：ADTQueue數(shù)據(jù)對象：D=a|aGElemSet,i=l

4、,2,3,n,n0ii數(shù)據(jù)關(guān)系：R1=|a,a$D,i=l,2,3,ni-1ii-1i基本操作：InitQueue(&Q)操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。QueueEmpty(Q)初始條件：Q為非空隊(duì)列。操作結(jié)果：若Q為空隊(duì)列，則返回真，否則為假。EnQueue(&Q,e)初始條件：Q為非空隊(duì)列。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。DeQueue(&Q,e)初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。ADTQueueADTGraph數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R=VRVR二v,w|v,wGV且P(v,w),v,w表示從v到w的弧

5、，謂詞P(v,w)定義了弧v,w的意義或信息基本操作P：CreatGraph(&G,V,VR);初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。BFSTraverse(G,visit();初始條件：圖G存在，Visit是定點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過程中對每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。DFSTraverse(G,visit();初始條件：圖G存在，Visit是定點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過程中對每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作

6、失敗。DFStra_fen(G)初始條件：圖G存在，存在圖的深度優(yōu)先遍歷算法。操作結(jié)果：從多個(gè)頂點(diǎn)對圖進(jìn)行深度優(yōu)先遍歷，得到連通分量ADTGraph;3.軟件結(jié)構(gòu)設(shè)計(jì)：maincreatMGraph_L(G)catadj(gra,G)a,G)e(gra)efen(gra6MiniSpanTfiMiniSpanTRee_PRIM(g|EE_KRUSCALG.vexnum)(G,gra)函數(shù)名返回值類型creatMGraphL(G)intcreatadj(gra,G)intljjzprint(G)voidadjprint(gra,G)voidBFSTraverse(gra)voidDFStra(g

7、ra)intDFSTraversefen(gra)intMiniSpanTreePRIM(g,G.vexnum)intMiniSpanTREEKRUSCAL(G,gra)voidljjzprinadjprint(g*BFSTraverSDFStra(gr*DFSTraverG)三、詳細(xì)設(shè)計(jì)定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu)，及其基本操作的實(shí)現(xiàn)；鄰接矩陣定義:typedefstructArcCellVRTypeadj；/VRType是頂點(diǎn)關(guān)系類型。對無權(quán)圖，用1或0表示相鄰否;對帶權(quán)圖，則為權(quán)值類型InfoType*info；/該弧相關(guān)信息的指針ArcCell,AdjMatrixmaxmax；

8、typedefstructVertexTypevexsmax；/頂點(diǎn)向量AdjMatrixarcs;/鄰接矩陣intvexnum,arcnum；/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)MGraph_L；鄰接表的定義:typedefstruetArcNode/弧結(jié)點(diǎn)intadjvex；/該弧指向的頂點(diǎn)的位置structArcNode*nextare；/指向下一條弧的指針I(yè)nfoType*info；/該弧相關(guān)信息的指針ArcNode；typedefstructVNode/鄰接鏈表頂點(diǎn)頭接點(diǎn)VertexTypedata；/頂點(diǎn)信息ArcNode*firstare；/指向第一條依附該頂點(diǎn)的弧的指針VNode,AdjLi

9、st；typedefstruct/圖的定義AdjListverticesmax；intvexnum,arcnum；/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)ALGraph；隊(duì)列定義:typedefstructQNodeQElemTypedata；structQNode*next；QNode,*QueuePtr；typedefstructQueuePtrfront；/隊(duì)頭指針QueuePtrrear；/隊(duì)尾指針LinkQueue；2主函數(shù)和其他函數(shù)的偽碼算法；主函數(shù)：intmain()ints；chary=y；cout|QQQQQQQQQQQQQQQQQ菜單QQQQQQQQQQQQQQQQQQ|endl；cout|

10、【0、創(chuàng)建一個(gè)無向圖|endl;cout|【1、顯示該圖的鄰接矩陣|endl;cout|【2、顯示該圖的鄰接表|endl;cout|【3、廣度優(yōu)先遍歷|endl;cout|【4、深度優(yōu)先遍歷|endl;cout|5、最小生成樹MiniSpanTree_PRIM算法|endl;cout|6、最小生成樹MiniSpanTree_KRUSCAL算法|endl；cout|7、連通分量|s；if(s=0)+o；if(o=2)n=0；l=0；o=0；switch(s)case0：cout創(chuàng)建一個(gè)無向圖：endl；MGraph_LG；creatMGraph_L(G);ALGraphgra;creatadj(

11、gra,G);break;casel：cout鄰接矩陣顯示如下：endl；ljjzprint(G);break；case2：cout鄰接表顯示如下：endl；adjprint(gra,G)；break；case3：cout”廣度優(yōu)先遍歷：；BFSTraverse(gra)；coutendl；break；case4：cout深度優(yōu)先遍歷：；DFStra(gra)；coutendl；break；case5：if(n=0)cout無權(quán)圖沒有最小生成樹；break；elseif(l0)cout若該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)時(shí)最小生成樹不存在endl；break；elseinti,gmaxmax

12、；for(i=0；i!=G.vexnum；+i)for(intj=0；j!=G.vexnum；+j)gi+1j+1=G.arcsij.adj；cout普利姆算法：endl；MiniSpanTree_PRIM(g,G.vexnum)；break；case6：if(n=0)cout無權(quán)圖沒有最小生成樹；break；elseif(l0)couty；if(y=n)break；return0；鄰接矩陣存儲：intcreatMGraph_L(MGraph_L&G)/創(chuàng)建圖用鄰接矩陣表示charv1,v2；inti,j,w；cout請輸入頂點(diǎn)和弧的個(gè)數(shù)endl；cinG.vexnumG.arcnum；cou

13、t輸入各個(gè)頂點(diǎn)endl；for(i=0；iG.vexnum；+i)cinG.vexsi；for(i=0；iG.vexnum；+i)for(j=0；jG.vexnum；+j)G.arcsij.adj=int_max；G.=NULL；for(intk=0;kvlv2w；/輸入一條邊依附的兩點(diǎn)及權(quán)值i=localvex(G,vl)；/確定頂點(diǎn)VI和V2在圖中的位置j=localvex(G,v2)；G.arcsij.adj=w；G.arcsji.adj=w；for(i=0；i!=G.vexnum；+i)for(j=0；j!=G.vexnum；+j)if(G.arcsij.adj!

14、=1&G.arcsij.adjint_max)n+=1；if(n=1)cout這是一個(gè)有權(quán)圖endl；elsecout這是一個(gè)無權(quán)圖endl；cout圖G鄰接矩陣創(chuàng)建成功！endl；returnG.vexnum；鄰接矩陣的輸出：voidljjzprint(MGraph_LG)/鄰接矩陣的輸出inti,j；if(n=0)for(i=0；i!=G.vexnum；+i)for(j=0；j!=G.vexnum；+j)if(G.arcsij.adj=int_max)cout0；elsecoutG.arcsij.adj；coutendl；elsefor(i=0;i!=G.vexnum;+i)for(j=0

15、;j!=G.vexnum;+j)if(G.arcsij.adj二二int_max)cout8；elsecoutG.arcsij.adj;coutadjvex=j;arc-nextarc=gra.verticesi.firstarc;gra.verticesi.firstarc=arc;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;cout圖G鄰接表創(chuàng)建成功！endl；return1;鄰接表輸出：voidadjprint(ALGraphgra,MGraph_LG)/鄰接表輸出inti；for(i=0；i!=gra.vexnum；+i)ArcNode*p；cout

16、i,G.vexsi；p=gra.verticesi.firstarc；while(p!=NULL)coutadjvexnextarc；coutEnd；coutnext=NULL；return1；入隊(duì)：StatusEnQueue(LinkQueue&Q,QElemTypee)/入隊(duì)，插入元素e為Q的新的隊(duì)尾元素QueuePtrp；p=(QueuePtr)malloc(sizeof(QNode)；if(!p)return0；/存儲分配失敗p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return1;出隊(duì)：StatusDeQueue(LinkQueue&Q,

17、QElemType&e)/出隊(duì)，若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回，并返回真，否則假Q(mào)ueuePtrp;if(Q.front=Q.rear)return0;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return1;判斷隊(duì)為空：StatusQueueEmpty(LinkQueueQ)/判斷隊(duì)為空if(Q.front=Q.rear)return1;return0;廣度優(yōu)先遍歷：voidBFSTraverse(ALGraphgra)inti,e;LinkQueueq;for(i=

18、0;i!=gra.vexnum;+i)visitedi=0;InitQueue(q);for(i=0;i!=gra.vexnum;+i)if(!visitedi)visitedi=1;cout=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)visitedwe=1;coutgra.verticeswe.data;EnQueue(q,we);深度優(yōu)先遍歷：intDFS(ALGraphgra,inti)visitedi=1;intwe1;cout=0;we=nextadjvex(gra,gra.verticesi,we)we1=we;if(vi

19、sitedwe=0)DFS(gra,we);we=we1;return1;intDFStra(ALGraphgra)inti,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);return0;連通分量：intDFSTraverse_fen(ALGraphgra)inti,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);cout=0;we=nex

20、tadjvex(gr-a,gra.verticese,we)If(!visitedwe.)YESVisitedwe=1;Enqueue(q.we)結(jié)束NO開始YESIf(lowcostjmin)&(lowcostj!=0)fIf(gkj0為有權(quán)圖，此時(shí)輸出的時(shí)候用a代替10000；n=0為無權(quán)圖，此時(shí)輸出的時(shí)候用0代替10000.b程序中有的功能對某些圖是不適用的，比如無權(quán)圖沒有最小生成樹，非強(qiáng)連通圖沒有最小生成樹等。所以在程序中又新增了全局變量l,l0時(shí)表示為非強(qiáng)連通圖，則在求最小生成樹時(shí)報(bào)錯(cuò)。C當(dāng)程序先創(chuàng)建一個(gè)有權(quán)圖后，n的值會大于1,第二次創(chuàng)無權(quán)圖時(shí)也會被程序認(rèn)為有權(quán)圖，所以在程序中在定

21、義全局變量o（初值為0），來判斷創(chuàng)建了幾次圖，當(dāng)?shù)诙蝿?chuàng)建圖，即o=2時(shí)，所有全局變量在開始全歸零。程序中可以改進(jìn)的地方說明；當(dāng)建立一個(gè)圖時(shí)先得求其連通分量，從而確定全局變量l的值，從而才能判斷該圖是否有最小生成樹。五、測試結(jié)果創(chuàng)建一個(gè)無權(quán)圖：JE:C6MyProjectsk課設(shè)叭tewt,exeinnmnnmnnmnunnnngmnnmnnoannonnai!【0、倉建一|無問圖i【丄、顯不該固冃勺鄰按矩庫!匕顯丞該圖的鄰揍表!0亠度優(yōu)先遍歷iS塗捷憂客遍厲土innmnnm口口mn口口aancononn口口口口口口oaSoonnoi在或最小生咸梃前請去求逐通分量F!6.iniSpanTree

22、_PRI:【7、最小生iniSpanTpee_KRUSCftL請選擇菜單、創(chuàng)建一個(gè)無向圖:i青輸入頂點(diǎn)和弧的個(gè)數(shù)76輸入各個(gè)頂點(diǎn)abcdefg-輸人一條邊恆附的頂點(diǎn)和權(quán)ah1輸入一條邊依附的頂點(diǎn)利權(quán)kc1輸入一條邊依附的頂點(diǎn)和權(quán)bd1箭入一條邊依附的頂點(diǎn)和權(quán)淀1輸入一條邊恆附的頂點(diǎn)利權(quán)de1輸入一條邊依附的頂點(diǎn)和權(quán)輸1建是一個(gè)無機(jī)圖fficW矩陣創(chuàng)建成功！圖G鄰聲衰創(chuàng)建成功!足否繼續(xù)？V/n：是否繼續(xù)?y/n：y請選擇菜單；鄰接矩陣顯示如下:3110009L001100L0000003160100316100030000013000010是否繼續(xù)？y/n：是否繼續(xù)？yn：y責(zé)選擇菜單；怎通分量

23、Mcbedfsr是否繼續(xù)？y/n：ij請選擇菜単：無權(quán)圖滾有最小空成樹是否無瘵？yn=y請選擇菜單；7役宙最小生成郴創(chuàng)建一個(gè)費(fèi)強(qiáng)連通的有權(quán)圖:CfiIyProjects$入各個(gè)頂點(diǎn)hedefg金入一條邊依附的頂點(diǎn)和權(quán)鼬K條邊依附的頂點(diǎn)和權(quán)c3鼬條邊依附的頂點(diǎn)和權(quán)d1俞坯條邊依附的頂點(diǎn)和權(quán)鈦條邊依附的頂點(diǎn)和權(quán)e4敘V條邊依附的頂點(diǎn)和權(quán)g2丈杲一個(gè)有權(quán)圈昶鄰拱矩陣倉!I建成功|昶鄰謹(jǐn)袤創(chuàng)建成功|否繼續(xù)農(nóng)少2該圈為非強(qiáng)連適圈（含有多個(gè)連通分量時(shí),最小主成樹不存在亥圏為非強(qiáng)連通圏含有多個(gè)連逋分量,最小-主成捌不存在創(chuàng)建一個(gè)有權(quán)連通圖：g*E:XVCfiMyPxojects創(chuàng)建一個(gè)無向商；1請輸入頂點(diǎn)和

24、弧的個(gè)數(shù)S5輸入各個(gè)頂點(diǎn)；ibcde輸入一條邊依附的頂點(diǎn)和權(quán)ab2輸入一條邊依附的頂點(diǎn)和權(quán)ac3輸入一條邊依附的頂點(diǎn)和權(quán)bd1輸入一條邊依附的頂點(diǎn)和權(quán)脣只一條邊依附的頂點(diǎn)和權(quán)de4邊杲個(gè)有權(quán)圈圖G鄰按矩陣刨建咸功I圈G鄰接表創(chuàng)建成功|是否繼續(xù)？y/n=P喜選擇菜單：磴通分量=acb&db否繼續(xù)？y/n=i,賣選擇菜單：詈利姆算法匕(0A233曜否繼續(xù)？必曲事選擇菜單；住魯斯卡爾算法二233是否繼綾1y/n=六、用戶手冊-*E:VC5IyProjects課設(shè)4Debugtest.exeH口口口口O.C11!.V:漠卑.【TOC o 1-5 h z!t【氛倉0建廣無總:旻f!-舐顯丞該1WS矩陣n

25、住、顯示該圖的鄰接表H-3.廣鹿備先遍歷一亠亠一一亠亠一亠一-氐gB先遍歷h鸚、雀通分量5!Lt；iniSpanTree_PEI法?.最小生inISpanTree_KEUSGA法Ii|g口口口g口口口口口口口口口口口口口g口口口口口口口口口口口口口口口E弁求最小生戒樹前請先求棄誦分量！慵選擇莢卑：a.先選0創(chuàng)建一個(gè)圖。b.選擇y繼續(xù)操作。c.按照菜單編碼選擇操作。七、體會與自我評價(jià)在做這個(gè)程序的時(shí)候你首先必須知道圖的一些概念，圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并

26、且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素（及其孩子結(jié)點(diǎn)）相關(guān)但只能和上一層中一個(gè)元素（即雙親結(jié)點(diǎn)）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。當(dāng)我們拿到一個(gè)圖時(shí)，我們對該圖的遍歷就要有一些方法，所以有了深度優(yōu)先遍歷和廣度優(yōu)先遍歷，我們要明白這兩種遍歷是怎么實(shí)現(xiàn)的，然后根據(jù)我們?nèi)四X中的方法把它寫成電腦算法。對一個(gè)圖我們還定義了連通分量，所以將圖存到電腦中時(shí)，我們對連通分量得有個(gè)算法。求圖的最小生成樹有兩種算法，普利姆是從結(jié)點(diǎn)出發(fā)尋找權(quán)最小的邊，知道所有結(jié)點(diǎn)都練通了；而克魯斯卡爾算法則是從邊出發(fā)，尋找使圖連通的權(quán)值最小邊的方法。算法的實(shí)現(xiàn)從人腦到電腦的轉(zhuǎn)

27、變是比較復(fù)雜的一件事，要求做到具體到實(shí)現(xiàn)該方法的每一個(gè)步驟，然后再將每一個(gè)步驟通過代碼實(shí)現(xiàn)。這要求我們要明確各個(gè)數(shù)據(jù)元素和個(gè)元素之間的關(guān)系，然后才能明確使用算法去調(diào)用這些數(shù)據(jù)。通過本次的課程設(shè)計(jì)，我對數(shù)據(jù)結(jié)構(gòu)有了一定的認(rèn)識，明白了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)，數(shù)據(jù)關(guān)系，及對其操作的方法。但同時(shí)也發(fā)現(xiàn)在自己有很多的不足，在使用語言和如何精煉語言需要進(jìn)行更多的訓(xùn)練。源代碼：#include#includeusingnamespacestd;#defineint_max10000/最大值staticintn=0；/全局變量，判斷有權(quán)圖和無權(quán)圖staticinto=0；/全局變量，清除BUGstaticintl=0

28、;/全局變量，清除BUG#defineinf9999/最小值的最大值#definemax20/最大頂點(diǎn)個(gè)數(shù)typedefintVRType,QElemType,Status；typedefcharInfoType,VertexType；/|鄰接矩陣|/鄰接矩陣定義typedefstructArcCellVRTypeadj；/VRType是頂點(diǎn)關(guān)系類型。對無權(quán)圖，用1或0表示相鄰否；對帶權(quán)圖,則為權(quán)值類型InfoType*info；/該弧相關(guān)信息的指針ArcCell,AdjMatrixmaxmax；typedefstructVertexTypevexsmax；/頂點(diǎn)向量AdjMatrixarcs

29、；/鄰接矩陣intvexnum,arcnum；/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)MGraph_L；/intlocalvex(MGraph_LG,charv)/返回V的位置inti=0；while(G.vexsi!=v)+i；returni；intcreatMGraph_L(MGraph_L&G)/創(chuàng)建圖用鄰接矩陣表示charv1,v2；inti,j,w；cout請輸入頂點(diǎn)和弧的個(gè)數(shù)endl；cinG.vexnumG.arcnum；cout輸入各個(gè)頂點(diǎn)endl；for(i=0；iG.vexnum；+i)cinG.vexsi；for(i=0；iG.vexnum；+i)for(j=0;jG.vexnum;+j)

30、G.arcsij.adj=int_max;G.=NULL;for(intk=0;kG.arcnum;+k)cout輸入一條邊依附的頂點(diǎn)和權(quán)endl；cinvlv2w；/輸入一條邊依附的兩點(diǎn)及權(quán)值i=localvex(G,vl)；/確定頂點(diǎn)VI和V2在圖中的位置j=localvex(G,v2)；G.arcsij.adj=w；G.arcsji.adj=w；for(i=0；i!=G.vexnum；+i)for(j=0；j!=G.vexnum；+j)if(G.arcsij.adj!=1&G.arcsij.adjint_max)n+=1；if(n=l)cout這是一個(gè)有權(quán)圖endl

31、；elsecout這是一個(gè)無權(quán)圖endl；cout圖G鄰接矩陣創(chuàng)建成功！endl；returnG.vexnum；voidljjzprint(MGraph_LG)/鄰接矩陣的輸出inti,j；if(n=0)for(i=0；i!=G.vexnum；+i)for(j=0；j!=G.vexnum；+j)if(G.arcsij.adj=int_max)cout0；elsecoutG.arcsij.adj；coutendl；elsefor(i=0；i!=G.vexnum；+i)for(j=0；j!=G.vexnum；+j)if(G.arcsij.adj二二int_max)cout8；elsecoutG.a

32、rcsij.adjadjvex=j；arc-nextarc=gra.verticesi.firstarc;gra.verticesi.firstarc=arc;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;cout圖G鄰接表創(chuàng)建成功！endl；return1;voidadjprint(ALGraphgra,MGraph_LG)/鄰接表輸出inti；for(i=0；i!=gra.vexnum；+i)ArcNode*p；couti,G.vexsi；p=gra.verticesi.firstarc；while(p!=NULL)cout-p-adjvex；p=p-ne

33、xtarc；cout-End；coutendl；/|/隊(duì)列定義typedefstructQNodeQElemTypedata；structQNode*next；QNode,*QueuePtr；typedefstructQueuePtrfront；/隊(duì)頭指針QueuePtrrear;/隊(duì)尾指針LinkQueue；/StatusInitQueue(LinkQueue&Q)/初始化隊(duì)列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)；if(!Q.front)return0；/存儲分配失敗Q.front-next=NULL;return1;StatusEnQu

34、eue(LinkQueue&Q,QElemTypee)/入隊(duì)，插入元素e為Q的新的隊(duì)尾元素QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode);if(!p)return0;/存儲分配失敗p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return1;StatusDeQueue(LinkQueue&Q,QElemType&e)/出隊(duì)，若隊(duì)列不空，則刪除Q的隊(duì)頭元素,用e返回，并返回真，否則假Q(mào)ueuePtrp;if(Q.front=Q.rear)return0;p=Q.front-next;e=p-data;Q.front-

35、next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return1;StatusQueueEmpty(LinkQueueQ)/判斷隊(duì)為空if(Q.front=Q.rear)return1;return0;/圖的遍歷intvisitedmax；/訪問標(biāo)記intwe;intfirstadjvex(ALGraphgra,VNodev)/返回依附頂點(diǎn)V的第一個(gè)點(diǎn)/即以V為尾的第一個(gè)結(jié)點(diǎn)if(v.firstarc!=NULL)returnv.firstarc-adjvex；intnextadjvex(ALGraphgra,VNodev,intw)/返回依附頂點(diǎn)V

36、的相對于W的下一個(gè)頂點(diǎn)ArcNode*p；p=v.firstarc；while(p!=NULL&p-adjvex!=w)p=p-nextarc;if(p-adjvex=w&p-nextarc!=NULL)p=p-nextarc;returnp-adjvex;if(p-adjvex=w&p-nextarc=NULL)return-10;/廣度優(yōu)先遍歷voidBFSTraverse(ALGraphgra)inti,e;LinkQueueq;for(i=0;i!=gra.vexnum;+i)visitedi=0;InitQueue(q);for(i=0;i!=gra.vexnum;+i)if(!vi

37、sitedi)visitedi=1;cout=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)visitedwe=1;coutgra.verticeswe.data;EnQueue(q,we);/深度優(yōu)先遍歷intDFS(ALGraphgra,inti)visitedi=1;intwe1;cout=0;we=nextadjvex(gra,gra.verticesi,we)we1=we;if(visitedwe=0)DFS(gra,we);we=we1;return1;intDFStra(ALGraphgra)inti,j;for(i=0;i

38、!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);return0;/求連通分量intDFSTraverse_fen(ALGraphgra)inti,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);coutendl;l+;return0;/最小生成樹的普利姆算法typedefstructintadjvex;intlowcost;closedge;intMiniSpan

39、Tree_PRIM(intgmax,intn)intlowcostmax,prevexmax；/lowcost存儲當(dāng)前集合分別到剩余結(jié)點(diǎn)的最小權(quán)值/prevex存儲最短路徑的前一個(gè)結(jié)點(diǎn)inti,j,k,min；for(i=2；i二n；i+)/n個(gè)頂點(diǎn)，n-1條邊lowcosti=g1i；/初始化prevexi=1；/頂點(diǎn)未加入到最小生成樹中l(wèi)owcostl=0；/標(biāo)志頂點(diǎn)1加入U(xiǎn)集合for(i=2；i=n；i+)/形成n-1條邊的生成樹min=inf；k=0；for(j=2；j=n；j+)/尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊if(lowcostjmin)&(lowcostj!=0)min=lowcostj；k=j；cout(prevexk-1,k-1)min；lowcostk=O；/頂點(diǎn)k加入U(xiǎn)for(j=2；j0)f=acrvisitedf;returnf;typedefstructacrintpre；/弧的一結(jié)點(diǎn)intbak；/弧另一結(jié)點(diǎn)intweight；/弧的權(quán)edg；voidMiniSpanTR