數(shù)據(jù)結(jié)構(gòu)(最小生成樹(shù)普利姆算法)

1、計(jì)算機(jī)系課程設(shè)計(jì)報(bào)告計(jì)算機(jī)系課程設(shè)計(jì)報(bào)告一、問(wèn)題分析和任務(wù)定義在n個(gè)城市間建立通信網(wǎng)絡(luò)，需架設(shè)n-1條線路。求解如何以最低經(jīng)濟(jì)代價(jià)建設(shè)此通信網(wǎng)，這是一個(gè)最小生成樹(shù)問(wèn)題。要求：（1）利用普利姆算法求網(wǎng)的最小生成樹(shù)；（2）輸出生成樹(shù)中各邊及權(quán)值。 二、實(shí)現(xiàn)本程序需要解決的問(wè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)PRIM算法的功能。(4)、如何從每個(gè)頂點(diǎn)開(kāi)始找到所有的最小生成樹(shù)的頂點(diǎn)。(5)、如何輸出最小生成樹(shù)的邊及其權(quán)值。此問(wèn)題的關(guān)鍵在于如何實(shí)現(xiàn)PRIM算法，實(shí)現(xiàn)的過(guò)程中如何得到構(gòu)成最小生成樹(shù)的所有頂點(diǎn)，此外輸出也是一個(gè)關(guān)鍵

2、問(wèn)題所在，在此過(guò)程中經(jīng)過(guò)了多次調(diào)試。首先我們對(duì)問(wèn)題進(jìn)行大致的概要分析：這個(gè)問(wèn)題主要牽涉到通過(guò)PRIM的基本算法思想實(shí)現(xiàn)程序所要求的功能，該算法的主要思想是：假設(shè)N=（V，E）是連通網(wǎng)，TE是N上最小生成樹(shù)中邊的集合。算法從U=u0( u0V),TE=開(kāi)始，重復(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的最小生成樹(shù)。問(wèn)題的輸入數(shù)據(jù)的格式為：首先提示輸入帶權(quán)網(wǎng)絡(luò)的頂點(diǎn)邊數(shù)，我定義的為整形數(shù)據(jù)型，然后輸入每一條邊的信息，即邊的兩個(gè)頂點(diǎn)以及權(quán)值，是十進(jìn)制整數(shù)類型，這樣我

3、們就建立一個(gè)帶權(quán)網(wǎng)絡(luò)，并用鄰接矩陣來(lái)存儲(chǔ)，生成一個(gè)方陣顯示出來(lái)。問(wèn)題的輸出數(shù)據(jù)格式為：輸出是以鄰接矩陣存儲(chǔ)結(jié)構(gòu)下的方陣，以及從不同頂點(diǎn)開(kāi)始省城的最小生成樹(shù)。題目要求以及達(dá)到目標(biāo)：題目要求用普利姆算法實(shí)現(xiàn)任意給定的網(wǎng)和頂點(diǎn)的所有最小生成樹(shù)，并且輸出各邊的權(quán)值。- 19 -三、測(cè)試數(shù)據(jù)第一組頂點(diǎn)數(shù)（vertices）、邊數(shù)（edge）：2、1起始節(jié)點(diǎn)（starting）、下個(gè)節(jié)點(diǎn)（terminal）、權(quán)值（weights）：1、2、5，預(yù)測(cè)結(jié)果5第二組頂點(diǎn)數(shù)（vertices）、邊數(shù)（edge）：3、3起始節(jié)點(diǎn)（starting）、下個(gè)節(jié)點(diǎn)（terminal）、權(quán)值（weights）：1、2、4

4、1、3、5 2、3、6預(yù)測(cè)結(jié)果4、5第三組頂點(diǎn)數(shù)（vertices）、邊數(shù)（edge）：4、5，起始節(jié)點(diǎn)（starting）、下個(gè)節(jié)點(diǎn)（terminal）、權(quán)值（weights）：1、2、3 1、3、4 1、4、6 2、4、7 3、4、5預(yù)測(cè)結(jié)果3、4、6 四、算法思想Prim算法求最小生成樹(shù)的主要思想此算法是普利姆與1957年提出的一種構(gòu)造最小生成樹(shù)的算法，主要思想是：假設(shè)N=（V，E）是連通網(wǎng)，TE是N上最小生成樹(shù)中邊的集合。算法從U=u0( u0V),TE=開(kāi)始，重復(fù)執(zhí)行下述操作：在所有uU,vV-U的邊（u,v）E中找一條代價(jià)最小的邊（u0,v0）并入集合TE，同時(shí)v0并入U(xiǎn)，直至U=

5、V為止。此時(shí)TE中必有n-1條邊，則T=（V，E）為N的最小生成樹(shù)。對(duì)于最小生成樹(shù)問(wèn)題最小生成樹(shù)是指在所有生成樹(shù)中，邊上權(quán)值之和最小的生成樹(shù)，另外最小生成樹(shù)也可能是多個(gè)，他們之間的權(quán)值之和相等。 五、模塊劃分（1）預(yù)處理#include #include #define inf 9999#define max 40#define linelenght 77（2）普里姆算法void prim(int gmax,int n) /* prim的函數(shù) */ int lowcostmax,closestmax; int i,j,k,min; for(i=2;i=n;i+) /* n個(gè)頂點(diǎn)，n-1條邊 *

6、/ lowcosti=g1i; /* 初始化 */ closesti=1; /* 頂點(diǎn)未加入到最小生成樹(shù)中 */ lowcost1=0; /* 標(biāo)志頂點(diǎn)1加入U(xiǎn)集合 */ for(i=2;i=n;i+) /* 形成n-1條邊的生成樹(shù) */ min=inf; k=0; for(j=2;j=n;j+) /* 尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊 */ if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,closestk,k,min); lowcostk=0; /* 頂點(diǎn)k加入U(xiǎn) */ for(j=2;j=n

7、;j+) /* 修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值 */ if(gkjlowcostj) lowcostj=gkj; closestj=k; printf(n); （3）輸出分割線int priline(int h) /* 輸出一條分割線 */ int g; printf(n|); for(g=0;gh;g+) printf(*); printf(|n); （4）提示錯(cuò)誤信息int error() /* 提示錯(cuò)誤信息 */ printf(nn|*E*R*R*O*R*|n); printf(Input errors or Data overflow! please re-enternn); fflu

