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

1、 榆林學(xué)院12屆課程設(shè)計(jì) 最小生成樹(shù)問(wèn)題課程設(shè)計(jì)說(shuō)明書 學(xué)生姓名： 趙佳 學(xué) 號(hào)： 1412210112 院 系： 信息工程學(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、 功能模塊圖開(kāi)始創(chuàng)建一個(gè)圖功能選擇1.建立鄰接矩陣2.建立鄰接表3.kruskal

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

3、 MiniSpanTree_PRIM()PRIM算法：利用PRIM算法求出圖的最小生成樹(shù)，即：城市之間最經(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 char vexsMAX_VERTEX_NUM; /節(jié)點(diǎn)數(shù)組 AdjMatrix arcs; /鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前節(jié)點(diǎn)數(shù)和弧數(shù) MGraph; typedef

4、 struct Pnode /用于普利姆算法 char adjvex; /節(jié)點(diǎn) double lowcost; /權(quán)值 Pnode,ClosedgeMAX_VERTEX_NUM;/記錄頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義 typedef struct Knode/用于克魯斯卡爾算法中存儲(chǔ)一條邊及其對(duì)應(yīng)的2個(gè)節(jié)點(diǎn) char ch1; /節(jié)點(diǎn)1 char ch2; /節(jié)點(diǎn)2 double value;/權(quán)值 Knode,DgevalueMAX_VERTEX_NUM; 2、求解算法采用Prim算法和Kruskal算法。（1）普里姆算法(Prim)算法普里姆算法(Prim)算法是一種構(gòu)造性算法

5、，生成最小生成樹(shù)的步驟如下：初始化U=v。以v到其他頂點(diǎn)的所有邊為候選邊。重復(fù)一下步驟(n-1)次，使得其他(n-1)個(gè)頂點(diǎn)被加入到U中。從候選邊中挑選權(quán)值最小的邊加入TE，設(shè)該邊在VU中的頂點(diǎn)是vk，將頂點(diǎn)vk加入到U中;考察當(dāng)前VU中的所有頂點(diǎn)vj ，修改候選邊：若(vk,vj)的權(quán)值小于原來(lái)和vj關(guān)聯(lián)的候選邊，則用(vk,vj)取代后者作為候選邊。 開(kāi)始標(biāo)志頂點(diǎn)1加入U(xiǎn)集合尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊形成n-1條邊的生成樹(shù)頂點(diǎn)k加入U(xiǎn)修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值結(jié)束得到最小生成樹(shù)（2）克魯斯卡爾(Kruskal)算法克魯斯卡爾(Kruskal)算法是一種按權(quán)值的遞增

6、次序選擇合適的邊來(lái)構(gòu)造最小生成樹(shù)的方法。假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖，T=(U,TE)是G的最小生成樹(shù)，則構(gòu)造最小生成樹(shù)的步驟如下：置U的初值等于V（即包含有G中的全部頂點(diǎn)），TE的初值為空集（即圖T中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)分量）。將圖G中的邊按權(quán)值從小到大的順序依次選?。喝暨x取的邊未使生成樹(shù)T形成回路，則加入TE，否則舍棄，直到TE中包含(n-1)條邊為止。3、使用的函數(shù)int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,char ch); int Minimum(M

7、Graph G,Closedge closedge); void MiniSpanTree_PRIM(MGraph G,char u); void Sortdge(Dgevalue & dgevalue,MGraph G); void Adjacency_Matrix(MGraph G);void Adjacency_List(MGraph G,Dgevalue dgevalue);函數(shù)之間的調(diào)用關(guān)系圖：CreateUDG()main()Adjacency_Matrix()Adjacency_List()MiniSpanTree_KRSL()MiniSpanTree_PRIM()loc

8、ateVex()locateVex()Minimum()locateVex()Sortdge()五、 程序代碼#include<stdio.h> #include<stdlib.h> #include<iostream.h> #define MAX_VERTEX_NUM 20 #define OK 1 #define ERROR 0 #define MAX 1000 typedef struct Arcell double adj; Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct ch

9、ar vexsMAX_VERTEX_NUM; /節(jié)點(diǎn)數(shù)組 AdjMatrix arcs; /鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前節(jié)點(diǎn)數(shù)和弧數(shù) MGraph; typedef struct Pnode /用于普利姆算法 char adjvex; /節(jié)點(diǎn) double lowcost; /權(quán)值 Pnode,ClosedgeMAX_VERTEX_NUM;/記錄頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義 typedef struct Knode/用于克魯斯卡爾算法中存儲(chǔ)一條邊及其對(duì)應(yīng)的2個(gè)節(jié)點(diǎn) char ch1; /節(jié)點(diǎn)1 char ch2; /節(jié)點(diǎn)2 double value

10、;/權(quán)值 Knode,DgevalueMAX_VERTEX_NUM; int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,char ch); int Minimum(MGraph G,Closedge closedge); void MiniSpanTree_PRIM(MGraph G,char u); void Sortdge(Dgevalue & dgevalue,MGraph G); void Adjacency_Matrix(MGraph G);void Adjacency_

