貪心算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告

1、算法設(shè)計(jì)技巧與分析課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱貪心算法的運(yùn)用實(shí)驗(yàn)序號(hào)姓 名系院專業(yè)班 級(jí)學(xué) 號(hào)實(shí)驗(yàn)口期指導(dǎo)教師成 績(jī)一、實(shí)驗(yàn)?zāi)康恼莆肇澬乃惴ǖ幕靖拍詈蛢蓚€(gè)基本要素熟練掌握貪心算法解決問(wèn)題的基本步驟學(xué)會(huì)利用貪心算法解決實(shí)際問(wèn)題二、實(shí)驗(yàn)內(nèi)容與要求1，實(shí)現(xiàn)貪心算法的經(jīng)典運(yùn)用 Krnskal算法（最小生成樹(shù)）2,實(shí)現(xiàn)貪心算法的經(jīng)典運(yùn)用Pnm算法（最小生成樹(shù)）三、實(shí)驗(yàn)設(shè)備地點(diǎn)：科技樓網(wǎng)絡(luò)實(shí)驗(yàn)室602硬件環(huán)境：Intel Pentium Processor 1.8G , 512M 內(nèi)存，windows 操作系統(tǒng)軟件環(huán)境：VC+6.0五、實(shí)驗(yàn)步驟用Kiuskal算法實(shí)現(xiàn)最小生成樹(shù)算法描述：假設(shè)WN=（V,E）是一

2、個(gè)含有n個(gè)頂點(diǎn)的連通網(wǎng)，則按照克魯斯卡爾算法構(gòu) 造最小生成樹(shù)的過(guò)程為：先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)，而邊集為空的子圖，若將該子圖中 各個(gè)頂點(diǎn)看成是各棵樹(shù)上的根結(jié)點(diǎn)，則它是一個(gè)含有a棵樹(shù)的一個(gè)森林。之后，從網(wǎng)的 邊集E中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹(shù)，則將其加入子圖, 也就是說(shuō)，將這兩個(gè)頂點(diǎn)分別所在的兩棵樹(shù)合成一棵樹(shù)：反之，若該條邊的兩個(gè)頂點(diǎn)己落 在同一棵樹(shù)上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直至森林中 只有一棵樹(shù)，也即子圖中含有n-1條邊為止。G下面給出C語(yǔ)言代碼實(shí)現(xiàn)及說(shuō)明本程序?qū)?shù)的存儲(chǔ)主要是以邊為存儲(chǔ)對(duì)象，即邊的結(jié)構(gòu)體里面有這樣幾個(gè)參數(shù)：1,邊的權(quán)值。

3、2, 邊的一個(gè)頂點(diǎn)。3,邊的另一個(gè)頂點(diǎn)。4,邊是否屬于生成樹(shù)的一條邊（即最小生成樹(shù)邊標(biāo)志）。 由該程序的存儲(chǔ)結(jié)構(gòu)決定了該算法比較適用于邊稀疏的情形，至于邊稠密的情況會(huì)在卜.面的Pnm 算法中給出。在Kiwskal算法中有兩個(gè)比較重要的部分1,對(duì)邊按權(quán)重排序。2,對(duì)一條邊加入子樹(shù)后是否會(huì)產(chǎn) 生回路的判斷即判斷邊的兩個(gè)節(jié)點(diǎn)是否在同一個(gè)樹(shù)中（集合里）對(duì)于問(wèn)題1：可以有各種排序算法，讀者可以自行選擇自己喜歡的排序算法來(lái)替換代碼中的排序 算法。（本處使用選擇排序算法（效率較低），讀者可以自己修改為快速排序或者是對(duì)排序）下面主要講解解決問(wèn)題2,解決這個(gè)問(wèn)題一般借用不相交集的思想，即在本程序中每次以同集合

4、中所有點(diǎn)的編號(hào)最小的數(shù)來(lái)標(biāo)識(shí)本集合。（對(duì)于根節(jié)點(diǎn)即標(biāo)號(hào)最小的節(jié)點(diǎn)則標(biāo)記為0）例如對(duì)于 上圖實(shí)例，下面給出詳細(xì)的不相交集的維護(hù)過(guò)程（給出前幾步的詳細(xì)說(shuō)明）a,初始狀態(tài)（ABCDEFG分別在數(shù)組的第1, 2, 3, 4, 5, 6, 7） 0號(hào)位空置（均為0）0ABCDEFG0b,選擇第一彳0條邊A-D（將0D的標(biāo)記改0為1）（因?yàn)?D最短）0000ABCDEFG0000I000對(duì)表進(jìn)行維護(hù)（維護(hù)后仍同上表，因?yàn)檫€沒(méi)有兩個(gè)集合合并）0ABCDEFG0000I000C,選擇第二條邊C-E （修改上表）0ABCDEFG0000I300對(duì)上表進(jìn)行維護(hù)（任同上表，因?yàn)檫€沒(méi)有兩個(gè)集合合并）0ABCDEFG0

