數(shù)據(jù)結(jié)構實驗報告四

1、甘肅政法學院本科生實驗報告()姓名：學院:專業(yè)：班級：13級實驗課程名稱:數(shù)據(jù)結(jié)構實驗日期:2014年5月30日指導教師及職稱：實驗成績：開課時間：2013-2014學年第二學期甘肅政法學院實驗管理中心印制實驗題目樹形結(jié)構小組合作否姓名班級學號一、實驗目的8.1實現(xiàn)圖的鄰接矩陣和鄰接表儲存8.2實現(xiàn)圖的遍歷算法8.3求所有深度優(yōu)先遍歷序列8.4用圖搜索方法求解迷宮問題8.5求有向圖的簡單路徑8.6求無向圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹8.7用普利姆算法求最小生成樹8.8釆用克魯斯卡爾算法求最小生成樹8.9釆用狄克斯特拉算法求有向帶權圖的最短路徑&10采用弗洛伊德算法求有向帶權圖的最短路徑.實

2、驗環(huán)境安裝了Windows7操作系統(tǒng)，并且安裝了MicrosoftVisualC+6.0。三、實驗內(nèi)容與步驟1、安裝MicrosoftVisualC+6.0。2打開MicrosoftVisualC+6.0!1!實驗過程:8.1實現(xiàn)圖的鄰接矩陣和鄰接表儲存編寫一個程序algo8-l,實現(xiàn)不帶權圖和帶權圖的鄰接矩陣與鄰接表的相互轉(zhuǎn)化算法、輸出鄰接矩陣與鄰接表的運算并在此基礎上設計一個主程序完成如下功能：（1）建立如圖所示的有向G鄰接矩陣，并輸出之；（2）由有向圖G的鄰接矩陣產(chǎn)生鄰接表，并輸出之；（3）再由（2）的鄰接表產(chǎn)生相應的鄰接矩陣，并輸出之reuwiNj：冷創(chuàng)建簫ni：作空円（bj廠廉加列期

3、工作空岡l從（KFroi：二J廠平臺舊:方一|門-*Win32新建工程l-ATLCOMAppWIzordraciuatcrRcfioufccTypeWi2ardSnCutomAppWiardProjectSISAPIExtensionWardMokefileDevStudioAddinWizord&Extended8wicdPrueWMadMFCActiveXControlWirdMFCAppWizard(dll|jcc筲Win32Application*nwin32ConooleApplicationWin32Dynomic-LInkUbrary?dVVin32StaticLibrary選擇

4、uHello,world!程序”您拔要創(chuàng)蹇什么類型的控制臺程序?一個空工程E)一個簡單的程序Q個-Hello,Worldf程序(W)一個支MFCfig序M選擇Fileview復制algo8-l和Graph到工程文件中。把主文件大開，用exp8-l的內(nèi)容覆蓋到主文件由于main()函數(shù)被重復定義所以需要備注，把algo8-1中主函數(shù)備注掉，并且手動引入#inchide“algo8l.cpp”。運行程序，如下圖：SC;TDebugJFF.exe1有向圖G的鄰接矩陣:05co7coco4053CO88888896053cococo10圖G的鄰接矩陣轉(zhuǎn)換戚鄰接表二0：131：22：053：254：35

