1、前言從學習數(shù)據(jù)結構這門課程開始，我已發(fā)現(xiàn)了學習算法的樂趣，在學習這門課的過程中也學到了許多計算機應用基礎知識，對計算機的機體也有了一個初步的了解，又在課余時間閱讀了大量有關算法設計與分析的圖書，在此基礎上，利用貪心算法，編寫了一個用prim和kruskal算法求解最小生成樹，也以此檢驗自己一學期所學成果，加深對算法設計與分析這門課程的理解，由于所學知識有限，難免有些繁瑣和不完善之處，下面向大家介紹此程序的設計原理，方法，內容及設計的結果。本程序是在windows 環(huán)境下利用Microsoft Visual C+ 6.0所編寫的，主要利用貪心算法的思想，以及數(shù)組，for語句的循環(huán)，if語句的嵌套

2、，運用以上所學知識編寫出的prim和kruskal算法求解最小生成樹，在輸入其邊的起始位置，種植位置以及權值后，便可分別輸出此網(wǎng)的prim和kruskal算法最小生成樹的邊的起始位置，終止位置以及權值。正文2.1 設計方法和內容一.軟件環(huán)境：Microsoft Visual C+ 6.0二.詳細設計思想：所謂貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。 貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。 貪心算法的基本思路如下： 1.建立數(shù)學

3、模型來描述問題。 2.把求解的問題分成若干個子問題。 3.對每一子問題求解，得到子問題的局部最優(yōu)解。 4.把子問題的解局部最優(yōu)解合成原來解問題的一個解。 1.Prim（普里姆）算法思想無向網(wǎng)的最小生成樹問題此算法的思想是基于點的貪心，力求從源點到下一個點的距離最短，以此來構建臨接矩陣，所以此算法的核心思想是求得源點到下一個點的最短距離，下面具體解釋如何求此最短距離：在圖中任取一個頂點k作為開始點，令集合U=k,集合w=V-U,其中v為圖中所有頂點的集合，然后找出：一個頂點在集合U中，另一個頂點在集合W中的所有邊中，權值最短的一條邊，并將該邊頂點全部加入集合U中，并從W中刪去這些頂點，然后重新調

4、整U中頂點到W中頂點的距離，使之保持最小，在重復此過程，直到W為空集為止，求解過程如下：由圖可知最小生成樹的步驟，假設開始頂點就選為1，故首先有u=1，w=2,3,4,5。2.kruskal(克魯斯卡爾)算法的基本思想kruskal(克魯斯卡爾)算法的基本思想是：將無向圖的所有邊按權值遞增順序排列，依次選定權值數(shù)較小的邊，但要求后面選取的邊不能與前面選區(qū)的邊構成回路，若構成回路，則放棄該條邊，然后再選后面權值較大的邊，n個頂點的圖中，選取n-1條邊即可。注意：kruskal算法的貪心是從源點到下一個點的距離最短。prim算法的貪心是任意點到生成樹的距離最短，也就是邊的最小。三，設計方法與內容：

5、1.Prim（普里姆）算法：假設網(wǎng)用鄰接矩陣作存儲結構，與圖的鄰接矩陣類似，只是將0變?yōu)闊o窮，1變?yōu)閷吷蠙嘀?，而矩陣中對角線上的元素為0。（1）定義網(wǎng)中的頂點數(shù)，網(wǎng)的邊數(shù)，這里將網(wǎng)的頂點數(shù)定為6個，網(wǎng)的邊數(shù)定為10個。(2) 定義一個名為edgeset類，其數(shù)據(jù)成員fromvex,endvex,weight,分別為一條邊的起點，終點和權值。（3）定義一個名為tree的類，定義了一個最小生成樹邊集的數(shù)組，用數(shù)組記錄具有最小代價的邊，找到后，將該邊作為最小生成樹的樹邊保存起來，再定義一個普里姆算法的成員函數(shù)prim(tree &t)。（4）對prim(tree &t)函數(shù)進行類外定義，分別將頂

6、點數(shù)定義為k,邊為m, 權值為w,定義一個變量min，使其等于32767，即無窮大，利用for循環(huán)從頂點1出發(fā)求最小生成的數(shù)邊，即設t.cti.fromvex=1。令終止點t.cti.endvex=i+1,令t.cti.weight=t.s1i+1,再利用第二個for循環(huán)找到權值最小的樹邊，從頂點為2開始循環(huán)，當j=k-1且小于網(wǎng)中總頂點數(shù)時，權值小于無窮則將此權值付給min,并令邊m=j。（5）重新修改樹邊的距離，將原來的邊用權值小的邊替換，若當前邊k小于n(原定邊數(shù))，則令 tl=t.cti.endvex，w=t.sjtl，若wt.cti.weight，則令 t.cti.weight=w，