5、000I300D,選擇第三條邊（D-F）（根據(jù)條件DF兩點(diǎn)不再同一集合，改邊可選）然后就合并DF兩點(diǎn)所在的集合D的前去是1,即A標(biāo)記為0, E的標(biāo)記也為0,合并因?yàn)?1 所以表修改如下0ABcDEFG00001310以后幾步均如上判斷兩點(diǎn)是否在一個(gè)集合從而判斷改邊是否可取，并維護(hù)上表下面附上源代碼Kiuskal算法的實(shí)現(xiàn)09 網(wǎng)一 殷賽 0910322113輸入：圖G（用結(jié)構(gòu)體數(shù)組來(lái)存儲(chǔ)每條邊，包含每條邊的節(jié)點(diǎn)） 輸出：圖G的最小生成樹(shù)樹(shù)*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*左*左*：$：*：$：*：$：*/#iiiclude

6、#iiiclude typedef stiuct Edge (char dot_l;char dot_2;int weight;int leap;Edge;Edge* selectioiisort(Edge *arrayint n)選擇排序(對(duì)邊按權(quán)重由高到低排序) (int i jminjemp;fbi(i=0;in;i+)nun=i;fbr(j=i+lJaiTayj .weight)mm=j;iRmni!=i)temp=anayi .weight;airayi. weight=array nini .weight;aiTayfnun .weight=temp;temp=anay i. d