8、sh(stdin); /* 清除緩存 */ （5）建立無(wú)向圖int adjg(int gmax) /* 建立無(wú)向圖 */ int n,e,i,j,k,v1=0,v2=0,weight=0; printf(Input the number of vertices, number of the edge:); scanf(%d,%d,&n,&e); while(e=n*(n-1)|n=max) error(); printf(Input the number of vertices, number of the edge:); scanf(%d,%d,&n,&e); for(i=1;i=n;i+)

9、 for(j=1;j=n;j+) gij=inf; /* 初始化矩陣，全部元素設(shè)為無(wú)窮大 */ for(k=1;kn|v2n|v11|v21) error(); printf(Input the %d on the edge of the starting point, terminal, weights:,k); scanf(%d,%d,%d,&v1,&v2,&weight); gv1v2=weight; gv2v1=weight; return(n); /* 返回節(jié)點(diǎn)個(gè)數(shù)n */（6）輸出無(wú)向圖的鄰接矩陣void pri(int gmax,int n) /* 輸出無(wú)向圖的鄰接矩陣 */ i

10、nt i,j; for(i=0;i=n;i+) printf(%dt,i); for(i=1;i=n;i+) printf(n%dt,i); for(j=1;j=n;j+) /* 輸出邊的權(quán)值 */ if(gij=inf) printf(%ct,354); else printf(%dt,gij); printf(n);（7）主函數(shù)模塊void main() /* 主函數(shù) */ int gmaxmax,n;priline(linelenght); n=adjg(g);priline(linelenght);priline(linelenght); printf(Input the adjace

11、ncy matrix without directed graph:n); pri(g,n); printf(n); printf(Minimum spanning tree structure:n); prim(g,n); getch();六、算法設(shè)計(jì)與分析（1）關(guān)于帶權(quán)網(wǎng)絡(luò)的存儲(chǔ)形式 要實(shí)現(xiàn)對(duì)于任意給定帶權(quán)網(wǎng)絡(luò)和頂點(diǎn)，運(yùn)用PRIM基本算法思想求解所有的最小生成樹(shù)的運(yùn)算。在這里我們首先要明確所選用的數(shù)據(jù)結(jié)構(gòu)，即選用何種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)來(lái)存儲(chǔ)帶權(quán)網(wǎng)絡(luò)，這是必選首先解決的問(wèn)題，所以我們選擇了圖的鄰接矩陣存儲(chǔ)方式來(lái)存儲(chǔ)帶權(quán)網(wǎng)絡(luò)，建圖時(shí)采用鄰接矩陣的結(jié)構(gòu)，定義鄰接矩陣用到了一維數(shù)組和二維數(shù)組，分別存儲(chǔ)頂

