最小生成樹問題

1、榆林學(xué)院12屆課程設(shè)計(jì) 最小生成樹問題 課程設(shè)計(jì)說明書 學(xué)生姓名：趙佳 學(xué)號(hào)：12 院系：信息工程學(xué)院 專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 班級(jí)：計(jì)14本1 指導(dǎo)教師： 答辯時(shí)間：年 月 日 最小生成樹問題 一、問題陳述 最小生成樹問題 設(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) CreateUDG() 創(chuàng)建一個(gè)圖：通過給用戶信息提示，讓用戶將城市

2、信息及城市之間的聯(lián)系關(guān) 系和連接權(quán)值寫入程序，并根據(jù)寫入的數(shù)據(jù)創(chuàng)建成一個(gè)圖。 (2) Switch() 功能選擇：給用戶提示信息，讓用戶選擇相應(yīng)功能。 (3) Adjace ncy_Matrix() 建立鄰接矩陣：將用戶輸入的數(shù)據(jù)整理成鄰接矩陣并顯現(xiàn)在屏幕上。 ( 4) Adjacency_List() 建立鄰接表：將用戶輸入的數(shù)據(jù)整理成臨接表并顯現(xiàn)在屏幕上。 ( 5) MiniSpanTree_KRSL() kruskal 算法：利用 kruskal 算法求出圖的最小生成樹，即：城市之間最經(jīng) 濟(jì)的連接方案。 ( 6) MiniSpanTree_PRIM() PRIM算法：利用PRIM算法求出

3、圖的最小生成樹，即：城市之間最經(jīng)濟(jì)的連 接方案。 四、詳細(xì)設(shè)計(jì) 本次課程設(shè)計(jì)采用兩種存儲(chǔ)結(jié)構(gòu)以及兩種求解算法。 1、兩種存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)定義如下： typedef struct Arcell double adj; Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct charvexsMAX_VERTEX_NUM; dj=MAX; cout 請(qǐng)輸入兩個(gè)城市名稱及其連接費(fèi)用 ( 嚴(yán)禁連接重復(fù)輸入 !) ： 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 請(qǐng)根據(jù)如下菜單選擇操作。 n; cout1 、用鄰接矩陣存儲(chǔ)： endl; cout2 、用鄰接表存儲(chǔ)： endl;

8、cout3 、克魯斯卡爾算法求最經(jīng)濟(jì)的連接方案 endl; cout4 、普里姆算法求最經(jīng)濟(jì)的連接方案 endl; int s; char y=y; while(y=y) cout 請(qǐng)選擇菜單： s; switch(s) case 1: cout 用鄰接矩陣存儲(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); b

9、reak; case 4: cout 普里姆算法最經(jīng)濟(jì)的連接方案為 :endl; coutu; MiniSpanTree_PRIM(G,u); break; default: cout 輸入有誤 !; break; coutendly; if(y=n) break; 五、運(yùn)行結(jié)果與測(cè)試 六、設(shè)計(jì)體會(huì)與總結(jié) 通過本次課程設(shè)計(jì)， 我在程序設(shè)計(jì)中， 用鄰接矩陣和鄰接表這兩種存儲(chǔ)結(jié)構(gòu) 進(jìn)行編程，且對(duì) Prim 算法和 Kruskal 算法生成最小生成樹有了一個(gè)初步的了解， 同時(shí)也為日后的畢業(yè)設(shè)計(jì)打下了良好的基礎(chǔ)。 而且通過課程設(shè)計(jì)在下述各方面得 到了鍛煉： 1、能根據(jù)實(shí)際問題的具體情況，結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算 法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)， 合理地選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu)， 并能設(shè)計(jì)出解決 問題的有效算法。 2、提高程序設(shè)計(jì)和調(diào)試能力。通過上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)的算法的正確 性。學(xué)會(huì)有效利用基本調(diào)試方法，迅速找出程序代碼中的錯(cuò)誤并且修改。 3、培養(yǎng)算法分析能力。分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度，進(jìn)一 步提高程序設(shè)計(jì)水平。 在本次課