最小生成樹(shù)問(wèn)題

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

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

3、構(gòu)以及兩種求解算法。 1、兩種存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)定義如下： typedef struct Arcelldouble adj;Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef structvexsMAX_VERTEX_NUM;chardj=MAX;cout<<" 請(qǐng)輸入兩個(gè)城市名稱及其連接費(fèi)用 "<<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;（ 嚴(yán)禁連接重復(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"、用鄰接矩陣存儲(chǔ)： "<<endl;、用鄰接表存儲(chǔ)： "<<endl;、克魯斯卡爾算法求最經(jīng)濟(jì)的連接方案 &quo

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

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

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