12、點(diǎn)信息和邊的權(quán)值。由于該算法對(duì)圖中的邊的權(quán)值頻繁比較，所以采用鄰接矩陣比較方便，并在此基礎(chǔ)上實(shí)現(xiàn)帶權(quán)網(wǎng)絡(luò)的建立以及輸出顯示。（2）關(guān)于普利姆算法的基本思想Prim算法求最小生成樹(shù)的主要思想此算法是普利姆與1957年提出的一種構(gòu)造最小生成樹(shù)的算法，主要思想是：假設(shè)N=（V，E）是連通網(wǎng)，TE是N上最小生成樹(shù)中邊的集合。算法從U=u0( u0V),TE=開(kāi)始，重復(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的最小生成樹(shù)。對(duì)于最小生成樹(shù)問(wèn)題最小生成樹(shù)是指在所有生成樹(shù)中，

13、邊上權(quán)值之和最小的生成樹(shù)，另外最小生成樹(shù)也可能是多個(gè)，他們之間的權(quán)值之和相等。（3）概要設(shè)計(jì)通過(guò)鄰接矩陣的建立，可以將任意兩點(diǎn)的權(quán)值存入其中，便于進(jìn)行各邊的權(quán)值的比較修改，在普利姆算法中，為實(shí)現(xiàn)這個(gè)算法需附設(shè)一個(gè)輔助數(shù)組closedge，以記錄從U到V-U具有最小代價(jià)的邊，對(duì)每個(gè)頂點(diǎn)viV-U,在輔助數(shù)組中存在一個(gè)相應(yīng)分量closedgei-1，他包括兩個(gè)域，其中l(wèi)owcost存儲(chǔ)該邊上的權(quán)值。顯然，closedgei-1.lowcost=Mincost(u,vi)| uU從算法可以看出每加入一個(gè)頂點(diǎn)到U中，closedge數(shù)組都會(huì)發(fā)生相應(yīng)的變化。程序模塊之間的調(diào)用：在主函數(shù)中調(diào)用鄰接矩陣的初

14、始化函數(shù)，鄰接矩陣的生成函數(shù)，PRIM算法的函數(shù)，圖的構(gòu)造函數(shù)，輸出函數(shù)。鄰接矩陣的生成函數(shù)主要解決的是邊的信息存儲(chǔ)問(wèn)題，而PRIM算法的函數(shù)是解決計(jì)算出最小生成樹(shù)的功能。詳細(xì)設(shè)計(jì)和編碼首先我在接下來(lái)給出總的流程：Main（）建立圖并初始化圖中信息調(diào)用主函數(shù)prim找到頂點(diǎn)I信息，并將其加入到數(shù)組closedge中與I相鄰的頂點(diǎn)，將它們與之比較，最小的放入cloedgei.lowcost中將找到的所有定點(diǎn)信息都給K，并輸出closedgek.adjvex,closedgek.lowcost G.vexsk結(jié)束Main（）結(jié)果分析：本課程設(shè)計(jì)的要求對(duì)于任意給定的網(wǎng)和起點(diǎn)，用PRIM算法的基本思想

15、求解出所有的最小生成樹(shù)并輸出這些邊的權(quán)值，所以如何實(shí)現(xiàn)輸出顯示所有的最小生成樹(shù)關(guān)鍵問(wèn)題所在，經(jīng)過(guò)分析調(diào)試，用一個(gè)for語(yǔ)句就可以解決這個(gè)問(wèn)題，從每個(gè)頂點(diǎn)出發(fā)，開(kāi)始每一次遍歷并輸出顯示出來(lái)。算法的時(shí)間和空間性能分析根據(jù)程序中算法的循環(huán)語(yǔ)句可以判斷出普利姆算法的時(shí)間復(fù)雜度為O（n2）算法和圖中的邊數(shù)無(wú)關(guān)。因此普利姆算法適合求稠密網(wǎng)的最小生成樹(shù)，因?yàn)樵谒惴ㄖ杏绵徑泳仃嚨拇鎯?chǔ)結(jié)構(gòu)，在無(wú)向圖中，鄰接矩陣是對(duì)稱的。所以僅需要存儲(chǔ)上三角或下三角的元素，因此需要n(n+1)的存儲(chǔ)空間。測(cè)試結(jié)果界面的截圖輸入的情況的截圖輸出結(jié)果的截圖輸入錯(cuò)誤的截圖七、源程序源程序代碼（有注釋詳解）#include #inclu

16、de #define inf 9999#define max 40#define linelenght 77void prim(int gmax,int n) /* prim的函數(shù) */ int lowcostmax,closestmax; int i,j,k,min; for(i=2;i=n;i+) /* n個(gè)頂點(diǎn)，n-1條邊 */ lowcosti=g1i; /* 初始化 */ closesti=1; /* 頂點(diǎn)未加入到最小生成樹(shù)中 */ lowcost1=0; /* 標(biāo)志頂點(diǎn)1加入U(xiǎn)集合 */ for(i=2;i=n;i+) /* 形成n-1條邊的生成樹(shù) */ min=inf; k=0;

