最小生成樹問題

1、榆林學院12屆課程設(shè)計 最小生成樹問題 課程設(shè)計說明書 學生姓名：趙佳 學號：12 院系：信息工程學院 專業(yè)：計算機科學與技術(shù) 班級：計14本1 指導教師： 答辯時間：年 月 日 最小生成樹問題 一、問題陳述 最小生成樹問題 設(shè)計要求：在n個城市之間建設(shè)網(wǎng)絡，只需保證連通即可，求最經(jīng)濟的架 設(shè)方法。存儲結(jié)構(gòu)采用多種。求解算法多種。 二、需求分析 1. 在n個城市之間建設(shè)網(wǎng)絡，只需保證連通即可。 2. 求城市之間最經(jīng)濟的架設(shè)方法。 3. 采用多種存儲結(jié)構(gòu)，求解算法也采用多種。 三、概要設(shè)計 1、功能模塊圖 2、功能描述 (1) CreateUDG() 創(chuàng)建一個圖：通過給用戶信息提示，讓用戶將城市

2、信息及城市之間的聯(lián)系關(guān) 系和連接權(quán)值寫入程序，并根據(jù)寫入的數(shù)據(jù)創(chuàng)建成一個圖。 (2) Switch() 功能選擇：給用戶提示信息，讓用戶選擇相應功能。 (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算法求出

3、圖的最小生成樹，即：城市之間最經(jīng)濟的連 接方案。 四、詳細設(shè)計 本次課程設(shè)計采用兩種存儲結(jié)構(gòu)以及兩種求解算法。 1、兩種存儲結(jié)構(gòu)的存儲定義如下： typedef struct Arcell double adj; Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct charvexsMAX_VERTEX_NUM; dj=MAX; cout 請輸入兩個城市名稱及其連接費用 ( 嚴禁連接重復輸入 !) ： endl; for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value; i

4、= LocateVex(G,dgevaluek.ch1); j = LocateVex(G,dgevaluek.ch2); ij.adj = dgevaluek.value; ji.adj = ij.adj; return OK; int LocateVex(MGraph G,char ch) dj=MAX) cout0 ; else coutij.adj ; coutendl; void Adjacency_List(MGraph G,Dgevalue dgevalue) h1=i else if(dgevaluej.ch1!=i coutbb endl; void MiniSpanTree

5、_KRSL(MGraph G,Dgevalue p2 = bjLocateVex(G,dgevaluei.ch2); if(p1 != p2) cout 城 市 dgevaluei.ch1 與 城 市 dgevaluei.ch2 連接。 endl; for(j=0; j dgevaluej.value) temp = dgevaluei.value; dgevaluei.value = dgevaluej.value; dgevaluej.value = temp; ch1 = dgevaluei.ch1; dgevaluei.ch1 = dgevaluej.ch1; dgevaluej.ch

6、1 = 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.lowcost = 0; for(i=1; i; i+) k = Minimum(G,closedge); cout 城市 closedgek.adjvex 與城市 k 連接。 endl; closedgek.lowcost = 0; for(j=0; j;

7、+j) ifkj.adj closedgej.lowcost) closedgej.adjvex = k; closedgej.lowcost= kj.adj; int Minimum(MGraph G,Closedge closedge) owcost != 0 j = i; return j; void main() MGraph G; Dgevalue dgevalue; CreateUDG(G,dgevalue); char u; cout 圖創(chuàng)建成功。 ; cout 請根據(jù)如下菜單選擇操作。 n; cout1 、用鄰接矩陣存儲： endl; cout2 、用鄰接表存儲： endl;

8、cout3 、克魯斯卡爾算法求最經(jīng)濟的連接方案 endl; cout4 、普里姆算法求最經(jīng)濟的連接方案 endl; int s; char y=y; while(y=y) cout 請選擇菜單： s; switch(s) case 1: cout 用鄰接矩陣存儲為： endl; Adjacency_Matrix(G); break; case 2: cout 用鄰接表存儲為： endl; Adjacency_List(G,dgevalue); break; case 3: cout 克魯斯卡爾算法最經(jīng)濟的連接方案為 :endl; MiniSpanTree_KRSL(G,dgevalue); b

9、reak; case 4: cout 普里姆算法最經(jīng)濟的連接方案為 :endl; coutu; MiniSpanTree_PRIM(G,u); break; default: cout 輸入有誤 !; break; coutendly; 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)， 合理地選擇相應的存儲結(jié)構(gòu)， 并能設(shè)計出解決 問題的有效算法。 2、提高程序設(shè)計和調(diào)試能力。通過上機實習，驗證自己設(shè)計的算法的正確 性。學會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改。 3、培養(yǎng)算法分析能力。分析所設(shè)計算法的時間復雜度和空間復雜度，進一 步提高程序設(shè)計水平。 在本次課