5、：04圖G的鄰接表轉(zhuǎn)換成鄰接鄰陣,05CO?88cococococococoCOCOcoPressanyKeytocontinue輸入代碼如下:/婷子.cpp:DefinestheentrypointFortheconsoleapplicationttincludestdafx.h文件名:exp8-1.cppttincludettincludettinclude,Balgo8-1.cppexternexternexternexternuoidMatToList1(MGraptiALGraph*&);voidListTot1at1(ALGraph*,MGraph&);uoidDispMatl(M

6、Graph);uoldDispAdj1(ALGraph*);以下外部函數(shù)在goA1-cppvoidnainOinti,j；MGraphg,g1;ALGraph*G;intftMAXU6=0,5,INF,7,INF,INF,8,INF,0,INF,INF,9,INF,IHF,5,0fINF,6,3,INF,INF,INF,1,0；-g.n=6;g.e=10;建立圖中有向帶標圖G的鄰接矩陣for(i=0;ig.n;i+)For(j=0；jpWiznrd3Clunt:rClcnourccTypeWixMrdH5CustomAppWi?ard(ftDotoba&cProjedDcv3ludioAdd-

7、inWUord話ExtendedSlorodProcWizardAISAMExtensionWlrdrMakefile裾MFCActiveXConlrolWiard由MFCAppWi2ard(dll)KJMFCAppWi2ard(excjJsNrwDatsbaeWixardTlUtilityPfoicd為Win32Applicationnwin32ConooloApplication1Win32Dynomlc-LInkLlbvoryWin32SStlcLibrevyrew(N)：2tBCii9daiidaii7儀壑C：zhangdandan7e刨尬插的工作空冋Bl廣加伽御沛工件041閥L從KT

8、(O)：I_d平臺舊：*Win32選擇Hello,world!程序”您馥要創(chuàng)蹇什么類型的控制臺程序?srsin一個空工6(E)一個簡單的程序(S)Q個Hello,World嚴程序(W)個支持MFC的程序(M)選擇Fileview復制algo8-l和algo8-2和Graph到工程文件中。把主文件大開，用exp8-2的內(nèi)容覆蓋到主文件由于main()函數(shù)被重復定義所以需要備注，把algo8-1中主函數(shù)備注掉，并且手動引入#includet6algo8-l.cpp和#inchidealgo82cpp”。運行程序，如下圖:3-C:1222DebugL222.exe0:1C5)3C7)1:22：053

9、：2C5)5C6)4：35：0C34(1從頂點0開始的DFSC遞歸算法:012543從頂點0開始的dfsE遞歸算法從務上謠始鮎b；sIe遞歸算法013254Pressanykeytocontinue輸入代碼如下:ttincludeBlstdafx.h11ttincludettincludettincludealgoS-l.cppttincludeialgo8-2.cpptBexternuoidexternuoidexternuoidexternuoidexternuoidexternuoidMatToListl(MGraph9ALGraphDispfidj1(fiLGraph*G);DFS(A

10、LGraph*G,intu);DFSKALGraph*G,intv);DFS2(ALGraph*G,intu);BFS(ALGraph*G,intu);*&)；以下外部函數(shù)在alQ08-1.cpp中以下外部函數(shù)在al98-2卬卩中uoidnain()inti,j；MGraphg;fiLGraph*G;intAMAXU6=0,5,INF,7,INF,INF,(INF,0,4,INF,INF,INF,8,INF,0,INF,INF,9,INF,INF,5,0,INF,6,IHF,IHF,IHF,5,0,IHF,3,INF,INF,INF,1,0;_g-n=6;g-e=10;建立圖8.1中有向帶標圖

11、G的鄰接矩陣for(i=B;ig.n;i+)For(j=0;jg.n;j+)g.edgesij=fiij;G=(fiLGraph*)nalloc(5izeof(ALGraph);MatToListl(g,G)；圖G的鄰接矩陣轉(zhuǎn)換成鄰接表耐ntW圖G的鄰接表:冊)；DispAdj1(G)；prints從頂點研始的DFS(遞歸算法):中)；DFS(G)；printF(rT);PMintfC-頂點研始的DFS(非遞歸算法):n)；DFS1(G,fi);printf(-K頂點研始的BFS(非遞歸算法):W);BFS(G,0);pKintF(,inM);8.3求所有深度優(yōu)先遍歷序列編寫一個程序algo8