11、List(MGraph G,Dgevalue dgevalue);int CreateUDG(MGraph & G,Dgevalue & dgevalue)/構(gòu)造無(wú)向加權(quán)圖的鄰接矩陣 int i,j,k; cout<<"請(qǐng)輸入城市個(gè)數(shù)及其之間的可連接線路數(shù)目：" cin>>G.vexnum>>G.arcnum; cout<<"請(qǐng)輸入各個(gè)城市名稱(分別用一個(gè)字符代替)：" for(i=0;i<G.vexnum;+i) cin>>G.vexsi; for(i=0;i<G.

12、vexnum;+i)/初始化數(shù)組 for(j=0;j<G.vexnum;+j) G.arcsij.adj=MAX; cout<<"請(qǐng)輸入兩個(gè)城市名稱及其連接費(fèi)用(嚴(yán)禁連接重復(fù)輸入!)："<<endl; for(k=0;k<G.arcnum;+k) cin >> dgevaluek.ch1 >> dgevaluek.ch2 >> dgevaluek.value; i = LocateVex(G,dgevaluek.ch1); j = LocateVex(G,dgevaluek.ch2); G.arcsij

13、.adj = dgevaluek.value; G.arcsji.adj = G.arcsij.adj; return OK; int LocateVex(MGraph G,char ch) /確定節(jié)點(diǎn)ch在圖G.vexs中的位置 int a ; for(int i=0; i<G.vexnum; i+) if(G.vexsi = ch) a=i; return a; void Adjacency_Matrix(MGraph G) /用鄰接矩陣存儲(chǔ)數(shù)據(jù)int i,j;for(i=0; i<G.vexnum; i+) for(j=0; j<G.vexnum; j+) if(G.a

14、rcsij.adj=MAX)cout<<0<<" " elsecout<<G.arcsij.adj<<" " cout<<endl; void Adjacency_List(MGraph G,Dgevalue dgevalue) /用鄰接表儲(chǔ)存數(shù)據(jù)int i,j;for(i=0;i<G.vexnum;i+)cout<<G.vexsi<<"->"for(j=0;j<G.arcnum;j+)if(dgevaluej.ch1=G.vexsi

15、&&dgevaluej.ch2!=G.vexsi)cout<<dgevaluej.ch2<<"->"else if(dgevaluej.ch1!=G.vexsi&&dgevaluej.ch2=G.vexsi)cout<<dgevaluej.ch1<<"->"cout<<"bb "<<endl;void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)/克魯斯卡爾算法求

16、最小生成樹(shù) int p1,p2,i,j; int bjMAX_VERTEX_NUM; /標(biāo)記數(shù)組 for(i=0; i<G.vexnum; i+) /標(biāo)記數(shù)組初始化 bji=i; Sortdge(dgevalue,G);/將所有權(quán)值按從小到大排序 for(i=0; i<G.arcnum; i+) p1 = bjLocateVex(G,dgevaluei.ch1); p2 = bjLocateVex(G,dgevaluei.ch2); if(p1 != p2) cout<<" 城市"<<dgevaluei.ch1<<"

17、與城市"<<dgevaluei.ch2<<"連接。"<<endl; for(j=0; j<G.vexnum; j+) if(bjj = p2) bjj = p1; void Sortdge(Dgevalue & dgevalue,MGraph G)/對(duì)dgevalue中各元素按權(quán)值按從小到大排序 int i,j; double temp; char ch1,ch2; for(i=0; i<G.arcnum; i+) for(j=i; j<G.arcnum; j+) if(dgevaluei.value

18、> dgevaluej.value) temp = dgevaluei.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)/普里姆算法求最小生

19、成樹(shù) int i,j,k; Closedge closedge; k = LocateVex(G,u); for(j=0; j<G.vexnum; j+) /輔助數(shù)組初始化 if(j != k) closedgej.adjvex = u; closedgej.lowcost = G.arcskj.adj; closedgek.lowcost = 0; for(i=1; i<G.vexnum; i+) k = Minimum(G,closedge); cout<<" 城市"<<closedgek.adjvex<<"與城

20、市"<<G.vexsk<<"連接。"<<endl; closedgek.lowcost = 0; for(j=0; j<G.vexnum; +j) if(G.arcskj.adj < closedgej.lowcost) closedgej.adjvex = G.vexsk; closedgej.lowcost= G.arcskj.adj; int Minimum(MGraph G,Closedge closedge) /求closedge中權(quán)值最小的邊，并返回其頂點(diǎn)在vexs中的位置 int i,j; double

21、 k = 1000; for(i=0; i<G.vexnum; i+) if(closedgei.lowcost != 0 && closedgei.lowcost < k) k = closedgei.lowcost; j = i; return j; void main() MGraph G; Dgevalue dgevalue; CreateUDG(G,dgevalue); char u; cout<<"圖創(chuàng)建成功。" cout<<"請(qǐng)根據(jù)如下菜單選擇操作。n" cout<<"

22、;1、用鄰接矩陣存儲(chǔ)："<<endl; cout<<"2、用鄰接表存儲(chǔ)："<<endl; cout<<"3、克魯斯卡爾算法求最經(jīng)濟(jì)的連接方案"<<endl; cout<<"4、普里姆算法求最經(jīng)濟(jì)的連接方案"<<endl; int s; char y='y' while(y='y') cout<<"請(qǐng)選擇菜單："<<endl; cin>>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_KR