最小生成樹問題

1、榆林學(xué)院12屆課程設(shè)計最小生成樹問題課程設(shè)計說明書學(xué)生姓名:趙佳t=r.號:12系:信息工程學(xué)院業(yè):計算機科學(xué)與技術(shù)級:計14本1指導(dǎo)教師: 答辯時間:最小生成樹問題問題陳述最小生成樹問題設(shè)計要求：在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟的架 設(shè)方法。存儲結(jié)構(gòu)采用多種。求解算法多種。需求分析1. 在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可。2. 求城市之間最經(jīng)濟的架設(shè)方法。3. 米用多種存儲結(jié)構(gòu)，求解算法也米用多種。概要設(shè)計1功能模塊圖2、功能描述(1) CreateUDGO創(chuàng)建一個圖：通過給用戶信息提示，讓用戶將城市信息及城市之間的聯(lián)系關(guān) 系和連接權(quán)值寫入程序，并根據(jù)寫入的數(shù)據(jù)創(chuàng)建成

2、一個圖。(2) SwitchO功能選擇：給用戶提示信息，讓用戶選擇相應(yīng)功能。(3) Adjace ncy_Matrix()建立鄰接矩陣：將用戶輸入的數(shù)據(jù)整理成鄰接矩陣并顯現(xiàn)在屏幕上。( 4) Adjacency_List() 建立鄰接表：將用戶輸入的數(shù)據(jù)整理成臨接表并顯現(xiàn)在屏幕上。( 5) MiniSpanTree_KRSL()kruskal 算法：利用 kruskal 算法求出圖的最小生成樹，即：城市之間最經(jīng) 濟的連接方案。( 6) MiniSpanTree_PRIM()PRIM算法：利用PRIM算法求出圖的最小生成樹，即：城市之間最經(jīng)濟的連 接方案。四、 詳細設(shè)計本次課程設(shè)計采用兩種存儲結(jié)

3、構(gòu)以及兩種求解算法。 1、兩種存儲結(jié)構(gòu)的存儲定義如下： typedef struct Arcelldouble adj;Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef structvexsMAX_VERTEX_NUM;chardj=MAX;cout<<" 請輸入兩個城市名稱及其連接費用 "<<endl;for(k=0;k<+k) cin >> dgevaluek.ch1 dgevaluek.value;i = LocateVex(G,dgevaluek.ch1);j = L

4、ocateVex(G,dgevaluek.ch2); ij.adj = dgevaluek.value; ji.adj = ij.adj;return OK;int LocateVex(MGraph G,char ch) dj=MAX) cout<<0<<" "else cout<<ij.adj<<" " cout<<endl; void Adjacency_List(MGraph h1=i&&dgevaluej.ch2!=i) cout<<dgevaluej.ch2

5、<<"->"else if(dgevaluej.ch1!=i&&dgevaluej.ch2=i) cout<<dgevaluej.ch1<<"->"cout<<"bb "<<endl; void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)h1);p2 = bjLocateVex(G,dgevaluei.ch2);if(p1 != p2) cout<<" 城 市 &qu

6、ot;<<dgevaluei.ch1<<" "<<dgevaluei.ch2<<" 連接。 "<<endl;for(j=0; j< j+)if(bjj = p2)bjj = p1;（ 嚴禁連接重復(fù)輸入 !） ：>> dgevaluek.ch2G,Dgevalue>>dgevalue)與城市void Sortdge(Dgevalue & dgevalue,MGraph G)alue > dgevaluej.value) temp = dgevaluei.

7、value; dgevaluei.value = dgevaluej.value; dgevaluej.value = temp;ch1 = dgevaluei.ch1; dgevaluei.ch1 = dgevaluej.ch1; dgevaluej.ch1 = ch1;ch2 = dgevaluei.ch2; dgevaluei.ch2 = dgevaluej.ch2; dgevaluej.ch2 = ch2;void MiniSpanTree_PRIM(MGraph G,char u)djvex = u; closedgej.lowcost = kj.adj;closedgek.lowc

8、ost = 0;for(i=1; i< i+)k = Minimum(G,closedge);cout<<" 城市 "<<closedgek.adjvex<<" 與城市 "<<k<<" 連接。 "<<endl;closedgek.lowcost = 0;for(j=0; j< +j)ifkj.adj < closedgej.lowcost)closedgej.adjvex = k; closedgej.lowcost= kj.adj;Minimu

9、m(MGraph G,Closedge closedge) owcost0 &&intclosedgei.lowcost < k)k = closedgei.lowcost; j = i; return j;void main() MGraph G; Dgevalue dgevalue; CreateUDG(G,dgevalue); char u; cout<<" 圖創(chuàng)建成功。H.n"、用鄰接矩陣存儲： "<<endl;、用鄰接表存儲： "<<endl;、克魯斯卡爾算法求最經(jīng)濟的連接方案 &quo

10、t;<<endl; 、普里姆算法求最經(jīng)濟的連接方案 "<<endl;cout<<" 請根據(jù)如下菜單選擇操作。 cout<<"1 cout<<"2 cout<<"3 cout<<"4 int s; char y='y' while(y='y') cout<<" 請選擇菜單： "<<endl; cin>>s; switch(s) case 1: cout<<

11、" 用鄰接矩陣存儲為： "<<endl; Adjacency_Matrix(G); break; case 2: cout<<" 用鄰接表存儲為： "<<endl; Adjacency_List(G,dgevalue); break; case 3: cout<<" 克魯斯卡爾算法最經(jīng)濟的連接方案為 :"<<endl; MiniSpanTree_KRSL(G,dgevalue); break; case 4: cout<<" 普里姆算法最經(jīng)濟的連接方案為

12、 :"<<endl; cout<<" 請輸入起始城市名稱： " cin>>u;MiniSpanTree_PRIM(G,u); break; default:cout<<" 輸入有誤 !" break; cout<<endl<<" 是否繼續(xù)？ y/n:" cin>>y;if(y='n')break;六、五、 運行結(jié)果與測試設(shè)計體會與總結(jié)通過本次課程設(shè)計， 我在程序設(shè)計中， 用鄰接矩陣和鄰接表這兩種存儲結(jié)構(gòu) 進行編程，且對 Prim 算法和 Kruskal 算法生成最小生成樹有了一個初步的了解， 同時也為日后的畢業(yè)設(shè)計打下了良好的基礎(chǔ)。 而且通過課程設(shè)計在下述各方面得 到了鍛煉：1、能根據(jù)實際問題的具體情況，結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算 法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)， 合理地選擇相應(yīng)的存儲結(jié)構(gòu)， 并能設(shè)計出解決 問題的有效算法。2、提高程序設(shè)計和調(diào)試能力。通過上機實習(xí)，驗證自己設(shè)計的算法的正確 性。學(xué)會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且