12、-3,釆用鄰接表存儲圖。新建工程文侔re|:r件區(qū)覽它文檔|占ATLCOMAppWizardTHCluntcrClcnourccTypeWixNrdiTICugtomAppWi?ard)選擇Hello,world!程序”您馥要創(chuàng)蹇什么類型的控制臺程序?一個空工程(E)一個簡單的程序Q個Hello,Worlds程序(W)一個支持MFC的程序(M選擇Fileview復制algo8-l和Graph到工程文件中。把主文件大開，用exp8-3的內(nèi)容覆蓋到主文件由于main()函數(shù)被重復定義所以需要備注，把algo8-1中主函數(shù)備注掉，并且手動引入#inchide“algo8l.cpp”。運行程序，如下圖

13、：3C:4Debug4.exe-圖G的鄰接表：0：134從嘯點1岀發(fā)的所有深度優(yōu)先序列:10324103421042310432i23041234012403i24301304213240Pressanykeytocontinue輸入程序如下:/置已訪間標記/如果已訪問所有頂點，則輸岀訪問序列/P指向頂點U的第一條弧的弧頭結(jié)點uisitedu=0;voidDFS(ALGraph*G,intu)ArcNode*p;visitedv=1;printFCdp=G-adjlistu.firstarc;while(p皆NULL)if(uisitedp-adjuex=8)DFS(G,p-adjuex);p

14、=p-nextarc;置已訪問禰記側(cè)鼬蠶喘節(jié)點/gp-adjuex頂點未訪間，遞歸訪間它卩指向頂點u的下一個邊節(jié)點ttincludestdafx.h文件名:exp8-3.cppttincludettincludettincludealgo8-1-cppexternuoidMatToList(MGraph,ALGraph*&);以下外部函數(shù)在algo8-1.cpp中externuoidDispAdj(ALGraph*);/intuisitedHAXV;voidDFSALL(fiLGraph*G,intu,intpath,intd)ArcNode*p;uisitedv=1;pathd=u;di;i

15、F(d=G-n)for(intk=0;kp=G-adjlistu.firstarc;while(p?=NULL)iF(uisltedp-adjuex=0)若p-adjuex頂點未訪|可,遞歸訪問它DFSALL(G9p-adjvex,path,d);p=p-nextarc;P指向頂點u的下一條觀的弧頭結(jié)點uisitedu=0;voidmain()intpathMAKU,i,j,u=1;MGraphg;ALGraph*G;g.n=5;g.e=8;intfiMAXUMAXU=8,1,8.1,1,1,8,8,1,0,1,1,1,1,1.0,1,1,0,1,1,0;for(i=0;ig.n;i*)建立教

16、程中圖8.1的鄰接矩陣For(j=0;jg.n;j+)g.edgesij=Aij;MatToList(g,G);for(i=0;i);8.4用圖搜索方法求解迷宮問題設計一個程序，實現(xiàn)如下功能:（1）建立教程所示港宮對應的鄰接表表示。（2）采用深度優(yōu)先遍歷輸出所有迷宮的路徑。新建工程Fll3|文命re|工帚區(qū)覽它文檔|4ATLCOMA4pWiznrdjCluntcrClcnourccTypeWixMrdTlCugtomAppWi?ardUtPDotobe&cProject$*Dcv3ludioAdd-inWlzoid強ExtendedSlorodProcWizardAISAMExtensionW

17、izardMakefile宙MFCActiveXConlrolWiard0MFCAppWi2ard(dllj0MFCAppWi2ard(excjNrwDatsbaceWizardT(UtilityProied宣Win32ApplicationnWin32ConooloApplicationWln?2Dynomlc4_lnkUbroryJWin32StaUcLibrevyrewiw)：.hongdondottWlO：C：zhangdandan7平臺舊:Win32選擇Hello,world!程序”您拔要創(chuàng)蹇什么類型的控制臺程序?一個空工程E)一個簡單的程序Q個Hello,Worldf程序(W)一個

18、支MFCfig序M選擇Fileview復制algo8-l和Graph到工程文件中。把主文件大開，用exp84的內(nèi)容覆蓋到主文件由于main()函數(shù)被重復定義所以需要備注，把algo8-l中主函數(shù)備注掉，并且手動引入#include4424Ji尸4444zkccc4434zkccc3C:：199DEbug199g333ccc3213333111222211各:-continues1234kany:*顯各kp血p-mmnfa..3.4店的宀呂宀呂宀呂宀呂4555555-1.采一卷米.一輸入程序如下:111ttincludestdafx.h文件名:exp8-4.cppttinclude

19、includettdefineMaxsize180ItdefineM4ttdefineN4以下定義鄰接表類型typedefstructfiNodeinti,j；structAHode*nextarc;鄰接表頭結(jié)點的類型指向第一條邊ArcNode;typedefstructUnodefircNode*Firstarc;VHode;typedefstructUHodeadjlistM*2N+2;ALGraph;111111typedefstruct111111intintBox;structBoxintdataMaxSize;length;PathType;intuisitedM*2N+2=0;i

20、ntcount=0;uoidCreateList(fiLGraph*&G,int建立迷宮數(shù)組對應的鄰接表G從磁曇類型ngN2Jinti,j,i1,j1,di;ArcHode*p;G=(ALGraph*)malloc(sizeoF(ALGraph);For(i=0；iM*2；i-)給鄰接表中所有頭節(jié)點的指針域置初值for(j=0;jH+2;j+)for(j=0;jadjlistij.Firstarc=HULL;for(i=1;i=M;i*+)/檢查呵中毎個元素For(j=1；j=N;j+)if(mgij=0)di=0;while(di4)switch(di)case0:i1=i-1;j!=j;b

21、reak;case1:i1=i;j1=j+1;break;case2:i1=i+1;ji=j;break;case3:i1=i,j1=j-1;break;if(ngi1j1=0)為可走方塊i=i1;p-j=j1；p-nextarc=G-adjlistij.Firstarc;/將叩節(jié)點鏈到鏈表后G-adjlistij.firstarc=p;di+;uoidDispAdjCALGraph*G)/輸岀鄰接表Cintij；ArcNode*p;for(i=0;iM+2;i+)for(j=0;jadjlistij.Firstarc;luhile(p?=NULL)printf(-(%(!,%d)1B,p-i

22、,p-j);p=p-nextarc;printF(-nBi);uoidFindPath(fiLGraph*G,intxi,intyi,intxe,intye,PathTypepatArcNode*p;uisitedxiyi=1；置已訪間標記path.datapath.length.i=xi;path.datapath.lengthj=yi;path.length*;iF(xi=xe&yi=ye)printF(,B迷宮路徑d:Bi,*+count);For(initk=8;kB);p=G-adjlig：txiyi.Fir5tarc;p指向頂點u的第一條邊頂點while(p?=NULL)ip-j=

23、0)/若(p-i,p-j)方塊未訪問，遞歸訪問它FindPath(G,p-i,p-j,xe9ye,pth);p=p-nextarc;/pfe向頂點u的下一條邊頂點迷宮數(shù)組輸出鄰接表ui5itedxiyi=8;ALGrapti*G;intngM*2H*2=1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,0,0,1,1,0,0,0,1,1,1,1,1,1,1,1；CreateList(G,mg);printFC-迷宮對危的鄰接表:n,B);Dispfidj(G);PathTypmpath;intF(”濟有苗迷宮路徑:W)；FindPath(G,1,1,M,N,path);8.5求有向圖

24、的簡單路徑編寫一個程序exp8-5,實現(xiàn)如下功能：（1）輸出所示的有線圖G從頂點5到頂點2的所有路徑:（2）輸出所示的有線圖G從頂點5到頂點2的所有長度為3的輕:輸出所示的有線圖G從頂點5到頂點2的最短路徑:新建工程WI3frewiNi：zliuii9liBdan7,C：zhangdandan7e剛尬插的工作空冋Bl於力1細前：r你空廠從T(Q)：Iz平臺舊：*Win32選擇Hello,world!程序”您馥要創(chuàng)蹇什么類型的控制臺程序?Bf?E3一個空工6(E)r一個簡單的程序(習個Hello,World嚴程序(W)個支持MFC的程序(M)選擇Fileview復制algo8-l和Graph到工

25、程文件中。把主文件大開，用exp8-5的內(nèi)容覆蓋到主文件由于main()函數(shù)被重復定義所以需要備注，把algo8-1中主函數(shù)備注掉，并且手動引入#includealgo8-1.cpp運行程序，如下圖：BC:3546Debug3546.eKe圖G的鄰接急0:131：2TOC o 1-5 h z2:053:254：35：0134|從頂點5到2的所有路徑：581250325125325432i從頂點弓到2的所有長度為3路徑二581250325432從頂點5到2的最短路徑；512Pressanykeytocontinue輸入代碼如下:ttincludestdaFx.h打文件名：Exp-5.cpptti

26、ncludettincludettincludeB,algo8-1-cppexternvoidMatToList(MGraph,ALGraph*&);externuoidDigpfidj(ftLGraph*);/intuisitedMAXU;/全局數(shù)組voidPathAlU(ALGraph*G,intuintu,intpath,inti輸岀圖呻從頂點u到u的所有簡單路徑ftrcNode*p;intj,n;ui5itedu=1;卩=G-adjlistu.Firstarc;P指向頂點皿的第一條邊while(p?=HULL)adjvex；為m的鄰接頂點if(n=u)pathi+1=u;For(j=0

27、;jnextarc;找的下一個鄰接頂點uisitedu=O;uoidPathA112(ALGraph*G,u,int1,intpath,intd)Kvrt*叵焙nJ瑤更、DIP膘咂護-聖蓋OIP躡峽昌偽汕、-V-oHrHanelrrEMlnbIrlFoumzefjnb=H【己d-Hs-HnIKdxS05i二lWIWLlegLIH4UOJU-4.5二fiXUldnh宀IrlludJBd4S二2n2r-14u-rMgA4占4Jon4ssisQH=n峽修爍、(【jmEdpuun蘭-rn41HJ*udm壽-lsmedzMOUS3匚-H旺撅1刪丘娠亙図埋s塩叵堆毎蠱、丄=pm砸國wASS

28、Ksn徑、*占和2LKdud二Elned二llJ)zlETUlnedZ叵灼E3S*叵溶居歸峽昌慳和、缶丄邑S3蕓峽亙鰹累岳n苓/7xe二DEAdNul21nN=id)QI-HU冷一j希4JS-H4=4STHPE人肆d宀zcrjzRUMd二ulns.pgzLtuTd半二亍二茜“匕莒4(IHHP比小n=Hn-IIMn丄巳edr+p-LH【=:4JH5nIKd*apohpuu二占pul隊非空則執(zhí)行qurear.parent=-1;uhile(rontrear)k=qu4=ront.uno;出隊lev=quFront.leuel;if(k=v)i=0;j=front;while(j?=-1)Mtiim

29、leu;找到頂點u,返回p=G-adjlistfk.Firstarc;while(p!=NULL)adjuex=O)若未訪問過adjuex;訪問過的鄰接點入隊qurearleuel=leu+1;qurea-parent=Front;p=p-nextarc；找頂點i的下一鄰接點return-1;如果未找到頂點j,返回一特殊值7uoidmain()inti,j;intu=5,u=2,d=3;intpathMAXU;MGraphg;AiLGraph*G;intAMAXU6=,g.n=6;g.e=10;For(i=0;ig.n;i*+)建立圖910的鄰接矩陣For(j=D;jg.n;j*+)g.edg

30、esij=Aij;G=(ALGraph*)malloc(sizeof(ALGraph);l1atToList(g,G);圖G的鄰接矩陳轉(zhuǎn)換成鄰接表printFC1圖G的鄰接表W)；OispAdj(G);For(i=O;ig.n;i+)uisitedi=0;printfCJA頂點卻到加的所有路徑：n-,u,v);path8=u;uisitedu=1;PathAll1(G,ufu,path,8);p廠intF(從預點卻到U的崩有長度為d路徑:XnBu,u,d);PathA112G,u,u,d,path,-|);printF(,ni,);For(i=O;ig.n;i*+)uisitedi=0;p廠i

31、ntFL從頂點知到燈的最短路徑：n-,u,u);For(i=O;ig.n;i+)uisitedi=0;j=ShortPath(G,u,v,path);For(i=8;i=j;i+)printfCSd-jpathfi);printfCAn);&6求無向圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹編寫一個程序algo8-2,輸出所示的有線圖G從頂點3出發(fā)深度優(yōu)先生成樹和廣度優(yōu)先生成樹。新建工程文命r|rtt=e覽它文4$|4ATLCOMAppWi2ardTHCiuntcrClcnourccTypeWixnrd53CuslomAppWi?ard宙DatableProjed$Dcv3ludiuAdd-inWlz

32、atd總ExtendedSlorodProcWizardAISAMExtensionWizardr：-Makefile&MFCActiveXConlrolWiard由MFCAppWi2ard(dll)0MFCAppWi2ard(excjjXNrwDstsbaeWizardT(UtilityPfoied為Win32Applicationnwin32ConooloApplicationIWin32Dynomlc-.lnkLlbroryJWin32SStlcLibrevyrew(Nj：zliungdaiBdaii7C：zhangdandan7a剛尬攝的工作空冋(Bl廣序如何汕I：件0冋閥L從T(Q)

33、：I丄平臺舊：*Win32選擇Hello,world!程序”您啤要創(chuàng)蹇什么類型的控制臺程序?一個空工程(E)一個簡單的程序Q個Hello,World?-程序(W)一個支持MFC的段序(M)選擇Fileview復制algo8-l和Gmph到工程文件中。把主文件大開，用exp8-6的內(nèi)容覆蓋到主文件由于main()函數(shù)被重復定義所以需要備注，把algo8-1中主函數(shù)備注掉，并且手動引入#includealgo8-1.cpp,9程運行序，如下圖：輸入程序如下:ttincludestdafx.h文件名:exp8-6.cppttincludettincludeitincludealgo8-1-cpp1e

34、xternuoidMJtToList(MGraph,fiLGraph關&);externuoidDispAdj(ALGraph*);/intuisitedfHAXUJ;uoidDFS(ALGraph*G,intu)全局數(shù)組ArcNode*p;visitedv=1;p=G-adjlistv.firstarc;while(p!=NULL)緒訥臨-條邊iF(uisitedp-a時若p-2djuox頂點未訪問，遞歸訪間它printf-,u,p-adjuex);輸出生成樹的一條邊DFS(G,p-adjuex);P指向頂點u的下一條邊ArcNode*p;intimtFor定義循環(huán)隊列并初始化voidBFS

35、(ALGraph*G,intu)queueMA2Uront=0,rear=fl;w,i；(i=8;in;i+)uisitedi=O;visitedv=1;rear=(rear+1)MAXU;queuerear=u;while(Front?=rear)front=(front*1)WAXU；Front=(front*1)%HAXU;w=queuefront;岀隊并賦結(jié)押p=G-adjlistw.firstarc;找與頂點兩馳第一個頂點while(p?=NULL)iF(uisitedp-adjuex=0)若當前鄰接頂點未被訪問printF(-ad,d-Mpadjuex);/輸岀生成枕|的一條邊ui

36、sitedp-adjuex=1;置該頂點己被詢可的標志rear=(rear+1)MAXU;該頂點進隊queuerear=p-adjuex;p=p-nextarc；我下一個鄰接頂點printf(iBnBi);uoidnain()inti,j；MCraphg;ALGraph*C;intfiMAXU11=0,1,1,1,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1.0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,fl,fl,fl,0,1

37、,1,1,fl,0,0,0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0；g.n=11;g.e=13;建立圖8.13的鄰接矩陣for(i=0;ig.n;i+)For(j=O;j);DispAdj(G);iiprin申圖G的鄰接表:W);DispAdj(G);printffXn-1)；For(i=0;ig.n;i+)visitedi=0;prints探度優(yōu)先生成樹叩)：ftFS(G,3);printfCn11);For(i=8;ig.n;i+)uisitedi=0;printfC

38、-J度優(yōu)先生成樹：J；BFS(G,3);printf(n);8.7用普利姆算法求最小生成樹編寫一個程序設計一個算法對所示無限帶權圖G,采用普利姆算法輸出從頂點0出發(fā)的最小生成樹新建工程nnm文命r|:r帚區(qū)覽它文檔JATLCOMAppWizardjCluntcrClcnourccTypeWixnrdiFICugtomAppWi?ardDotoba&cProjediDcv3tudiuAdd-inWUcvil能ExtendedSlorodProcWizardISAMExtensionWizardrpMakefile待MFCActiveXConlrolWiard宙MFCAppWi2ard(dll|S

39、JMFCAppWi2ard(excjNrwDtsbaccWizardTlUtilityPfojedXWin32Application二Win32ConooloApplicationWin32Dynomic-LInkLibraryWin32SttlcLibraryrewiN)：2liaii9daiidaii7ewici：C：zhangdandan7平臺舊：*Win32選擇Hello,world!程序”您馥要創(chuàng)蹇什么類型的控制臺程序?一個空re(E)一個簡單的程序(S)/V算舟,4J.2,3_-By05014o/3里邊邊邊邊邊普Pressanykeytocontinue輸入程序如下:ttinclu

40、destdaFu-h/文件名:exp8-7.cppitincludettincludeBialgo8-1.cppexternvoidDispMati(MGraph);外部函數(shù)在algo8-1-cpp中voidPrim(MGraptig,intu)intlowcostMAXU,nin,n=g.n;intclosestfMftXU,i,j,K；For(i=O;in;i+)給lowcostQclosest置初值lowcosti=g.edgesui;closesti=u;for(i=1;in;i*+)找岀nT個頂點min=INF;for(j=0；jn;j-)在(U-U)中找出離U最近的頂點kiF(lo

41、wcostj!=6&lowcostjmin)min=lowcostj;k=j;printF(IB邊(盅d麗)祓%:%dnIB,closestk9kvmln);lowcostk=0;標記k己經(jīng)加人UFor(j=0;jn;j+)修改數(shù)組lowcoctQclosestif(g.edgesfkj?=0&g.edgeskjlowcostj)lowcostj=g.edgeskj;clospstj=k;uoidnain()inti,j,u=3;MGraphg;intfiMfiXUMflXU=0,5,8,7,INF,3,5,0,1*,INF,INF,INF,INF,INF,INF,5,9,1,3,INF,9,

42、IHF,1,0;g.n=6;g.e=10;for(i=O;ig.n;i+)建立圖&億的鄰接矩陣for(j=0;jg-n;j*+)g.edgPSij=Aij;圖G的鄰接矩陣:W)；DispHat1(g);普里姆算法求解結(jié)果An-);Prin(g,O);HI8.8采用克魯斯卡爾算法求最小生成樹編寫一個程序所示無限帶權G,采用克魯斯卡爾算法輸出從頂點0出發(fā)的最小生成樹新建工程文侔re|:r件區(qū)覽它文檔|占ATLCOMAppWizardTHCluntcrClcnourccTypeWixNrdiTICugtomAppWi?ard)選擇Hello,world!程序”您馥要創(chuàng)蹇什么類型的控制臺程序?一個空工

43、程(E)一個簡單的程序Q個Hello,Worlds程序(W)一個支持MFC的程序(M選擇Fileview復制algo8-l和Graph到工程文件中。把主文件大開，用exp8-8的內(nèi)容覆蓋到主文件由于main()函數(shù)被重復定義所以需要備注，把algo8-1中主函數(shù)備注掉，并且手動引入#inchide“algo8l.cpp運行程序，如下圖：JBC;0Debug0.exeB圖G的鄰接矩陣0587cooocx3CO9CO3oo?coi0克魯斯卡爾算法求解結(jié)果0.5）：3CU2：43M5Pfcssanykeytocontinue輸入程序如下:酮鬆第V袈層、二UHnasn?*IJU-HHio*-二館uzh

44、asn蘭-rtusTUSra3Erapural?T4U-H?蘭-Hu蘭-hulli告D3二eJISFHDMon.H丄ybl+f-w/v二a宀掘險曹二sM-K豊責二zu丄T-二tzr3二！JLLJ*dule:l當：3M歸桓匕3|輕任?1:丄兇也悴皚-W叵Bw、二丄丄二匸中du亠二r=us26p26g二汽3二Hnia二Hnildu2bllx=lnsabpa5r*c-WVQHULo*(：w6yfQNifdulalA=W:U-Hllde3526pL!JtusP-Hon二A3Q.5-HQDIO*uxa皆p:34U-H:U-H4un4s4epaJdf4鬆瑪廉喘、6=UJXUHau-l-1l4-aMtdd:

45、rL80edDnEuntITO-HP4Sepnr-Hou-HltddT8l8dxd卯世収、S3M0CSfor(i=0;in;i+)useti=i;RT；k表示2j=0;中邊while(kn)曜遡驊寸的第幾條邊初值為生成的邊鳥柬職器齧Fm1=Ej.u;n2=Ej.u;sn1=usetml;sn2=vsetm2;if(sn1?=sn2)兩頂點屬寸printF(B,(Zd必d):盅drr.m,n2,Ej.w);.I八、I5|ZII丿一1k*+;for(i=0;in;i+)iF(useti=sn2)useti=sn1;sn1J*；掃描下一條邊voidnain()inti,j,u=3;MGraphg;E

46、dgeEMfiXE;intAMAXUMAXU=FS,O,J|5INF,INF,INF,8,4,0,5,INF,9,INF,INF,INF,5,0,1,；g.n=6;g.e=10;for(i=8;ig.n;i*+)建立圖816的鄰接矩陣For(j=8;jg.n;j+*)g.edgesij=Aij;SortEdge(g,E);printfC*圖G的鄰接矩陣:ArT)；DispMatl(g);printfC*#斯卡爾算法求解結(jié)果：n);Kruskal(E,g.n,g.e);printfCn11);8.9采用狄克斯特拉算法求有向帶權圖的最短路徑編寫一個程對所示無限帶權圖G,采用克魯斯卡爾算法輸出從頂點

47、0的最短路徑的長度和最短路徑。新建工程學st文侔re|:r件區(qū)覽它文檔|4ATLCOMAppWizardTHCluntcrClcnourccTypeWixNrd53CustomAppWi?ard)廠平feiei：*Win32選擇Hello,world!程序”您馥要創(chuàng)蹇什么類型的控制臺程序?一個空工程(E)一個簡單的程序Q個Hello,Worlds程序(W)r一個支持MFC的程序M選擇Fileview復制algo8-l和Graph到工程文件中。把主文件大開，用exp8-9的內(nèi)容覆蓋到主文件由于main()函數(shù)被重復定義所以需要備注，把algo8-1中主函數(shù)備注掉，并且手動引入#includeal

48、go8-1.cpp,9運行程序，如下圖：EC:654Debug654.exe-OD8ODCO2551133300000isenHHncxnknSn5n53S43597113.:5ff匱度度度1snscxnknnJnjnsnJn3L短_EH_8徑曰簪Bs簪販8nJ.B.B.B.B.B豆丄2345、QKh:到MiS到到0Ewt000003岀置笛%.7:|1?|期Pressanykeytocontinue輸入程序如下:ttincludestdaFx.h文件名:exp8-9.cppttincludettincludeB,algo8-1.cppdefineMfiXU180最丈頂點仝數(shù)externuoid

49、DispMatl(MGraphg);夕卜部曲數(shù)在.cpp中voidppath(intpath,inti,intu)intk;k=pathi;if(k=u)return;ppath(path,k,u);printfCd,3k);uoidDisPath(intdist,intpath,ints,intn,intu)inti；printfCBpath:);輸岀path值For(i=0;in;i+)printf(Bi%3dlpathi);printf(iBXn,B);For(i=0;in;i+)if(si=1)iF(ir=u)Printf(-從d到初的最短路徑長度為瑰dt路徑為：,u,i7disti)