7、t.cti.fromvex=j。（6）最后利用for循環(huán)鍵入每條邊的起始點，終結點及邊上的權值。2.kruskal算法：（1）定義網(wǎng)中的頂點數(shù)，網(wǎng)的邊數(shù)，這里將網(wǎng)的頂點數(shù)定為6個，網(wǎng)的邊數(shù)定為10個。（2）定義一個名為edgeset2的類，其數(shù)據(jù)成員fromvex,endvex,weight,分別為一條邊的起點，終點和權值。（3）定義一個名為tree2的類，定義了一個最小生成樹邊集的數(shù)組，用edgeset ge2e+1存放網(wǎng)中所有的邊，定義一個s2n+1n+1，s為一個集合，一行元素si0sin表示一個集合，若sit=1。則表示頂點t屬于該集合，否則不屬于該集合，再定義一個普里姆算法的成員函數(shù)

8、kruskal(tree2 &t2)。（4）對kruskal(tree2 &t2)函數(shù)進行類外定義,定義k并設初值為1用來統(tǒng)計生成樹的邊數(shù)，定義d并設初值為1用來表示待掃描邊的下標位置，定義兩個變量m1,m2用來記錄一條邊的兩個頂點所在集合的序號，如果t2.ge2d.fromvex=j且t2.s2ij=1，則令m1=i，若t2.ge2d.endvex=j且t2.s2ij=1則令m2=i，最后判斷m1是否等于m2，若不等于則令t2.c2k=t2.ge2d，k自加，求出一條邊后，合并兩個集合，另一個集合設置為空。（6）最后利用for循環(huán)鍵入每條邊的起始點，終結點及邊上的權值，要求輸入的網(wǎng)中的邊上的

9、權值必須為從大到小排列，調用kruskal（t）循環(huán)輸出一條邊的起始點，終結點及邊上的權值。 2.3設計流程圖定義數(shù)據(jù)成員fromvex,endvex,weight,分別為一條邊的起點，終點和權值。定義網(wǎng)中的頂點數(shù)n=6，網(wǎng)的邊數(shù)e=10從頂點1出發(fā)求最小生成樹的邊先找權值最小的樹邊, 然后重新修改樹邊的距離, 原來的邊用權值較小的邊取代最后利用for循環(huán)鍵入每條邊的起始點，終結點及邊上的權值Prim算法Kruskal算法定義了一個最小生成樹邊集的數(shù)組，用edgeset ge2e+1存放網(wǎng)中所有的邊定義一個s2n+1n+1，s為一個集合，一行元素si0sin表示一個集合，若sit=1。則表示頂

10、點t屬于該集合，否則不屬于該集合定義k并設初值為1用來統(tǒng)計生成樹的邊數(shù)，定義d并設初值為1用來表示待掃描邊的下標位置，定義兩個變量m1,m2用來記錄一條邊的兩個頂點所在集合的序號圖2-22.4 設計結論Prim算法：在圖中任取一個頂點k作為開始點，令集合U=k,集合w=V-U,其中v為圖中所有頂點的集合，然后找出：一個頂點在集合U中，另一個頂點在集合W中的所有邊中，權值最短的一條邊，并將該邊頂點全部加入集合U中，并從W中刪去這些頂點，然后重新調整U中頂點到W中頂點的距離，使之保持最小，在重復此過程，直到W為空集為止Kruskal算法：將無向圖的所有邊按權值遞增順序排列，依次選定權值數(shù)較小的邊，

11、但要求后面選取的邊不能與前面選區(qū)的邊構成回路，若構成回路，則放棄該條邊，然后再選后面權值較大的邊，n個頂點的圖中，選取n-1條邊即可。其中兩個算法的貪心思想有本質的區(qū)別：kruskal算法的貪心是從源點到下一個點的距離最短。而prim算法的貪心是任意點到生成樹的距離最短，也就是邊的最小。有關說明（1） 程序運行剛開始會出現(xiàn)一個界面：*請選擇一種算法* 1.prim 算法求解最小生成樹 2.kruskal 算法求解最小生成樹此時便可輸入用戶想要選擇的數(shù)值，回車然后進入如（圖一或圖二）的界面。（2）接著根據(jù)提示輸輸入一條邊的起始點，終結點及邊上的權值，如（圖三）界面 。 （3）重復步驟（2）十次。