17、 for(j=2;j=n;j+) /* 尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊 */ if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,closestk,k,min); lowcostk=0; /* 頂點(diǎn)k加入U(xiǎn) */ for(j=2;j=n;j+) /* 修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值 */ if(gkjlowcostj) lowcostj=gkj; closestj=k; printf(n); int priline(int h) /* 輸出一條分割線 */ int g; printf(n|); f

18、or(g=0;gh;g+) printf(*); printf(|n); int error() /* 提示錯(cuò)誤信息 */ printf(nn|*E*R*R*O*R*|n); printf(Input errors or Data overflow! please re-enternn); fflush(stdin); /* 清除緩存 */ int adjg(int gmax) /* 建立無(wú)向圖 */ int n,e,i,j,k,v1=0,v2=0,weight=0; printf(Input the number of vertices, number of the edge:); scan

19、f(%d,%d,&n,&e); while(e=n*(n-1)|n=max) error(); printf(Input the number of vertices, number of the edge:); scanf(%d,%d,&n,&e); for(i=1;i=n;i+) for(j=1;j=n;j+) gij=inf; /* 初始化矩陣，全部元素設(shè)為無(wú)窮大 */ for(k=1;kn|v2n|v11|v21) error(); printf(Input the %d on the edge of the starting point, terminal, weights:,k);

20、 scanf(%d,%d,%d,&v1,&v2,&weight); gv1v2=weight; gv2v1=weight; return(n); /* 返回節(jié)點(diǎn)個(gè)數(shù)n */void pri(int gmax,int n) /* 輸出無(wú)向圖的鄰接矩陣 */ int i,j; for(i=0;i=n;i+) printf(%dt,i); for(i=1;i=n;i+) printf(n%dt,i); for(j=1;j=n;j+) /* 輸出邊的權(quán)值 */ if(gij=inf) printf(%ct,354); else printf(%dt,gij); printf(n);void main(

21、) /* 主函數(shù) */ int gmaxmax,n;priline(linelenght); n=adjg(g);priline(linelenght);priline(linelenght); printf(Input the adjacency matrix without directed graph:n); pri(g,n); printf(n); printf(Minimum spanning tree structure:n); prim(g,n); getch();八、測(cè)試數(shù)據(jù)第一組第二組第三組九、課程設(shè)計(jì)項(xiàng)目進(jìn)度表及任務(wù)分配表及任務(wù)分配表進(jìn)度日期 進(jìn)度2011-1-15搜集資料

22、2011-1-16至17設(shè)計(jì)算法2011-1-18 將問(wèn)題分塊，然后分塊寫(xiě)出程序2011-1-19將每塊程序銜接好，進(jìn)行調(diào)試2011-1-20對(duì)程序進(jìn)行最后修改，整理實(shí)驗(yàn)報(bào)告分配表成員座號(hào)項(xiàng)目?jī)?nèi)容序號(hào)蔣家權(quán)15號(hào)編寫(xiě)程序 調(diào)試程序01陳相財(cái)25號(hào)編寫(xiě)程序 調(diào)試程序02吳繼偉6號(hào)收集資料 調(diào)試程序03梁麗春7號(hào) 收集資料 調(diào)試程序04十、設(shè)計(jì)心得 我們?cè)O(shè)計(jì)的題目是最小生成樹(shù)的構(gòu)造，在這次實(shí)踐中遇到了各種問(wèn)題，碰到問(wèn)題有時(shí)總是百思不得其解最開(kāi)始，程序要求輸入數(shù)值時(shí)，如果任意沒(méi)有按照程序給定的類型輸入，程序就會(huì)出現(xiàn)死循環(huán)，雖然加入了檢測(cè)程序段，但是當(dāng)我們不按個(gè)數(shù)輸入的時(shí)候程序也出現(xiàn)了不穩(wěn)定，又進(jìn)入死循環(huán)了。我們想了很多辦法，其中之一就是加入break這個(gè)函數(shù)。不過(guò)，并沒(méi)有出項(xiàng)我們想要的結(jié)果，導(dǎo)致循環(huán)檢測(cè)輸入的函數(shù)while無(wú)法繼續(xù)執(zhí)行，中途就中斷了。有點(diǎn)大失所望，但是我們沒(méi)有氣餒。記得以前老是又用過(guò)清空緩存這個(gè)函數(shù)，會(huì)不會(huì)失這個(gè)原因呢？int error() /* 提示錯(cuò)誤信息 */ printf(nn|*E*R*R*O*R*|n); pr