7、o t_ 1;airayi. dot_ 1 =aiTayinin. dot_ 1;array min. dot_ 1 =temp;temp=anay i. d o t_2;arrayi .dot_2=arrayniin dot_2;array min. d ot_2=temp; letuin airay;Edge *Kinskal(Edge *Graph,iiit num_num_v)/克魯斯卡爾算法實(shí)現(xiàn)(int m.njest; mtfoi(i=O;inum_e;i+)fbr(j= l;jnum_v+1 ;j+)if(Giaphi.dod=V0j)m=j;if(Graphi .do

8、t_2=V0 j )n=J；if(V 1 m !=V 1 n&m!=V 1 n&n!=V 1 m)/Z 如果邊的兩個(gè)頂點(diǎn)不再一個(gè)集合則 邊是生成樹(shù)的邊(注意首節(jié)點(diǎn)的標(biāo)記和集合里非首節(jié)點(diǎn)的標(biāo)記不同)Graphi.leap=l;if(Vln=O)JIif(nVln)VlVlm=Vln;elseVlVln=Vlm;)維護(hù)不相交集k=l;對(duì)每個(gè)節(jié)點(diǎn)都檢查是否為標(biāo)記合格節(jié)點(diǎn)while(knum_v+1)一樣的(即標(biāo)記符合標(biāo)準(zhǔn)的節(jié)點(diǎn))(t=Vlk;wlule(Vlt!=O)(t=Vlt;Vlk=t;)k+;if( V 1 m=0&V 1 n=0)/如果邊的兩個(gè)頂點(diǎn)是兩個(gè)集合的首節(jié)點(diǎn)則可以合并Graphi.

9、leap=l;Vlm=n;elseVln=m;維護(hù)不相交集k=l；while(knum_v+1)if(Vlk!=O)(t=Vlk;wlule(Vlt!=O)(t=Vlt;k+;/*printf(”不相交集的情況：iiH);fbr(test= 1 ;testnum_v+1 ;test+) pnntf(”4c”,V0test);fbr(test= 1 ;testnum_v+1 ;test+) printf(,l%-4d fV 1 test);return Graph;void niainQ(int i J ,num_vjium_e ,cost=0;Edge *Graph=NULL;int *V=N

10、ULL;pnntf(”請(qǐng)輸入土中有多少個(gè)頂點(diǎn)!n”)； scanf(n%d,&num_v);V=(mt*)malloc(sizeof(iiit*)*2);fbr(i=0;i2;i+)Vi=(iiit*)malloc(sizeof(mt)*(num_v+1);fbr(i=0;i2;i+)Rr(j=O；jvnum_v+l ；j+)Vij=O;fbr(i= 1 ;inum_v+ l;i+)pnntf(”請(qǐng)輸入第1個(gè)頂點(diǎn)二1);scanff %c,&VOi);printfC請(qǐng)輸入圖中有多少條邊!n)； scanf(n%d,&num_e);Giaph=(Edge*)malloc(sizeof(Edge)

11、*num_e);fbr(i=O ;inum_e;i+)pnntf(”請(qǐng)輸入第1條邊的權(quán)值和兩個(gè)頂點(diǎn)！ n”,i+l);scanf(n%d %c %c”.&Graphi.weight,&Graphi.dot_l ,&Graphi.dot_2);Graphi.leap=O:Graph=selectionsoit(Graphjium_e);以上部分是存儲(chǔ)圖/Graph=Kiiiskal(Graph.num_e,V；num_v);printf(構(gòu)成最小生成樹(shù)的邊和頂點(diǎn)分別是：)；pnntf(”頂點(diǎn)1頂點(diǎn)2邊山”)；fbr(i=O ;inum_e;i+)if(Graphi. leap= 1)printR

12、”%c %c %d n,Graphi.dot_LGraphi.dot_2,Graphi.weight);cost=cost+Graphi .weight;printf(”最小生成樹(shù)的權(quán)值是:%dn,cost);請(qǐng)輸入土中有多少個(gè)頂點(diǎn)*7敏入篡1個(gè)頂京圄$入患6j-頂修F請(qǐng)轍入圖中有參少條邊？11請(qǐng)輸入第i條邊的權(quán)值和兩個(gè)頂點(diǎn)！5 A D請(qǐng)輸入第2條邊的權(quán)值和兩個(gè)頂點(diǎn)！A B請(qǐng)輸入第3條邊的權(quán)值和兩個(gè)頂點(diǎn)！9 B D請(qǐng)輸入第4條邊的權(quán)值和兩個(gè)頂點(diǎn)！B C請(qǐng)輸入第5條邊的權(quán)值和兩個(gè)頂點(diǎn)！B E請(qǐng)輸入第6條邊的權(quán)值和兩個(gè)頂點(diǎn)!S C E請(qǐng)輸入第?條邊的權(quán)值和兩個(gè)頂點(diǎn)！ 帝塞?第8條邊的權(quán)值和兩個(gè)頂點(diǎn)

13、! 整備人第9條邊的權(quán)值和兩個(gè)頂點(diǎn)!E F請(qǐng)輸入第博條邊的權(quán)值和兩個(gè)頂點(diǎn)!E G請(qǐng)輸入第11條邊的權(quán)值和兩個(gè)頂點(diǎn)!11 F G構(gòu)成最、生成樹(shù)的邊和點(diǎn)分別是;A -C A -C -D 一B -A -最泉星成樹(shù)的權(quán)值是：3?Press any key to continueDEFEBG用Prun算法實(shí)現(xiàn)最小生成樹(shù)算法描述：假設(shè)V是圖中頂點(diǎn)的集合,E是圖中邊的集合,TE為最小生成樹(shù)中的邊的集合，則prmi算 法通過(guò)以下步驟可以得到最小生成樹(shù)：1：初始化:U=u 0,TE=f此步驟設(shè)立一個(gè)只有結(jié)點(diǎn)u 0的結(jié)點(diǎn)集U和一個(gè)空的邊集TE作為最 小生成樹(shù)的初始形態(tài)，在隨后的算法執(zhí)行中，這個(gè)形態(tài)會(huì)不斷的發(fā)生變化

14、,直到得到最小生成樹(shù)為止。2:在所有uGU,vev-U的邊(u,v)GE中，找一條權(quán)最小的邊(u 0,v 0),將此邊加進(jìn)集合TE中， 并將此邊的非U中頂點(diǎn)加入U(xiǎn)中。此步驟的功能是在邊集E中找一條邊,要求這條邊滿足以下條件: 首先邊的兩個(gè)頂點(diǎn)要分別在頂點(diǎn)集合U和V-U中，其次邊的權(quán)要最小。找到這條邊以后，把這條邊放 到邊集TE中，并把這條邊上不在U中的那個(gè)頂點(diǎn)加入到U中。這一步驟在算法中應(yīng)執(zhí)行多次,每執(zhí)行 一次，集合TE和U都將發(fā)生變化，分別增加一條邊和一個(gè)頂點(diǎn),因此,TE和U是兩個(gè)動(dòng)態(tài)的集合,這一 點(diǎn)在理解算法時(shí)要密切注意。3:如果U=V,則算法結(jié)束;否則重復(fù)步驟2。可以把本步驟看成循環(huán)終止

15、條件。我們可以算出當(dāng)U=V 時(shí)，步驟2共執(zhí)行了 n-1次（設(shè)n為圖中頂點(diǎn)的數(shù)目）,TE中也增加了 n-1條邊，這n-1條邊就是需要 求出的最小生成樹(shù)的邊（圖任如上圖）下面給出具體c語(yǔ)言代碼和詳解該代碼的存儲(chǔ)結(jié)構(gòu)是鄰接矩陣上三角用來(lái)存儲(chǔ)最小生成樹(shù)的邊，樹(shù)邊用-1標(biāo)記，下三角用來(lái)存儲(chǔ) 原圖，方便輸出最小生成樹(shù)上圖的最后鄰接矩陣如下：（具體實(shí)現(xiàn)和解釋見(jiàn)代碼）（INF代表無(wú)窮， 即不相鄰）0-1INF-1INFINFINF70INFINF-1INFINFINF80INF-1INFINF59INF0INF-1INFINF75150INF-1INFINFINF680INFINFINFINFINF9110/

16、*09 網(wǎng)一 殷賽 0910322113Prun算法的實(shí)現(xiàn)輸入：圖G 輸出：圖G的最小生成樹(shù)*/#iiiclude #iiiclude#defiiie INF 32767*Pnm算法最重要的部分在于從可以挑選的邊中間挑選出最小值并且對(duì)加入后會(huì)產(chǎn)生回路的邊標(biāo)記為不可選（此代碼中將該邊權(quán)值標(biāo)記為INF即無(wú)窮大）每選中一條邊就會(huì)加入一個(gè)點(diǎn)（就必須對(duì)與該點(diǎn)連接的邊進(jìn)行維護(hù)，即多產(chǎn)生回路邊標(biāo)記為無(wú)窮）找最小邊則是從上三角中所有可選的行和列中選擇選中的樹(shù)邊則標(biāo)記為1 （其權(quán)值從下三角讀出）* */void Prim(int *Graph.iiit num_v)/轉(zhuǎn)化為對(duì)上三角的維護(hù)(int iJJeap=

17、Ojemp;int m,n jiiin;int *a=(int *)malloc(sizeof(int)*num_v);for(i=0 ;inum_v;i+)ai=0；a0=l;wliile(leap !=num_v-l)nun=INF:foi(i=0;inum_v;i+)/搜索上三角中的最小值/Iif(ai=l)/Ifbr(j=i+ ljGraphi0&Graphi0O)(nun=GraphiIj;m=j;n=i；tenip=0;)for(j=OjviJ+) 列中搜索if(minGraphj i&Graphj i0)nun=Graphji;m=j;n=i;tenip=l;)if(temp=O

18、)為了區(qū)別出是在行還是在列中搜索到的元素Graphnm=-1;elseGraphmn=-1;for(i=0;i0)fGraphfi m=INF;for(i=m+l ;i0)fGraphm i=INF:am=l;/*foi（i=0;inum.v;i+）/檢查矩陣中在那些行（列）可以選擇最小值（即那些列和行是候選行和列）/*for(i=0;inum_v;i+)/檢驗(yàn)對(duì)上三角的維護(hù)，和下三角是否修改了(下三角保存了原樹(shù)和用于輸出最小生成樹(shù))Ifbr(j=0 ;j num_vj+)pnntff%4dt”,Graphij);pnntf(nnM);*/leap+;void main。(int ij;int

19、 num_v4ium_e;int *Graph=NULL;char *V=NULL;char ch_l,ch_2;int weight;int m.n;printf(請(qǐng)輸入圖的頂點(diǎn)數(shù)：)；scanf(n%d,&num_v);V=(chai*)nialloc(sizeof(char)*num_v);Graph=(mt*)malloc(sizeof(mt*)*num_v)-J!動(dòng)態(tài)生成維數(shù)組用來(lái)存儲(chǔ)圖(鄰接矩陣)fbr(i=O ;inum_v;i-H-)Graphi=(mt*)malloc(sizeof(int)*num-v);for(i=0 ;inum_v;i+)/ 初始化矩陣Graphij=INF;fbr(i=O ;inum_v;i-H-)Graphii=O;fbr(i=O ;inum_v;i-H-)pnntf(”請(qǐng)輸入第1個(gè)頂點(diǎn):”,i+1);scanff %c”,&Vi);pnntf(請(qǐng)輸入圖的邊數(shù)：”)；scanf(%d,&num_e);fbr(i=O;inum_e;i-H-)pnntf(”請(qǐng)輸入第1條邊的頂點(diǎn)和權(quán)值二i+1);scan町 %c %c%d”.&ch_l,&ch_2,&weight);fbr(j=0;j num_vj+