數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)最小生成樹問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告 課程設(shè)計(jì)題目： 最小生成樹問題 專業(yè)班級(jí)： 信息與計(jì)算科學(xué)1001班 姓 名： 謝煒 學(xué) 號(hào)： 設(shè)計(jì)室號(hào)： 理學(xué)院機(jī)房 設(shè)計(jì)時(shí)間： 2011-12-26 批閱時(shí)間： 指導(dǎo)教師： 杜洪波 成 績(jī)： 一、摘要：隨著社會(huì)經(jīng)濟(jì)的發(fā)展，人們的生活已經(jīng)越來(lái)越離不開網(wǎng)絡(luò)，網(wǎng)絡(luò)成為人們社會(huì)生活的重要組成部分。我們希望擁有一個(gè)寬松的上網(wǎng)環(huán)境，以便更好的進(jìn)行信息的交流，在此我們有必要提升我們的網(wǎng)絡(luò)傳播速度。從某種程度上來(lái)說網(wǎng)絡(luò)傳播速度代表著一個(gè)國(guó)家網(wǎng)絡(luò)化程度的高低。為了解決網(wǎng)絡(luò)傳輸速度的問題我們希望在各個(gè)城市之間多架設(shè)一些通信網(wǎng)絡(luò)線路，以緩解網(wǎng)絡(luò)不夠流暢不夠

2、便捷的問題。而在城市之間架設(shè)網(wǎng)絡(luò)線路受到資金因素等的限制，我們希望找到一條捷徑這樣我們即達(dá)到了連接了各個(gè)城市網(wǎng)絡(luò)的目的又節(jié)省了建設(shè)成本。通過以上的分析我們得出解決此問題的關(guān)鍵在于找到一個(gè)短的路徑完成網(wǎng)絡(luò)的假設(shè)。在此我們想將各個(gè)城市抽象成為一個(gè)個(gè)節(jié)點(diǎn)，連接各個(gè)城市之間的網(wǎng)絡(luò)作為連接各個(gè)節(jié)點(diǎn)的邊。于是我們就將城市的空間分布抽象成為一個(gè)網(wǎng)絡(luò)圖，再將各條邊的距離抽象成為各節(jié)點(diǎn)之間的權(quán)值。在原來(lái)的基礎(chǔ)上建立一個(gè)帶有權(quán)值的網(wǎng)絡(luò)圖。于是原有的問題就轉(zhuǎn)化為找圖的最小生成樹問題。我們利用普利姆算法和卡魯斯卡爾算法找到我們所需要的最小的生成樹。二、問題分析 在n個(gè)城市間建立通信網(wǎng)絡(luò)，需架設(shè)n-1條路線。求解如何以

3、最低的經(jīng)濟(jì)代價(jià)建設(shè)此通信網(wǎng)，這是一個(gè)最小生成樹問題。我們可以利用普利姆算法或者克魯斯卡爾算法求出網(wǎng)的最小生成樹，輸入各城市的數(shù)目以及各個(gè)城市之間的距離。將城市之間的距離當(dāng)做網(wǎng)中各點(diǎn)之間的權(quán)值。三、實(shí)現(xiàn)本程序需要解決的問題（1）如何選擇存儲(chǔ)結(jié)構(gòu)去建立一個(gè)帶權(quán)的網(wǎng)絡(luò)；（2）如何在所選存儲(chǔ)結(jié)構(gòu)下輸出這個(gè)帶權(quán)網(wǎng)絡(luò)；（3）如何實(shí)現(xiàn)普利姆算法的功能；（4）如何從每個(gè)頂點(diǎn)開始找到所有的最小生成樹的頂點(diǎn)；（5）如何輸出最小生成樹的邊及其權(quán)值此問題的關(guān)鍵就是利用普利姆算法，找到一個(gè)最小上的生成樹，在一個(gè)就是輸出我們所需要的信息，在此我們將各個(gè)城市看做是網(wǎng)中的各個(gè)頂點(diǎn)城市之間的距離看做是個(gè)頂點(diǎn)之間的權(quán)值。現(xiàn)在我們

4、問題做如下的分析：這個(gè)問題主要在于普利姆算法的實(shí)現(xiàn)。我們將各個(gè)城市的空間分布抽象成一個(gè)帶有權(quán)值的網(wǎng)絡(luò)，這個(gè)權(quán)值就是任意兩個(gè)城市之間，各個(gè)城市就看做是網(wǎng)絡(luò)的各個(gè)頂點(diǎn)。我們建立的輸入的數(shù)據(jù)格式為：首先提示輸入帶權(quán)的頂點(diǎn)數(shù)目，我定義為整形的數(shù)據(jù)型，然后輸入每條邊的信息，即邊的兩個(gè)頂點(diǎn)之間的權(quán)值，以十進(jìn)制整數(shù)類型數(shù)據(jù)，這樣我們就建立了一個(gè)帶權(quán)的網(wǎng)絡(luò)。問題的輸出我是將我們所得到的最小生成樹的路線輸出出來(lái)。題目的要求就是我們?cè)趎個(gè)城市之間架設(shè)網(wǎng)絡(luò)得到的最為經(jīng)濟(jì)的架設(shè)方法，我們進(jìn)行以上的工作就是在找我們所需要的最小生成樹，已解決我們的問題。四、算法思想普利姆算法求最小生成樹的主要思想假設(shè)N=（V，E）是連通

