1、數據結構課程設計題目：城市通信網絡建設系統班級:*姓名:*指導教師:AAAAAAAAA完成日期：2015年6月13日1 .需求分析1.1 問題描述通信設施的安全保障是安全生產管理工作的一項重要內容。隨著通信網絡的不斷擴大和各種先進的通信方式日益增多相應的通信設施也在快速擴展，在不同的環境、不同的地域受到各種客觀條件的影響和破壞(包括自然因素和人為因素)以及通信設施在使用過程中的老化都會對全程全網的通信質量造成不同程度的影響。因此，采用通信設施安全保障計算機管理系統實現全區通信設施的集中管理，對保障通信設施安全，提高維護工作效率，及時發現與處理隱患問題，增強抵抗災害能力，特別是在實現管理工作的系

2、統化、正規化、規范化方面是非常必要的。如何在最小的經濟條件下達到利益最大化，是所有公司、企業已經政府部門一直所探討和解決的問題。對于城市通信管理系統來說，若要在n個城市之間建設通信網絡，只需要架設n-1條通信線路即可，建立最小生成樹即能實現以最低的經濟代價建設這個通信網。1.2 基本任務通過用戶調查分析及實際需求，系統需要實現如下基本任務：(1)在紙上模擬設計n個城市的網絡平面圖，城市數不少于20個，相同的的城市數不少于2(n-1),頂點表示各城市，邊表示城市間的距離；(2)編寫算法，求解最小代價通信網絡；(3)輸出該通信網絡中各邊及其權值；n個城市間的線路連接屬于圖的結構，要構建最經濟的通信

3、網絡，即是構建圖的生成樹。把城市間的線路關系看成是圖。城市間的距離即是圖的權值。利用prim算法或kruskal算法即可求出最小生成樹。2 .概要設計為了完成需求分析的基本任務，主要從以下3個方面進行設計：2.1 主界面設計為了使程序界面更加友好，建立了interface函數和choice函數，即歡迎界面以及實現用戶可以按數字鍵選擇相應的功能。歡迎界面如下圖:CAUwr<AdnnjniitF«tarXDektcpk生成樹的應月通值網余建向可超Uersionl，.d*附謂輸入場尊遺悻的信用口*2.2 數據結構設計若要在n個城市之間建設通信網絡，只需要架設n-1條通信線路即可。所以

4、，將一個現實的經濟問題，轉變為一個求最小生成樹的問題。本系統軟件采用經典算法prim算法和kruskal算法實現求最小生成樹，從而獲取最經濟的通信路徑。2.3 系統功能設計系統建立了interface函數和choice函數，其功能如下：(1) interface函數：使用戶更清晰看到程序的主體，使得程序界面更為直觀。程序如下：voidinterface。/初始界面printf("n");printf("最小生成樹的應用n");printf("通信網絡建設問題n");printf("Made-By董卓琴Version1.0n&

5、quot;);printf("n");printf("n");printf("n");printf("n"printf("n");printf("1.輸入通信網絡基本信息并將信息存儲到文件中n");printf("2.將網絡基本信息顯示到屏幕上n");printf("3.用kruskal算法算出最短路徑，并將結果存儲到文件中n");printf("4.用prim算法算出最短路徑，并將結果存儲到文件中n");print

6、f("5.退出n");printf("n");printf("n");printf("ttt請輸入您要選擇的選項(1-5):n");(2) choice函數：為用戶提供了方便，用戶可以通過按數字鍵來選擇相應的功能。程序如下：voidchoice()/控制選項函數MGraphG=MGraph();intc;interface。；std:cin>>c;while(c)switch(c)case1:system("cls");system("color1b");prin

7、tf("n");printf("ntt*歡迎使用*");Welcom_to_Use");printf("n*");printf("n");printf("n");printf("n");G=SaveGraph(G);system("cls");interface();/system("PAUSE");std:cin>>c;continue;case2:system("cls");system(&

8、quot;color1c");printf("n");printf("ntt*歡迎使用*");printf("nWelcom_to_Use");printf("n*printf("n*");printf("n");printf("ttt下面顯示的是通信網絡的基本信息n");printf("n");G=SaveGraph(G);G=print(G);printf("nttt按任意鍵返回n");c=getchar();c

9、=getchar();system("cls");interface();/system("PAUSE");std:cin>>c;continue;case 3:system("cls");system("color1e");歡迎使用*");Welcom_to_Use");printf("n");printf("ntt*printf("nprintf("n*");printf("n");printf(&q

10、uot;n");printf("n");G=SaveGraph(G);prim(G,G.vexs0);printf("tt*結果存入KruskalResult.dat中，按任意鍵返回*n'');c=getchar();c=getchar();system("cls");interface();system("PAUSE");std:cin>>c;continue;case 4:system("cls");system("color1d");歡迎使用

11、*");Welcom_to_Use");printf("n");printf("ntt*printf("nprintf("n*");printf("n");printf("n");printf("n");G=SaveGraph(G);G=kruskal(G);printf("tt*結果存入PrimResult.dat中，按任意鍵返回*n'');c=getchar();c=getchar();system("cls&quo

12、t;);interface();system("PAUSE");std:cin>>c;continue;case 5:return;)3.模塊設計3.1 模塊設計系統主要包含主程序模塊和其它操作模塊。其調用關系如下圖所示。(l)CreateGraph(G);/創建圖模塊(2)SaveGraph(G);/存儲圖模塊(3)Print(G);/輸出圖模塊(4)Kruskal(G);/kruskal算法求最小生成樹模塊Kruskal算法的基本思想是：1 、若網絡G的邊數en1,則G即為所求的最小生成樹，否則，一定有e>n-1.2 、將網絡的e條邊按權值自小到大順序

