圖的最小生成樹C

1、西北師范大學(xué)地環(huán)學(xué)院地理信息系數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)講義十二 最小生成樹張長(zhǎng)城2011-2-8圖的最小生成樹，Prim算法，C語(yǔ)言實(shí)現(xiàn)實(shí)驗(yàn)任務(wù)描述1 有向含權(quán)圖的存儲(chǔ)設(shè)計(jì)；2 分析圖的最小生成樹的算法；3 C語(yǔ)言實(shí)現(xiàn)圖的最小生成樹。一、 有向圖的存儲(chǔ)和最小生成樹算法分析1 Prim最小生成樹對(duì)一個(gè)圖而言，最小生成樹的算法經(jīng)常用到的是Prim算法。以下圖為例：圖 1 有向圖的范例圖Prim的算法，主要是構(gòu)造兩個(gè)集合：U、V，其中，U中有第0個(gè)頂點(diǎn)，V中有其余的頂點(diǎn)，一般編程中，設(shè)NO(NO=10000)為已經(jīng)使用，則開始狀態(tài)就是：V集合中，第0個(gè)元素是NO，代表已經(jīng)放入U(xiǎn)集合，其余的是頂點(diǎn)編號(hào)；U集合中，

2、第0個(gè)元素是0，代表第0個(gè)頂點(diǎn)在V集合。UV0NO,1,2,3,4,5表1 計(jì)算開始的狀態(tài)在這個(gè)時(shí)候，考慮的第一步就是：從U中取到頂點(diǎn)編號(hào)、與V中的頂點(diǎn)中尋找最短距離的頂點(diǎn)，根據(jù)圖1，則自然是到U中的0到V中的2、就是V1到V3，于是，把該頂點(diǎn)放入U(xiǎn)集合，V集合中標(biāo)記已經(jīng)使用，就是：UV0,2NO,1,NO,3,4,5表2 找到第一個(gè)最小鄰接頂點(diǎn)圖中表示就是：圖 2找到第一個(gè)最短鄰接頂點(diǎn)U中有兩個(gè)頂點(diǎn)，就是從U中逐個(gè)取0、2頂點(diǎn)，和V中各個(gè)頂點(diǎn)中對(duì)比，找到下一個(gè)最短距離的頂點(diǎn)，根據(jù)圖1、不難發(fā)現(xiàn)是U中的2到V中的5，就是V3到V6。于是再次把5放入U(xiǎn)集合，V中標(biāo)記6已經(jīng)使用，表處理如下：UV0

3、,2,5NO,1,NO,3,4,NO表3 找到第二個(gè)最小鄰接頂點(diǎn)這個(gè)過(guò)程的結(jié)果就是相當(dāng)于V3連接到V6，有下圖： 圖 3找到第二個(gè)最短鄰接頂點(diǎn)注意表3，再次從U中逐個(gè)取出頂點(diǎn)、和V中未使用的頂點(diǎn)逐個(gè)對(duì)比，尋找最小路徑的頂點(diǎn)，可以找到是U中的5到V中的3，就是V6到V4，于是表格再次處理如下：UV0,2,5,3NO,1,NO,NO,4,NO表4 找到第三個(gè)最小鄰接頂點(diǎn)所生成的圖就是： 圖 4找到第三個(gè)最短鄰接頂點(diǎn)由于表4中還有沒使用的頂點(diǎn)，于是再次逐個(gè)從U中取頂點(diǎn)、逐個(gè)和V中的頂點(diǎn)對(duì)比，尋找最短路的頂點(diǎn)，不難發(fā)現(xiàn)有U中2到V中1、就是V3到V2距離最短，于是再次處理表4、成為：UV0,2,5,3

4、,1NO,NO,NO,NO,4,NO表5 找到第四個(gè)最小鄰接頂點(diǎn)生成的圖就是： 圖 5找到第四個(gè)最短鄰接頂點(diǎn) 最后，再次從U中逐個(gè)取頂點(diǎn)，尋找和V中頂點(diǎn)最小距離的頂點(diǎn)，就是1到4相當(dāng)與V2到V5，處理表格5為：UV0,2,5,3,1,4NO,NO,NO,NO,NO,NO表6 找到第五個(gè)最小鄰接頂點(diǎn)處理到圖就是：圖 6最終的最小生成樹由于V集合中所有頂點(diǎn)都被使用了，所以程序到此停止。2 C語(yǔ)言的含權(quán)圖的存儲(chǔ)對(duì)含權(quán)圖，其不連接數(shù)學(xué)上是無(wú)窮大，這在C語(yǔ)言中是無(wú)法實(shí)現(xiàn)的，所以一般用一個(gè)大數(shù)來(lái)表示，比如用1000，在上述圖中，這個(gè)數(shù)字是足夠了。所以這個(gè)鄰接矩陣就是：A=圖1的鄰接矩陣這個(gè)寫法表明：C語(yǔ)言