5、網(wǎng)，TE是N上最小生成樹中邊的集合。算法從U=u0( u0V),TE=開始，重復(fù)執(zhí)行下述操作：在所有uU,vV-U的邊（u,v）E中找一條代價(jià)最小的邊（u0,v0）并入集合TE，同時(shí)v0并入U(xiǎn)，直至U=V為止。此時(shí)TE中必有n-1條邊，則T=（V，E）為N的最小生成樹。對(duì)于最小生成樹問題：最小生成樹是指在所有生成樹中，邊上權(quán)值之和最小的生成樹，另外最小生成樹也可能是多個(gè)但是他們權(quán)值之和是相等的。五、程序設(shè)計(jì)流程圖：輸入需要架設(shè)網(wǎng)絡(luò)的城市的數(shù)目輸入需要架設(shè)網(wǎng)絡(luò)的各個(gè)城市之間的距離找到一個(gè)最小的生成樹輸出一個(gè)最小的生成樹這個(gè)最小的生成樹就是一個(gè)架設(shè)網(wǎng)絡(luò)的最優(yōu)解六、模塊劃分（1）預(yù)處理#includ

6、e<stdio.h>#define maxvertexnum 20 #define maxedgenum 40 typedef int adjmatrixmaxvertexnummaxvertexnum;（2）定義一個(gè)儲(chǔ)存節(jié)點(diǎn)信息的結(jié)構(gòu)體struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum;（3）初始化的無(wú)向圖，將每條邊的權(quán)值賦值為無(wú)窮void insitadj(adjmatrix &GA)for(int i=1;i<maxvertexnum;i+)f

7、or(int j=1;j<maxvertexnum;j+)GAij=20000; /將邊的權(quán)值賦值為無(wú)窮/（4）以各個(gè)城市為基礎(chǔ)建立一個(gè)網(wǎng)絡(luò)void setadj(adjmatrix &GA,int n) /建立網(wǎng)絡(luò)for(int i=1;i<=n+1;i+)for(int j=i+1;j<n+1;j+)printf("請(qǐng)輸入第%d個(gè)城市到第%d個(gè)城市的距離：",i,j);scanf("%d",&GAij);for(i=1;i<=n+1;i+)for(int j=i+1;j<n+1;j+)GAji=GAij;

8、（5）將建立的網(wǎng)絡(luò)各個(gè)連接的節(jié)點(diǎn)賦上權(quán)值void insit(adgeset&GT,int n,adjmatrix GA)for(int i=1;i<n;i+)GTi.frontvex=1;GTi.rearvex=i+1;GTi.weight=GA1i+1; （6）輸出我們所找到的最小生成樹void fun(adjmatrix GA,adgeset&GT,int n) int i;for(i=1;i<n;i+)int min=10000,m=i;for(int j=i;j<n;j+)if(GTj.weight<min)min=GTj.weight;m=j

9、;edgenode temp=GTi;GTi=GTm;GTm=temp;int k=GTm.rearvex;for(j=i;j<n;j+)int t=GTj.rearvex;int w=GAkt;if(w<GTj.weight)GTj.weight=w;GTj.frontvex=k;void display(adgeset GT,int n)for(int i=1;i<n;i+)printf("第%d個(gè)城市到第%d城市修建一條電纜!n",GTi.frontvex,GTi.rearvex); printf("這樣修建可以使距離最短！");