13、排列。3 、將網絡G中的邊都去掉，只留下n個孤立頂點作為初始的最小生成樹T,再按邊的排放順序逐個考察，若與當前E(T)中的邊不構成圈，便將它加入到邊集E(T),直至E(T)中邊數滿n-1為止。(5)Prim(G);/prim算法求最小生成樹模塊Prim算法是另一種求最小生成樹的方法，它的基本思想是按權值局部最小逐次將頂點和邊加入到T中，直至V(T)，黃n個頂點為止。Prim算法步驟為：1、設最小生成樹T的V(T)和E(T)均為空。2、從頂點集V(G)中任取一頂點加到頂點集V(T)中。3、在與V(T)中各頂點相關的所有邊中，取一條權值最小的邊(Vi,Vj)，其中，Vi包含于V(T),Vj包含于V

14、(T)。4、(Vi,Vj)加入到E(T)中，將頂點Vj加入到V(T)中。5、若V(T)已滿n個頂點，則算法終止，否則轉步驟(3)。3.3系統模塊之間的調用關系系統的5個子模塊之間的主要調用關系如下圖所示:系統采用鄰接矩陣存儲信息，定義如下：/圖的數據結構typedefstructMGraph/建立圖(MGraph()(memset(vexs,0,MAX_VERTEX_NUM);)VertexvexsMAX_VERTEX_NUM;/城市名稱intAdjMatrixarcs;/網絡條數intvexnum;/圖的當前頂點數(城市總數)intarcnum;/圖的當前弧數(網絡總數)MGraph;/記錄

15、從頂點集U到V-U的代價最小的邊的輔助數組定義typedefstructTemp/輔助數組(Temp()(lowcost=0;Vertexadjvex;/當前點intlowcost;/權值closedgeMAX_VERTEX_NUM;typedefstructCityNumberCityNumber()memset(cityNam,0,1024);charcityNam1024;CityNum;CityNum*Hometown=newCityNum20;/若G中存在頂點u,則返回該頂點在圖中位置；否則返回-1。#include<stdio.h>intLocateVex(MGraph

16、G,Vertexu)inti;for(i=0;i<G.vexnum;+i)if(strcmp(u,G.vexsi)=0)returni;return-1;4.2系統主要模塊設計4.2.1 CreateGraph函數1)創建鄰接矩陣以存儲圖的內容。4.2.2 )填充矩陣，即輸入城市間網絡的狀況，以方便使用prim算法或kruskal算法求出最經濟的架設方法。程序如下：/采用數組(鄰接矩陣)表示法，構造無向網GoMGraphCreateGraph(MGraph&G)inti=0,j=0,k=0,w=0;Vertexva,vb;/路徑的兩個節點printf("nntt*建立城

17、市間網絡信息*");printf("請輸入城市的總數：n");scanf("%d",&G.vexnum);printf("請輸入城市間的網絡數：n");scanf("%d",&G.arcnum);printf("請輸入d個城市的名稱(<%d個字符):n",G.vexnum);for(i=0;i<G.vexnum;+i)/構造頂點向量scanf("%s",G.vexsi);for(i=0;i<G.vexnum;+i)/初始化鄰接矩陣f

18、or(j=0;j<G.vexnum;+j)G.arcsij=65535;/65535為無窮大printf("請輸入d條網絡的兩個城市信息城市1和城市2的距離（以空格作為間隔）:n",G.arcnum）;/輸入城市1城市2名稱及其距離/定位權值位置對稱for(k=0;k<G.arcnum;+k)(scanf("%s%s%d",va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G.arcsij=G.arcsji=w;/returnG;4.2.3 SaveGraph函數1)為了避免每次都重復輸入信息

19、，用文件存儲圖的內容。2 )如果沒有文件則建立文件，并把圖的內容存儲到文件中。3 )如果文件存在，則從文件中讀取圖的內容到內存，以便完成其他操作。程序如下：MGraphSaveGraph(MGraphG)/輸入內容存儲在smalltree.dat(inti,j;FILE*fp;fp=fopen("smalltree.dat","rt");if(fp=NULL)(G=CreateGraph(G);fp=fopen("smalltree.dat","wt");fprintf(fp,"%dn",G.v

20、exnum);/存城市樹fprintf(fp,"%dn",G.arcnum);/存網絡數for(i=0;i<G.vexnum;+i)fprintf(fp,"%stn",G.vexsi);存城市名稱for(i=0;i<G.vexnum;+i)存儲鄰接矩陣for(j=0;j<G.vexnum;+j)if(G.vexsi=G.vexsj)(G.arcsij=0;/到它自己fprintf(fp,"%s_%s_%dn",G.vexsi,G.vexsj,G.arcsij);else(fprintf(fp,"%s_%s_

21、%dn",G.vexsi,G.vexsj,G.arcsij);rewind(fp);std:cout<<"存儲成功！。輸入任意鍵返回."<<std:endl;charc=getchar();)else/從文件中讀取網的信息存到內存中printf("tt*正在讀取文件中*n");fscanf(fp,"%dn",&G.vexnum);fscanf(fp,"%dn",&G.arcnum);chartempBuffer1024;memset(tempBuffer,0,102

22、4);for(i=0;i<G.vexnum;+i)(fgets(tempBuffer,1023,fp);strcpy(Hometowni.cityNam,tempBuffer);)charCityA1024;intLenth=0;memset(CityA,0,1024);for(i=0;i<G.vexnum;+i)for(j=0;j<G.arcnum;+j)(fscanf(fp,"%s",&CityA);intn=0;chartempCityName1024;memset(tempCityName,0,1024);while(CityAn!=

23、9;_')(tempCityNamen=CityAn;n+;)strcpy(G.vexsi+G.vexnum,tempCityName);n+;memset(tempCityName,0,1024);intnum=0;while(CityAn!='_')(tempCityNamenum=CityAn;n+;num+;)strcpy(G.vexsi+G.vexnum+1,tempCityName);intnumint=0;n+;memset(tempCityName,0,1024);while(CityAn!='0')(tempCityNamenumint

24、=CityAn;n+;numint+;intX=1;Lenth=0;for(n=numint-1;n>=0;n-)(intintkeynum=0;switch(tempCityNamen)(case'0':intkeynum=0;break;case'1':intkeynum=1;break;case'2':intkeynum=2;break;case'3':intkeynum=3;break;case'4':intkeynum=4;break;case'5':intkeynum=5;brea

25、k;case'6':intkeynum=6;break;case'7':intkeynum=7;break;case'8':intkeynum=8;break;case'9':intkeynum=9;break;)Lenth+=intkeynum*X;X=X*10;)G.arcsij=Lenth;printf("tt*讀取成功.t*n");)fclose(fp);returnG;4.2.3 print函數Print函數完成輸出功能，將內存中圖的內容輸出到屏幕上程序如下：MGraphprint(MGraphG)/

26、將輸入的網絡基本信息打到屏幕上inti,j;printf("城市總數：dt",G.vexnum);printf("網絡條數：dn",G.arcnum);printf("城市名稱：tn");for(i=0;i<G.vexnum;i+)/printf("%s_",G.vexsi);std:cout<<Hometowni.cityNam;)printf("n");printf("各個城市間的距離：n");printf("n");printf(&

27、quot;n");for(i=0;i<G.vexnum;+i)for(j=0;j<G.vexnum;+j)printf("%s_%s_距離:%d公里n",G.vexsi+G.vexnum,G.vexsj+G.vexnum,G.arcsij);std:cout<<"輸入任意鍵返回."<<std:endl;charc=getchar();returnG;4.2.4 kruskal函數用kruskal算法求出最小生成樹，即最經濟的假設方案程序如下：MGraphkruskal(MGraphG)/結果存儲在Kruska

28、lResult.dat(intsetMAX_VERTEX_NUM,i,j;intk=0,a=0,b=0,min=G.arcsab;FILE*ffp;ffp=fopen("KruskaiResult.dat","wt");for(i=0;i<G.vexnum;i+)seti=i;printf("最短網絡路徑為：n");while(k<G.vexnum-1)(for(i=0;i<G.vexnum;+i)/從G.arcsij中找到權值最小的for(j=i+1;j<G.vexnum;+j)if(G.arcsij<

29、min)(min=G.arcsij;/min中存最小權值a=i;b=j;if(seta!=setb)/如果a和b值不同則輸出(printf("%s-%st距離:dn",G.vexsa,G.vexsb,G.arcsab);輸出生成樹各邊fprintf(ffp,"%s-%sn",G.vexsa,G.vexsb);k+;for(i=0;i<G.vexnum;i+)/輸出后變成相同值，下次將不會輸出if(seti=setb)seti=seta;min=G.arcsab=G.arcsba=65535;輸出過的權值變為最大值rewind(ffp);fclose

30、(ffp);returnG;4.2.5prim函數用prim算法求出最小生成樹，即最經濟的假設方案程序如下：/用普里姆算法從第u個頂點出發構造網G的最小生成樹T,輸出T的各條邊voidprim(MGraphG,Vertexu)/inti,j,k=0;closedgeclose;FILE*fpp;fpp=fopen("PrimResult.dat","wt");k=LocateVex(G,u);for(j=0;j<G.vexnum;+j)/strcpy(closej.adjvex,u);closej.lowcost=G.arcskj;結果存儲在Pri

31、mResult.dat輔助數組初始化)closek.lowcost=0;/printf("最短網絡路徑為for(i=1;i<G.vexnum;+i)k=minimum(G,close);/初始,U=u:n");選擇其余G.vexnum-1個頂點求出T的下一個結點：第K頂點printf("(%s-%s)n",closek.adjvex,G.vexsk);fprintf(fpp,"%s-%sn",closek.adjvex,G.vexsk);/closek.lowcost=0;/第K頂點并入U集for(j=0;j<G.vexn

32、um;+j)if(G.arcskj<closej.lowcost)/strcpy(closej.adjvex,G.vexsk);closej.lowcost=G.arcskj;rewind(fpp);fclose(fpp);輸出生成樹的邊新頂點并入U集后重新選擇最小邊5 .調試分析系統主界面運行如圖1所示。各子功能測試運行結果如下運行程序，出現歡迎界面，見下圖：_C:UsersAdrri4ni«rfltorD«ktcpl;可.。算。S小生防樹的應用信網落履逸回墨"ttAdcBy”：'JereLonl保皿W出魯®由退一.二屏可徑明想一住軍手翻

33、更儲存名金幣中5.1城市間網絡信息的建立Welcon_to_Use*建立城市間網絡信息*請輸入城市的總數:多輸入城市間的網絡數;請輸入5個城市的名稱<<10個字符）：NJUXSHSZCZ請輸入6條網絡的兩個城市信息城市1和城市2的距離以空格作為間隔,：NJUX125UXSH468SHSZ523SZCZ256CZNJ154MSZ296Md*用*5.2顯示通信網絡的基本信息IC:UsersAclministratorDesk±opkc5ji.exeWelcon_to_UseF面顯示的是通信網絡的基本信息*讀取成功，-網絡條數:6terfi.E城一*正tt讀取文件中.一tHHH

34、HHHHHHM悒個燈三間的距離:號耳一huj'ts5竺433ISA555ZA2550166s離離離離5=n-n-n_J二二Dt-XHzzw-s-s-c-MWIC:UsersAdiministratorDesktopkc5j.exeB-rAlAtnrl/-z/'zlA8-6-Z469042B-B-B-B-rAL>TnH耳ZJ7-Z5B-B-B-B-B二3mrlmrlmrlmrlmrl51.-TlAL'AlA-l-A5*1za124-b0flu-0nu0離離離離離離離離離離離離離離離離離離離離離離III巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨隹ssssssssss

35、sssssssssssS音U意鍵返回6 .用戶使用說明1、運行程序，出現歡迎界面；2、按1進入輸入系統，如果文件沒有存儲城市網絡內容，則由用戶從鍵盤讀入，讀入后自動保存到文件中，按任意鍵即可返回歡迎界面；3、如果文件內已經存儲了城市網絡內容，則顯示文件已保存到文件中，按任意鍵返回；4、輸入2可以在屏幕上輸出存儲在文件內的城市間網絡信息，顯示完畢后按任意鍵可返回歡迎見面；5、按3和4分別可實現kruskal算法和prim算法求出最小生成樹，即最低經濟代價建設通信網絡（距離最短的最經濟），顯示完畢后按任意鍵返回歡迎界面；6、按5退出程序。7 .參考文獻數據結構理論與實踐楊永斌（核心算法prim算法

36、以及kruskal算法來源于此）數據結構（C語言）實踐教程胡元義數據結構嚴蔚敏、吳偉民«VisualC+課程設計案例精選與編程指導陳清華、朱紅8 .對所設計的軟件進行自我評價，如創新點、未解決的問題等情況說明：1、對圖的邏輯結構及存儲結構有了更深刻的認識；2、對prim算法和kruskal算法亦有了更深刻的認識；3、了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力，深入了解了模塊化的程序設計步驟；4、kruskal算法應該用堆排序然后再找路徑，但未能實現；5、輸入方面如果沒有將網絡信息存入文件，由鍵盤輸入信息時，如果手誤輸錯了無法更改，只能重新輸入，而且如果輸入中文，

37、最后顯示時會出現亂碼，只能用英文輸入；6、kruskal算法的實現仍有問題，結果存在錯誤，而且只能實行到第三步，到第四步時會出現程序關閉的提醒；9、程序源代碼：#include<stdlib.h>#include<string.h>#include<iostream>#defineMAX_VERTEX_NUM20最大頂點個數#defineMAX_NAME3/頂點字符串的最大長度+1typedefintintAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefcharVertexMAX_NAME;鄰接矩陣的數據結構/圖的數

38、據結構typedefstructMGraph/建立圖MGraph()memset(vexs,0,MAX_VERTEX_NUM);VertexvexsMAX_VERTEX_NUM;/城市名稱intAdjMatrixarcs;/網絡條數intvexnum;/圖的當前頂點數(城市總數)intarcnum;/圖的當前弧數(網絡總數)MGraph;/記錄從頂點集U到V-U的代價最小的邊的輔助數組定義typedefstructTemp/輔助數組Temp()lowcost=0;Vertexadjvex;/當前點intlowcost;/權值closedgeMAX_VERTEX_NUM;typedefstruc

39、tCityNumberCityNumber()memset(cityNam,0,1024);charcityNam1024;CityNum;CityNum*Hometown=newCityNum20;/若G中存在頂點u,則返回該頂點在圖中位置；否則返回-1。#include<stdio.h>intLocateVex(MGraphG,Vertexu)inti;for(i=0;i<G.vexnum;+i)if(strcmp(u,G.vexsi)=0)returni;return-1;/采用數組(鄰接矩陣)表示法，構造無向網GoMGraphCreateGraph(MGraph&am

40、p;G)inti=0,j=0,k=0,w=0;Vertexva,vb;/路徑的兩個節點printf("nntt*建立城市間網絡信息*");printf("請輸入城市的總數：n");scanf("%d",&G.vexnum);printf("請輸入城市間的網絡數：n");scanf("%d",&G.arcnum);printf("請輸入d個城市的名稱(<%d個字符):n",G.vexnum);for(i=0;i<G.vexnum;+i)/構造頂點向量

41、scanf("%s",G.vexsi);for(i=0;i<G.vexnum;+i)/初始化鄰接矩陣for(j=0;j<G.vexnum;+j)G.arcsij=65535;/65535為無窮大printf("請輸入d條網絡的兩個城市信息城市1和城市2的距離(以空格作為間隔):n",G.arcnum);for(k=0;k<G.arcnum;+k)scanf("%s%s%d",va,vb,&w);/輸入城市1城市2名稱及其距離i=LocateVex(G,va);/定位權值位置j=LocateVex(G,vb);

42、G.arcsij=G.arcsji=w;/對稱returnG;MGraphSaveGraph(MGraphG)/輸入內容存儲在smalltree.datinti,j;FILE*fp;fp=fopen("smalltree.dat","rt");if(fp=NULL)(G=CreateGraph(G);fp=fopen("smalltree.dat","wt");fprintf(fp,"%dn",G.vexnum);/存城市樹fprintf(fp,"%dn",G.arcnum)

43、;存網絡數for(i=0;i<G.vexnum;+i)fprintf(fp,"%stn",G.vexsi);/存城市名稱for(i=0;i<G.vexnum;+i)/存儲鄰接矩陣for(j=0;j<G.vexnum;+j)if(G.vexsi=G.vexsj)(G.arcsij=0;/到它自己G.arcsij);G.arcsij);fprintf(fp,"%s_%s_%dn",G.vexsi,G.vexsj,else(fprintf(fp,"%s_%s_%dn",G.vexsi,G.vexsj,rewind(fp);

44、std:cout<<"存儲成功！。輸入任意鍵返回."<<std:endl;charc=getchar();else/從文件中讀取網的信息存到內存中printf("tt*正在讀取文件中*n");fscanf(fp,"%dn",&G.vexnum);fscanf(fp,"%dn",&G.arcnum);chartempBuffer1024;memset(tempBuffer,0,1024);for(i=0;i<G.vexnum;+i)(fgets(tempBuffer,10

45、23,fp);strcpy(Hometowni.cityNam,tempBuffer);charCityA1024;intLenth=0;memset(CityA,0,1024);for(i=0;i<G.vexnum;+i)for(j=0;j<G.arcnum;+j)(fscanf(fp,"%s",&CityA);intn=0;chartempCityName1024;memset(tempCityName,0,1024);while(CityAn!='_')tempCityNamen=CityAn;n+;strcpy(G.vexsi+G

46、.vexnum,tempCityName);n+;memset(tempCityName,0,1024);intnum=0;while(CityAn!='_')tempCityNamenum=CityAn;n+;num+;strcpy(G.vexsi+G.vexnum+1,tempCityName);intnumint=0;n+;memset(tempCityName,0,1024);while(CityAn!='0')tempCityNamenumint=CityAn;n+;numint+;intX=1;Lenth=0;for(n=numint-1;n>

47、=0;n-)intintkeynum=0;switch(tempCityNamen)case'0':intkeynum=0;break;case'1':intkeynum=1;break;case'2':intkeynum=2;break;case'3':intkeynum=3;break;case'4':intkeynum=4;break;case'5':intkeynum=5;break;case'6':intkeynum=6;break;case'7':intk

48、eynum=7;break;case'8':intkeynum=8;break;case'9':intkeynum=9;break;Lenth+=intkeynum*X;X=X*10;G.arcsij=Lenth;printf("tt*讀取成功t*n");fclose(fp);將輸入的網絡基本信息打到屏幕上returnG;MGraphprint(MGraphG)/inti,j;printf("城市總數：dt",G.vexnum);printf("網絡條數：dn",G.arcnum);printf(&qu

49、ot;城市名稱：tn");for(i=0;i<G.vexnum;i+)/printf("%s_",G.vexsi);std:cout<<Hometowni.cityNam;printf("n");printf("各個城市間的距離:n");printf("n");printf("n");for(i=0;i<G.vexnum;+i)for(j=0;j<G.vexnum;+j)printf("%s_%s_距離：d公里n",G.vexsi+G.

50、vexnum,G.vexsj+G.vexnum,G.arcsij);std:cout<<"輸入任意鍵返回."<<std:endl;charc=getchar();returnG;MGraphkruskal(MGraphG)/結果存儲在KruskalResult.datintsetMAX_VERTEX_NUM,i,j;intk=0,a=0,b=0,min=G.arcsab;FILE*ffp;ffp=fopen("KruskaiResult.dat","wt");for(i=0;i<G.vexnum;i+)s

51、eti=i;printf("最短網絡路徑為:n");while(k<G.vexnum-1)for(i=0;i<G.vexnum;+i)/從G.arcsij中找到權值最小的for(j=i+1;j<G.vexnum;+j)if(G.arcsij<min)min=G.arcsij;/min中存最小權值a=i;b=j;if(seta!=setb)/如果a和b值不同則輸出printf("%s-%st距離:dn",G.vexsa,G.vexsb,G.arcsab);輸出生成樹各邊fprintf(ffp,"%s-%sn",G

52、.vexsa,G.vexsb);k+;for(i=0;i<G.vexnum;i+)/輸出后變成相同值，下次將不會輸出if(seti=setb)seti=seta;輸出過的權值變為最大值min=G.arcsab=G.arcsba=65535;/)rewind(ffp);fclose(ffp);returnG;)/求closedge結構體中lowcost的最小正值intminimum(MGraphG,closedgeclose)inti=0,j,k,min;while(!closei.lowcost)i+;min=closei.lowcost;/第一個不為0的值k=i;for(j=i+1;j

53、<G.vexnum;j+)if(closej.lowcost>0&&min>closej.lowcost)min=closej.lowcost;k=j;)returnk;)/用普里姆算法從第u個頂點出發構造網G的最小生成樹輸出T的各條邊voidprim(MGraphG,Vertexu)/結果存儲在PrimResult.dat中inti,j,k=0;closedgeclose;FILE*fpp;fpp=fopen("PrimResult.dat","wt");k=LocateVex(G,u);for(j=0;j<G.

54、vexnum;+j)/輔助數組初始化strcpy(closej.adjvex,u);closej.lowcost=G.arcskj;)closek.lowcost=0;/初始,U=uprintf("最短網絡路徑為：n");for(i=1;i<G.vexnum;+i)/選擇其余G.vexnum-1個頂點k=minimum(G,close);/求出T的下一個結點：第K頂點printf("(%s-%s)n",closek.adjvex,G.vexsk);fprintf(fpp,"%s-%sn",closek.adjvex,G.vexs

55、k);/輸出生成樹的邊closek.lowcost=0;/第K頂點并入U集for(j=0;j<G.vexnum;+j)if(G.arcskj<closej.lowcost)/新頂點并入U集后重新選擇最小邊strcpy(closej.adjvex,G.vexsk);closej.lowcost=G.arcskj;rewind(fpp);fclose(fpp);voidinterface()/初始界面printf("n");printf("最小生成樹的應用n");printf("通信網絡建設問題n");printf("Made-By啦啦啦Version1.0n");printf("n");printf(&