12、（5）即可顯示此算法下的最小生成樹。如（圖四）界面。致謝這次課程設計實訓老師給我了很大的幫助，讓我發(fā)現(xiàn)了自身的不足之處，在實際操作過程中犯的一些錯誤，同時還有有意外的收獲。在具體操作中對這學期所學的數(shù)據(jù)結構的理論知識得到鞏固，達到實訓的基本目的，同時也認識到在以后的上機中應更加注意自己曾犯的錯誤，也發(fā)現(xiàn)上機實訓的重要作用，特別是對數(shù)組和鄰接矩陣有了深刻的理解。通過實際操作，學會數(shù)據(jù)結構程序編程的基本步驟、基本方法，開發(fā)了自己的邏輯思維能力，培養(yǎng)了分析問題、解決問題的能力。 在此感謝學院領導，老師們給我們提供了這樣一個良好的平臺，讓我們學有所用，把我們所學的理論知識與實踐結合，鍛煉了自己動手操作

13、的能力，希望自己以后有機會多進行這樣的實訓，培養(yǎng)自身獨立思考問題的能力，提高實際操作水平。參考文獻 1 李根強C+數(shù)據(jù)結構2005年1月第一版 中國水利水電出版社 2侯識忠數(shù)據(jù)結構算法程序集 3 -01/tp 譚浩強 C程序設計 2005年7月第三版 清華大學出版社 1-378頁。4顧仁 高級C+語言程序設計技巧與實例1995年11月第一版 機械工業(yè)出版社 1-462頁5 陳明數(shù)據(jù)結構（C+版）2005年3月第一版 清華大學出版社6 -01/tp 譚浩強 C+面向對象程序設計2006年1月第一版清華大學出版社 1-288頁7 王曉東數(shù)據(jù)結構C+語言2005年7月第一版 清華大學出版社附錄：/*

14、prim算法*#includeconst int n=6; /網(wǎng)中頂點數(shù)const int e=10; /網(wǎng)中邊數(shù)class edgeset /定義一條生成樹的邊的類public: int fromvex; /邊的起點 int endvex; /邊的終點 int weight; /邊的權值;class treepublic: int sn+1n+1; /網(wǎng)的鄰接矩陣 edgeset ctn+1; /最小生成樹的邊集 void prim(tree &t); /普里姆算法;void tree:prim(tree &t) int i,j,k,min,tl,m,w; /k為當前頂點數(shù),m為當前邊數(shù),w

15、為當前權值 for(i=1;in;i+) /從頂點1出發(fā)求最小生成樹的邊t.cti.fromvex=1; t.cti.endvex=i+1; t.cti.weight=t.s1i+1; for(k=2;k=n;k+) min=32767; m=k-1; for(j=k-1;jn;j+) /找權值最小的樹邊 if(t.ctj.weightmin) min=t.ctj.weight; m=j; edgeset temp=t.ctk-1; t.ctk-1=t.ctm; t.ctm=temp; j=t.ctk-1.endvex; for(i=k;in;i+) /重新修改樹邊的距離 tl=t.cti.e

16、ndvex; w=t.sjtl; if(wt.cti.weight) /原來的邊用權值較小的邊取代t.cti.weight=w; t.cti.fromvex=j; /*kruskal算法*class edgeset2public: int fromvex; int endvex; int weight;class tree2 /定義生成樹public:edgeset c2n; /存放生成樹的邊edgeset ge2e+1; /存放網(wǎng)中所有邊int s2n+1n+1; /s為一個集合，一行元素si0sin表示一個集合 /若sit=1。則表示頂點t屬于該集合，否則不屬于void kruska(tr

17、ee2 &t2);void tree2:kruska(tree2 &t2)int i,j;for(i=1;i=n;i+)for(j=1;j=n;j+)if(i=j) t2.s2ij=1;else t2.s2ij=0;int k=1; /統(tǒng)計生成樹的邊數(shù)int d=1; /表示待掃描邊的下標位置int m1,m2; /記錄一條邊的兩個頂點所在集合的序號while(kn) for(i=1;i=n;i+) for(j=1;j=n;j+) if(t2.ge2d.fromvex=j)&(t2.s2ij=1) m1=i; if(t2.ge2d.endvex=j)&(t2.s2ij=1) m2=i; if(

18、m1!=m2)t2.c2k=t2.ge2d;k+;for(j=1;j=n;j+)t2.s2m1j=t2.s2m1j|t2.s2m2j; /求出一條邊后，合并兩個集合t2.s2m2j=0; /另一個集合設置為空d+;void main() int z;for(z=1;z=3;z+) cout*請選擇一種算法*endl; cout1.prim 算法求解最小生成樹 endl; cout2.kruskal 算法求解最小生成樹 z; if(z=1) int j,w; tree t; coutprim算法求最小生成樹endl; cout請連續(xù)輸入網(wǎng)的10條邊endl;for(int i=1;i=n;i+)for(int j