10、（7）主函數(shù)int main() printf("請(qǐng)問您要在幾個(gè)城市間建立網(wǎng)絡(luò)？n請(qǐng)?jiān)诖溯斎耄?quot;);int n; scanf("%d",&n) ;adgeset GT;adjmatrix GA;insitadj(GA);setadj(GA,n);insit(GT,n,GA);fun(GA,GT,n);display(GT,n);return 0;七、算法設(shè)計(jì)與分析選定存儲(chǔ)形式要實(shí)現(xiàn)對(duì)于給定帶權(quán)網(wǎng)絡(luò)和頂點(diǎn)，運(yùn)用普利姆基本算法思想求解所有的最小生成樹的運(yùn)算，在這里我們首先要明確所選用的數(shù)據(jù)結(jié)構(gòu)，即采用何種數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)帶權(quán)網(wǎng)絡(luò)，這是必須首先解決的問題

11、，我們采用圖的鄰接矩陣的存儲(chǔ)方式來(lái)存儲(chǔ)帶權(quán)網(wǎng)絡(luò)。我們?cè)诮⑧徑泳仃嚨臅r(shí)候選用數(shù)組來(lái)分別存儲(chǔ)每個(gè)節(jié)點(diǎn)的信息以及邊的權(quán)值。八、源程序#include<stdio.h>#define maxvertexnum 20 #define maxedgenum 40 typedef int adjmatrixmaxvertexnummaxvertexnum;struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum;/=void insitadj(adjmatrix &GA);

12、void setadj(adjmatrix &GA,int n);void fun(adjmatrix GA,adgeset &GT,int n);void display(adgeset GT,int n);void insit(adgeset &GT,int n,adjmatrix GA);/=void insit(adgeset&GT,int n,adjmatrix GA)for(int i=1;i<n;i+)GTi.frontvex=1;GTi.rearvex=i+1;GTi.weight=GA1i+1; void insitadj(adjmatr

13、ix &GA)for(int i=1;i<maxvertexnum;i+)for(int j=1;j<maxvertexnum;j+)GAij=20000;void setadj(adjmatrix &GA,int n) /建立網(wǎng)絡(luò)for(int i=1;i<=n+1;i+)for(int j=i+1;j<n+1;j+)printf("請(qǐng)輸入第%d個(gè)城市到第%d個(gè)城市的距離：",i,j);scanf("%d",&GAij);for(i=1;i<=n+1;i+)for(int j=i+1;j<n+

14、1;j+)GAji=GAij;void fun(adjmatrix GA,adgeset&GT,int n) int i;for(i=1;i<n;i+)int min=10000,m=i;for(int j=i;j<n;j+)if(GTj.weight<min)min=GTj.weight;m=j;edgenode temp=GTi;GTi=GTm;GTm=temp;int k=GTm.rearvex;for(j=i;j<n;j+)int t=GTj.rearvex;int w=GAkt;if(w<GTj.weight)GTj.weight=w;GTj.f

15、rontvex=k;void display(adgeset GT,int n)for(int i=1;i<n;i+)printf("第%d個(gè)城市到第%d城市修建一條電纜!n",GTi.frontvex,GTi.rearvex); printf("這樣修建可以使距離最短！");int main() printf("請(qǐng)問您要在幾個(gè)城市間建立網(wǎng)絡(luò)？n請(qǐng)?jiān)诖溯斎耄?quot;);int n; scanf("%d",&n) ;adgeset GT;adjmatrix GA;insitadj(GA);setadj(GA,

16、n);insit(GT,n,GA);fun(GA,GT,n);display(GT,n);return 0;九、算法實(shí)現(xiàn)（1）提示輸入截圖(2)輸入各節(jié)點(diǎn)間的權(quán)（3）輸出結(jié)果十、心得體會(huì)數(shù)據(jù)結(jié)構(gòu)是學(xué)習(xí)計(jì)算機(jī)的一門重要的基礎(chǔ)課，在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之前我們學(xué)習(xí)了C語(yǔ)言在我們看來(lái)數(shù)據(jù)結(jié)構(gòu)就是學(xué)習(xí)C語(yǔ)言的延續(xù)。我們知道像這種計(jì)算機(jī)類的課程必須配合著上機(jī)實(shí)際操作才能很好的學(xué)習(xí)他。但是我們平時(shí)在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的過程中過少的參與到上機(jī)練習(xí)，在把精力放在了理論知識(shí)的學(xué)習(xí)上忽視了上機(jī)的重要性。在此次課程設(shè)計(jì)中我們深刻的體會(huì)到我們光靠學(xué)習(xí)理論只是不夠的，因而我們很珍惜此次上機(jī)學(xué)習(xí)的機(jī)會(huì)。認(rèn)真做好自己的程序。雖然我在剛剛接觸到這些習(xí)題的時(shí)候會(huì)感到無(wú)所適從，不知道該從哪里下手。但是還是要細(xì)心認(rèn)真的完成，在調(diào)試過程中雖然也會(huì)出現(xiàn)或多或少的錯(cuò)誤，剛開始在遇到錯(cuò)誤的時(shí)候非常焦躁，看到程序就會(huì)頭大，但最終還是找到了狀態(tài)，一步一步慢慢來(lái)，經(jīng)過無(wú)數(shù)次的檢查程序錯(cuò)誤的原因后慢慢懂得了耐心是一個(gè)人成功的必然條件！在本次試驗(yàn)的學(xué)習(xí)