50、;printf(d,u);ppatti(path丄uj;printfC.dn,i);elseprintFC-從盅d到盅d不存在路徑nBB,u,i);uoidDijkstra(MCraphg,intv)intdistMAXU,patht1fiXU;intsMftXU;intmindis,i3j,u,n=g.n;斶蟹化一II0For(i=0;in;i+*)disti=g.edgesui;si=6；u=-1;for(j=0;jn;j*)選取不在s中且具有最小距離的頂點uiF(5j=0&distjmindis)u=j;mindis=distj;5U=1；for(j=0；jn;j*)修改不在s申的頂點的

51、距離IF(sj=0)if(g.edgesujINF&distu+g.edgesujuoidnain()inti,j,u=0;MGraphg;intRMAKU6=5,INF,7,INF,INF,INF,INF,5,0,INF,6,；g.n=6;g.e=10;For(i=0;ig.n;i*+)建立圖&的鄰接矩陣g.edgesij=Aij;Printf(-pWi2nrd37)Clut)：Id平臺舊：*Win32選擇Hello,world!程序”您啤要創(chuàng)蹇什么類型的控制臺程序?一個空工程(E)一個簡單的程序Q個Hello,World廠程序(W)1一個支持MFC的程序(M|選擇Fileview復制algo8-l和Graph到工程文件中。把主文件大開，用exp8-10的內(nèi)容覆蓋到主文件。由于main()函