5、中的含權(quán)鄰接矩陣和普通鄰接矩陣沒有什么差別，差別僅僅在程序處理中：一旦遇到一個(gè)指定的大數(shù)，則認(rèn)為是不通的，由此可知對(duì)圖的存儲(chǔ)結(jié)構(gòu)不需要做任何變動(dòng)。3 C語(yǔ)言Prim最小生成樹程序設(shè)計(jì)首先我們要有兩個(gè)集合，用來(lái)表示U、V，對(duì)于大的圖，最好使用鏈表，而對(duì)于我們這個(gè)簡(jiǎn)單的圖，僅僅使用數(shù)組來(lái)表示就足夠了。我們把圖1中鄰接矩陣的1000在C中定義為NO，這樣方便后續(xù)的處理。開始，我們將在U數(shù)組中保存0，而在V數(shù)據(jù)中保存:NO、1、2、3、4，這代表著先把第0個(gè)頂點(diǎn)存進(jìn)U集合，而第1、第2、第3.等后續(xù)的頂點(diǎn)在V集合，并且設(shè)置n變量記錄進(jìn)入U(xiǎn)集合中的頂點(diǎn)個(gè)數(shù)，這樣就完成了初始化操作。對(duì)于圖，我們依然使用前

6、面的存儲(chǔ)結(jié)構(gòu)，所以圖的頂點(diǎn)個(gè)數(shù)可以來(lái)自于G->num，而U、V的大小可以通過(guò)動(dòng)態(tài)申請(qǐng)內(nèi)存來(lái)完成。所以整個(gè)初始化工作可以用以下程序完成：12345678int *U,*V,i,j,n,min,a,b,ma,mb;U=(int *)malloc(sizeof(int)*G->num);V=(int *)malloc(sizeof(int)*G->num);for(i=0;i<G->num;i+)Ui=0;Vi=i;V0=NO;n=1;表7 PRIM最小生成樹初始化 見P0.c下一步，就是要有函數(shù)來(lái)判斷V集合中是否全部取空了，這個(gè)集合全部為空，就是說(shuō)所有的值都是NO，為

7、此我們要編寫一個(gè)函數(shù)來(lái)做判斷，就是：1234567int VEmpty(int V,int n)int i;for(i=0;i<n;i+)if(Vi!=NO) return 0;return 1;表8 判斷V集合中頂點(diǎn)是否全部取空 見P0.c完成這樣的初始化后，則就是從U中取出一個(gè)頂點(diǎn)編號(hào)、逐個(gè)取出V中的頂點(diǎn)編號(hào)、然后尋找最短的路徑，設(shè)置min開始是NO，第一步寫成草稿就是：a=Ui; b=Vj;if (b=NO) 取下一個(gè)V中頂點(diǎn); /說(shuō)明這個(gè)頂點(diǎn)已經(jīng)在U中if (G->pAab<min)min=G->pAab;ma=a;mb=b; /記錄最小距離的兩個(gè)頂點(diǎn)編號(hào)找到m

8、a、mb后，要把mb轉(zhuǎn)入U(xiǎn)，然后n+，就是：Un=mb; Vmb=NO;n+;于此同時(shí)打印頂點(diǎn)關(guān)系：printf("%s->%sn",G->pVma,G->pVmb);于是整個(gè)函數(shù)就是下表：寫成一個(gè)完整的C語(yǔ)言程序就是：12345678910111213141516171819202122232425262728293031void Prim(struct Graph *G)int *U,*V,i,j,n,min,a,b,ma,mb;U=(int *)malloc(sizeof(int)*G->num);V=(int *)malloc(sizeof(

9、int)*G->num);for(i=0;i<G->num;i+)Ui=0;Vi=i;V0=NO;n=1;while(!VEmpty(V,G->num) min = NO;a=0;b=0;for(i=0;i<n;i+) for(j=0;j<G->num;j+)a=Ui; b=Vj;if (b=NO) continue; if (G->pAab<min)min=G->pAab;ma=a;mb=b;printf("%s->%sn",G->pVma,G->pVmb); Un=mb; Vmb=NO;n+;

10、free(U);free(V);表9 PRIM最小生成樹初始化 見P0.c123456789101112131415161718main()int i,j;struct Graph *G;G=GraphCreat("p182G726.txt");printf("頂點(diǎn)名稱:n");for(i=0;i<G->num;i+)printf("%st",G->pVi);printf("n鄰接矩陣:n");for(i=0;i<G->num;i+) for(j=0;j<G->num;j+)printf("%dt",G->pAij);printf("