普里姆算法求最小生成樹(shù)

1、word某某航空航天大學(xué)課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：Prim算法求最小生成樹(shù)院系：計(jì)算機(jī)學(xué)院 專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)物聯(lián)網(wǎng)方向 班級(jí): 學(xué)號(hào): 某某: 指導(dǎo)教師:指導(dǎo)教師評(píng)語(yǔ):簽名:審査結(jié)詒學(xué)術(shù)誠(chéng)信聲明本人聲明：所呈交的報(bào)告含電子版與數(shù)據(jù)文件是我個(gè)人在導(dǎo)師指 導(dǎo)下獨(dú)立進(jìn)展設(shè)計(jì)工作與取得的研究結(jié)果。盡我所知，除了文中特別 加以標(biāo)注或致謝中所羅列的內(nèi)容以外，報(bào)告中不包含其他人己經(jīng)發(fā)表 或撰寫(xiě)過(guò)的研究結(jié)果，也不包含其它教育機(jī)構(gòu)使用過(guò)的材料。與我一 同工作的同學(xué)對(duì)本研究所做的任何貢獻(xiàn)均己在報(bào)告中做了明確的說(shuō)明 并表示了謝意。報(bào)告資料與實(shí)驗(yàn)數(shù)據(jù)假如有不實(shí)之處，本人愿意承受 本

2、教學(xué)環(huán)節(jié)“不與格和“重修或重做的評(píng)分結(jié)論并承當(dāng)相關(guān)一切 后果。本人簽名：日期：2015年1月15日某某航空航天大學(xué)課程設(shè)計(jì)任務(wù)書(shū)課程設(shè)計(jì)名稱(chēng)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)專(zhuān)業(yè)計(jì)算機(jī)科學(xué)與技術(shù)物聯(lián)網(wǎng)方向?qū)W生某某班級(jí)學(xué)號(hào)題目名稱(chēng)Prim算法生成最小生成樹(shù)起止日期2015 年 1 月 5日起至2015 年1月 16 日止課設(shè)內(nèi)容和要求：在n個(gè)城市之間建立網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法，利用Prim算法輸出n個(gè)城市之間網(wǎng)絡(luò)圖，輸出n個(gè)節(jié)點(diǎn)的最小生成樹(shù)。其中，n個(gè)城市 表示n個(gè)節(jié)點(diǎn)，兩個(gè)城市間如果有路如此用邊連接，生成一個(gè)n個(gè)節(jié)點(diǎn)的邊權(quán)樹(shù)，要求鍵盤(pán)輸入。參考資料：算法與數(shù)據(jù)結(jié)構(gòu)，嚴(yán)蔚敏、吳偉民，清華大學(xué)，

3、2006C程序設(shè)計(jì)，譚浩強(qiáng)，清華大學(xué)，2010教研室審核意見(jiàn)：教研室主任簽字：指導(dǎo)教師簽名年月日學(xué)生簽名2015 年 1 月15 日目錄學(xué)術(shù)誠(chéng)信聲明-1 -一課程設(shè)計(jì)目的和要求-4 -1.1課程設(shè)計(jì)目的-4-1.2課程設(shè)計(jì)的要求-4- 二實(shí)驗(yàn)原理分析-5 -2.1最小生成樹(shù)的定義-5 -2.2 Prim算法的根本思想-5 -三概要分析和設(shè)計(jì)-8 -3.1概要分析-8-3.2概要設(shè)計(jì)-9 -四測(cè)試結(jié)果-14 -實(shí)驗(yàn)一 -14 -實(shí)驗(yàn)二-14 -4.3實(shí)驗(yàn)三-15 -參考文獻(xiàn)-16 -附錄關(guān)鍵局部程序清單-17 -一課程設(shè)計(jì)目的和要求1.1 課程設(shè)計(jì)目的（一）根據(jù)算法設(shè)計(jì)需要，掌握連通網(wǎng)的數(shù)據(jù)表示

4、方法;（二）掌握最小生成樹(shù)的Prim算法；（三）學(xué)習(xí)獨(dú)立撰寫(xiě)報(bào)告文檔。1.2 課程設(shè)計(jì)的要求在n個(gè)城市之間建立網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法，利用Prim算法輸出n個(gè)城市之間網(wǎng)絡(luò)圖，輸出n個(gè)節(jié)點(diǎn)的最小生成樹(shù)。其中，n個(gè)城 市表示n個(gè)節(jié)點(diǎn)，兩個(gè)城市間如果有路如此用邊連接，生成一個(gè) n個(gè)節(jié)點(diǎn)的邊權(quán) 樹(shù)，要求鍵盤(pán)輸入。二實(shí)驗(yàn)原理分析2.1最小生成樹(shù)的定義一個(gè)有n個(gè)結(jié)點(diǎn)的連通圖的生成樹(shù)是原圖的極小連通子圖， 且包含原圖中的 所有n個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊。最小生成樹(shù)可以用 kruskal 克 魯斯卡爾算法或Prim普里姆算法求出。(1) .最小生成樹(shù)的概述在一給定的無(wú)向圖G =

5、(V, E)中，(u, v)代表連接頂點(diǎn)u與頂點(diǎn)v的邊即，而w(u, v)代表此邊的權(quán)重，假如存在T為E的子集即且為無(wú)循環(huán)圖，使得w(T)最小，如此此T為G的最小生成樹(shù)。最小生成樹(shù)其實(shí)是最小權(quán)重生成樹(shù)的簡(jiǎn)稱(chēng)(2) . 最小生成樹(shù)的分析構(gòu)造最小生成樹(shù)可以用多種算法。其中多數(shù)算法利用了最小生成 樹(shù)的下面一種簡(jiǎn)稱(chēng)為MST的性質(zhì)：假設(shè)N=(V,E) 是一個(gè)連通網(wǎng)，U 是頂點(diǎn)集V的一個(gè)非空子集。假如(u,v)是一條具有最小權(quán)值代價(jià) 的邊，其中u U，v V-U，如此必存在一棵包含邊(u.v)的最小生成 樹(shù)。2.2 Prim 算法的根本思想假設(shè)G = V, E是一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是

6、G的最小生成 樹(shù)，其中U是T的頂點(diǎn)集，TE是T的邊集，U和TE的初值均為空集。算法開(kāi)始時(shí)， 首先從V中任取一個(gè)頂點(diǎn)假定取 V0，將它并入U(xiǎn)中，此時(shí)U=V0，然后只要 U是V的真子集，就從那些其一個(gè)端點(diǎn)已在 T中，另一個(gè)端點(diǎn)仍在T外的所有邊 中，找一條最短即權(quán)值最小邊，假定為i,j丨，其中Vi U,Vj (V-U),并把 該邊i,j和頂點(diǎn)j分別并入T的邊集TE和頂點(diǎn)集U,如此進(jìn)展下去，每次往生成樹(shù)里并入一個(gè)頂點(diǎn)和一條邊，直到n-1次后就把所有n個(gè)頂點(diǎn)都并入到生成樹(shù)T的頂點(diǎn)集中，此時(shí)U=V TE中含有n-1條邊，T就是最后得到的最小生成樹(shù)。 可以看出，在普利姆算法中，是采用逐步增加U中的頂點(diǎn)，常稱(chēng)

7、為“加點(diǎn)法。為了實(shí)現(xiàn)這個(gè)算法在本設(shè)計(jì)中需要設(shè)置一個(gè)輔助數(shù)組closedge，以記錄從U到V-U具有最小代價(jià)的邊。當(dāng)輔助數(shù)組中存在兩個(gè)或兩個(gè)以上的最小代價(jià)的邊時(shí)， 此時(shí)最小生成樹(shù)的形態(tài)就不唯一，此時(shí)可以在程序中采用遞歸的算法思想求出每 個(gè)最小生成樹(shù)。(1). 在prim算法中要解決兩個(gè)問(wèn)題1) 在無(wú)向網(wǎng)中，當(dāng)從一個(gè)頂點(diǎn)到其他頂點(diǎn)時(shí)，假如其邊上的權(quán)值相等，如此可能從某一起點(diǎn)出發(fā)時(shí)，會(huì)得到不同的生成樹(shù)，但最小生成樹(shù)的權(quán)值必定相等，此時(shí)我們應(yīng)該如何把所有的最小生成樹(shù)求解出來(lái)；2) 每次如何從生成樹(shù)T中到T外的所有邊中，找出一條權(quán)值最小的邊。例如，在第k次1< k< n-1丨前，生成樹(shù)T中已

8、有k個(gè)頂點(diǎn)和k-1條邊，此時(shí)T 中到T外的所有邊數(shù)為k(n-k)，當(dāng)然它也包括兩頂點(diǎn)間沒(méi)有直接邊相連，其 權(quán)值被看作常量的邊在內(nèi)，從如此多的邊中找出最短的邊，其時(shí)間復(fù)雜度0k n-k，是很費(fèi)時(shí)間的，是否有好的方法能夠降低查找最短邊的時(shí)間復(fù) 雜度。.上述問(wèn)題的解決方法針對(duì)1中出現(xiàn)的問(wèn)題，可以通過(guò)算法來(lái)實(shí)現(xiàn)，詳情請(qǐng)看Prim算法的概述；針對(duì)2中出現(xiàn)的問(wèn)題，通過(guò)對(duì)Prim算法的分析，可以使查找最短邊的時(shí)間 復(fù)雜度降低到0(n-k)。具體方法是假定在進(jìn)展第k次前已經(jīng)保存著從T中到T外 的每一頂點(diǎn)共n-k個(gè)頂點(diǎn)的各一條最短邊，進(jìn)展第k次時(shí)，首先從這n-k條最短邊中，找出一條最最短的邊，它就是從 T中到T

9、外的所有邊中的最短邊，假 設(shè)為i,j丨，此步需進(jìn)展n-k次比擬；然后把邊i,j和頂點(diǎn)j分別并入T中的 邊集TE和頂點(diǎn)集U中，此時(shí)T外只有n-(k+1)個(gè)頂點(diǎn)，對(duì)于其中的每個(gè)頂點(diǎn)t， 假如j,t丨邊上的權(quán)值小于已保存的從原 T中到頂點(diǎn)t的最短邊的權(quán)值，如此用 j,t丨修改之，使從T中到T外頂點(diǎn)t的最短邊為j,t丨，否如此原有最短邊保 持不變，這樣，就把第k次后從T中到T外每一頂點(diǎn)t的各一條最短邊都保存下 來(lái)了，為進(jìn)展第k+1次運(yùn)算做好了準(zhǔn)備，此步需進(jìn)展 n-k-1次比擬。所以，利用 此方法求第k次的最短邊共需比擬2(n-k)-1次，即時(shí)間復(fù)雜度為0(n-k)。三概要分析和設(shè)計(jì)3.1概要分析通過(guò)對(duì)

10、上述算法的分析，將從以下三方面來(lái)進(jìn)展分析:(1) .輸入數(shù)據(jù)的類(lèi)型在本次設(shè)計(jì)中，是對(duì)無(wú)向圖進(jìn)展操作，網(wǎng)中的頂點(diǎn)數(shù)，邊數(shù)，頂點(diǎn)的編號(hào)與 每條邊的權(quán)值都是通過(guò)鍵盤(pán)輸入的，他們的數(shù)據(jù)類(lèi)型均為整型，其中，權(quán)值的X圍為 032768即“"(2) .輸出數(shù)據(jù)的類(lèi)型當(dāng)用戶(hù)將無(wú)向圖創(chuàng)建成功以后，就可以通過(guò)鍵盤(pán)任意輸入一個(gè)起點(diǎn)值將其對(duì) 應(yīng)的最小生成樹(shù)的生成路徑與其權(quán)值顯示出來(lái)；(3) .測(cè)試數(shù)據(jù)本次設(shè)計(jì)中是通過(guò)用 Prim算法求最小生成樹(shù)，分別用以下三組數(shù)據(jù)進(jìn)展測(cè) 試：(一)假設(shè)在創(chuàng)建無(wú)向圖時(shí)，只輸入一個(gè)頂點(diǎn)，如圖1所示，驗(yàn)證運(yùn)行結(jié)果；(二) 假設(shè)創(chuàng)建的無(wú)向圖如圖2所示，驗(yàn)證運(yùn)行結(jié)果;在本次設(shè)計(jì)中，網(wǎng)

11、的定義為 G=(V,E),V表示非空頂點(diǎn)集,E表示邊集,其存儲(chǔ) 結(jié)構(gòu)這里采用鄰接矩陣的方式來(lái)存儲(chǔ)。1 數(shù)據(jù)類(lèi)型的定義 在本設(shè)計(jì)中所涉與 到的數(shù)據(jù)類(lèi)型定義如下：符號(hào)常量的定義 算法中涉與到兩個(gè)符號(hào)常量，定義如下：#defi ne MAX 20功能：用于表示網(wǎng)中最多頂點(diǎn)個(gè)數(shù)；#defi ne INFINIT 32768 功能：用于表示權(quán)的最大值，即. 結(jié)構(gòu)體的定義整個(gè)算法中涉與的結(jié)構(gòu)體定義如下：? 定義結(jié)構(gòu)體Arode功能：用于存放邊的權(quán)值typedef structint adj;/ 權(quán)值A(chǔ)rode;? 定義結(jié)構(gòu)體AdjMatrix功能：用于表示網(wǎng)的結(jié)構(gòu)與存儲(chǔ)方式。typedef structi

12、nt vexsMAX； /vexs 表示頂點(diǎn)向量intvexnum,arum； /分別表示圖的頂點(diǎn)數(shù)和弧數(shù)Arode arcsMAXMAX ； / 鄰接矩陣AdjMatrix? 定義結(jié)構(gòu)體Node功能：用于表示求最小生成樹(shù)時(shí)用到的輔助數(shù)組。typedef structint adjvex;/存放頂點(diǎn)編號(hào)int lowcost;/存放頂點(diǎn)權(quán)值Node;? 外部變量的定義算法中涉與到兩個(gè)外部變量，定義如下：Node closeMAX功能：存放每個(gè)頂點(diǎn)所連接的邊所對(duì)應(yīng)的權(quán)值；int flag=O功能：標(biāo)志變量，當(dāng)創(chuàng)建網(wǎng)時(shí)，輸入的頂點(diǎn)個(gè)數(shù)=1時(shí)，直接輸出“不 存在最小生成樹(shù)'程序不在往后執(zhí)行，

13、否如此繼續(xù)往下執(zhí)行。 函數(shù)模塊在本設(shè)計(jì)中一共包括六個(gè)模塊：一、子函數(shù) int Locate(AdjMatrix *G,int V)功能：是求出某個(gè)頂點(diǎn)在頂點(diǎn)向量表中的位置，在其函數(shù)體中通過(guò)for循環(huán)將某一頂點(diǎn)與頂點(diǎn)向量表中的所有頂點(diǎn)進(jìn)展比擬，當(dāng)出現(xiàn)兩者相等時(shí)，將該頂點(diǎn) 在vexsMAX數(shù)組中的下標(biāo)通過(guò)return語(yǔ)句返回，否如此返回-1 ；二、子函數(shù) AdjMatrix *creat(AdjMatrix *G)功能：是完成無(wú)向網(wǎng)的創(chuàng)建，在其函數(shù)體中，首先通過(guò)鍵盤(pán)輸入網(wǎng)中頂點(diǎn)數(shù)， 假如頂點(diǎn)個(gè)數(shù)<=1時(shí)，將標(biāo)志變量flag置為1并顯示“最小生成樹(shù)不存在，然 后返回主調(diào)函數(shù)；否如此，繼續(xù)通過(guò)鍵

14、盤(pán)輸入網(wǎng)中的邊數(shù)，通過(guò)二重for循環(huán)初始化鄰接矩陣，然后輸入各個(gè)頂點(diǎn)的編號(hào)與每條邊的權(quán)值，調(diào)用函數(shù)Locate()求出每條邊所對(duì)應(yīng)的兩個(gè)頂點(diǎn)在頂點(diǎn)向量表中的位置后，將對(duì)應(yīng)在鄰接矩陣中的相 應(yīng)位置賦予權(quán)值，從而在鄰接矩陣中存放了相關(guān)連的頂點(diǎn)之間邊的權(quán)值，完成無(wú) 向網(wǎng)的存儲(chǔ)；三、子函數(shù) int Minium(AdjMatrix *G,Node close)功能：是求出輔助數(shù)組 close中權(quán)值最小的邊，在其函數(shù)體中，首先將最 小權(quán)值min置為INFINIT，通過(guò)for循環(huán)將輔助數(shù)組中的各條邊的權(quán)值 與min進(jìn)展比擬，最終使得 min中存放的是當(dāng)前數(shù)組close中最小的權(quán)值，并 將其在輔助數(shù)組中的相

15、應(yīng)位置返回主調(diào)函數(shù)中；四、子函數(shù) void prim(AdjMatrix *G,int u)功能：是利用PRIM：普里姆算法求出無(wú)向網(wǎng)所對(duì)應(yīng)的最小生成樹(shù)，在其函 數(shù)體中，首先，定義AdjMatrix *p用于存放最小生成樹(shù)中的頂點(diǎn)按生成最小生 成樹(shù)時(shí)的順序存放，調(diào)用函數(shù)Locate()求出起點(diǎn)u在頂點(diǎn)向量表中的位置，將 u存放到p的頂點(diǎn)向量表中，初始化初始化U=u，利用for循環(huán)對(duì)V-U中的頂點(diǎn) i,初始化closei，再利用for循環(huán)找n-1條邊(n=G->vexnum)，其中，調(diào)用函數(shù)Minium()求出輔助數(shù)組close中權(quán)值最小的邊,并將其在輔助數(shù)組中的相應(yīng) 位置返回到主調(diào)函數(shù)中

16、并賦給 kO,此時(shí)closek0中存有當(dāng)前最小邊(uO, vO)的 信息，將邊所對(duì)應(yīng)的終點(diǎn)放入p的頂點(diǎn)向量表中，累加邊的權(quán)值；然后，輸出 <起點(diǎn) 終點(diǎn) 權(quán)值 >最后，在頂點(diǎn) vO并入U(xiǎn)之后，利用for循環(huán)更新 closedgei;當(dāng)所有的頂點(diǎn)v0都納入U(xiǎn)集合之后，輸出最小生成樹(shù)中的頂點(diǎn)序 列與最小生成樹(shù)的權(quán)值之和。五、子函數(shù) void display(AdjMatrix *G)功能：是創(chuàng)建的無(wú)向網(wǎng)所對(duì)應(yīng)的鄰接矩陣；六、主函數(shù) void main()功能：是完成對(duì)上述各子函數(shù)的調(diào)用，完本錢(qián)次設(shè)計(jì)的要求，在其函數(shù)體中，通過(guò)while循環(huán)可以實(shí)現(xiàn)重復(fù)創(chuàng)建網(wǎng)以與可以從網(wǎng)中的不同頂點(diǎn)出發(fā)求出

17、對(duì)應(yīng)的 最小生成樹(shù)。. 流程圖上述流程圖反映了整個(gè)算法中各個(gè)子函數(shù)之間的嵌套調(diào)用，從主函數(shù)開(kāi)始順 序往下執(zhí)行，首先調(diào)用creat()函數(shù)創(chuàng)建無(wú)向網(wǎng)并采用鄰接矩陣的方式來(lái)存儲(chǔ)；然后將該網(wǎng)對(duì)應(yīng)的鄰接矩陣通過(guò)調(diào)用display。函數(shù)輸出；最后調(diào)用prim ()函數(shù)求出該網(wǎng)所對(duì)應(yīng)的最小生成樹(shù)，并且在prim ()函數(shù)中通過(guò)嵌套調(diào)用 Minium ()函數(shù)求出輔助數(shù)組close中權(quán)值最小的邊，從而完成了本設(shè)計(jì)的要求。四測(cè)試結(jié)果該局部是對(duì)前面任務(wù)定義中的測(cè)試數(shù)據(jù)進(jìn)展驗(yàn)證和分析:4.1實(shí)驗(yàn)一只含一個(gè)頂點(diǎn)的無(wú)向圖。-怛供總母：丫甘.口止.“”斤旦盧屮r £鋁£飛11丄1丄1川亙 1EU-m

18、 “*是忙叵R5 flTpl 昨胡HLriffiwifmftfifif!憚導(dǎo)*百 魚(yú)逹無(wú) 問(wèn)用:手帝I人叫P .否ill|占任 螢密丫號(hào)押胃FlfWf if 1fll青皆If *!向 爲(wèi)了*軋 ' V P j 誹"ll| T"" » - Cl "十甲 HIMi»W bffWBf WW;WW i*MWH-W-irtfMWM'ii-WW 崗軸A.何中的助5亦-圖5.只含一個(gè)頂點(diǎn)的無(wú)向圖4.2 實(shí)驗(yàn)二假定創(chuàng)建的無(wú)向網(wǎng)的頂點(diǎn)個(gè)數(shù)1，并且網(wǎng)中有些邊的權(quán)值相等。分析：在上述創(chuàng)建的無(wú)向網(wǎng)中，有些頂點(diǎn)之間沒(méi)有邊相連接，所以在鄰接矩 陣

19、中用表示，由于是以頂點(diǎn)1作為起點(diǎn)生成最小生成樹(shù)，所以上述運(yùn)行結(jié)果對(duì) 應(yīng)的生成樹(shù)如圖7所示。實(shí)驗(yàn)三假定創(chuàng)建的無(wú)向網(wǎng)的頂點(diǎn)個(gè)數(shù)>1,并且網(wǎng)中有些邊的權(quán)值不相等。運(yùn)行結(jié)果 如下:尉卜牛威護(hù)I中芋頂點(diǎn)序列為» I 1234 E £ J刑用普甲妞就R出占1岀斜尉I江成樹(shù)的路槿如下<起點(diǎn)-，終點(diǎn)權(quán)值<1 ->216 ><1 ->35><1 ->46><1->611><1->518 >最才灶Ji湖比枉植2和為：躬詩(shī)繼紐評(píng)尼點(diǎn)吞口喩®E出匚參考文獻(xiàn)(1) .吳玉蓉，數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言

20、版，中國(guó)水利水電，2008年;(2) .徐孝凱，數(shù)據(jù)結(jié)構(gòu)實(shí)用教程，清華大學(xué)，2005年7月；(3) .譚浩強(qiáng)，C語(yǔ)言程序設(shè)計(jì)教程，高等教育，2004年5月。附錄關(guān)鍵局部程序清單#include"stdio.h"#include"string.h"#include"malloc.h"#include"iostream.h"#include"iomanip.h"#define MAX 20 / 最多頂點(diǎn)個(gè)數(shù)#define INFINIT 32768表示極大值，即®typedef struc

21、tint adj; /adj是權(quán)值類(lèi)型Arode;typedef structint vexsMAX,vexnum,arum; /*vexs表示頂點(diǎn)向量；vexnum,arum分別表示圖的頂點(diǎn)數(shù)和弧數(shù)*/Arode arcsMAXMAX; /*鄰接矩陣 */AdjMatrix;typedef structint adjvex;/ 存放頂點(diǎn)編號(hào) int lowcost;/存放頂點(diǎn)權(quán)值Node;Node closeMAX;/求最小生成樹(shù)時(shí)的輔助數(shù)組int flag=O; /功能：標(biāo)志變量，當(dāng)創(chuàng)建網(wǎng)時(shí)，輸入的頂點(diǎn)個(gè)數(shù)<=1時(shí)，直接輸岀“不存在最小生成樹(shù)"求頂點(diǎn)位置函數(shù)程序不在往后執(zhí)行

22、，否如此繼續(xù)往下執(zhí)行int Locate(AdjMatrix *G,int V) / intj=-1,k;for(k=O;k<G->vexnum;k+) if(G->vexsk=V)j=k;break;return j;AdjMatrix *creat(AdjMatrix *G) /創(chuàng)建無(wú)向網(wǎng)int i,j,k,v1,v2,weight,m=1;printf（”請(qǐng)輸入網(wǎng)中的頂點(diǎn)數(shù)："）;scanf("%d",&G->vexnum);if(G->vexnum<=1)printf("n*flag=1; return

23、 G; elseprintf(" 請(qǐng)輸入網(wǎng)中的邊數(shù): scanf("%d",&G->arum);for(i=0;i<G->vexnum;i+) /for(j=0;j<G_>vexnum;j+) if(i=j)G->arcsij.adj=0;elseG->arcsij.adj=INFINIT;最小生成樹(shù)不存在!*n"）;"）;初始化鄰接矩陣printf（"請(qǐng)輸入網(wǎng)中的頂點(diǎn)編號(hào)："）;/輸入網(wǎng)中的頂點(diǎn)編號(hào)for(i=0;i<G->vexnum;i+) scanf（&q

24、uot;%d",&G-vexsi）;printf（"輸入每條弧所對(duì)應(yīng)的兩個(gè)頂點(diǎn)與權(quán)值格式：起點(diǎn)終點(diǎn)權(quán)值!n"）;for(k=0;k<G->arum;k+)printf(" 請(qǐng)輸入第d條邊:",m);輸入一條弧的兩個(gè)頂點(diǎn)與權(quán)值m+;scanf("%d %d %d"，&v1,&v2,&weight); / i=Locate(G,v1);j=Locate(G,v2);G->arcsij.adj=weight;G->arcsji.adj=weight;return(G);中權(quán)值

25、最小的邊int Minium(AdjMatrix *G,Node close)/closeint i,min,k;min=INFINIT;置最小權(quán)值為 INFINITfor(i=0;i<G->vexnum;i+)if(closei.lowcost<min&&closei.lowcost!=0)min=closei.lowcost;k=i;return k;/返回權(quán)值最小的邊在輔助數(shù)組中的位置G的最小生成void prim(AdjMatrix *G,int u)/普里姆算法/從頂點(diǎn)u出發(fā)，按普里姆算法構(gòu)造連通網(wǎng)樹(shù)，并輸岀生成樹(shù)的每條邊int i,j,k,k0,u

26、0,v0,s=0,n=0;AdjMatrix *p;p=(AdjMatrix *)malloc(sizeof(AdjMatrix); k=Locate(G,u);/k 為頂點(diǎn)u的位置 p->vexsn+=u;closek.lowcost=0;/初始化 U=ufor(i=0;i<G->vexnum;i+)if(i!=k) / 對(duì)V-U中的頂點(diǎn)i,初始化closeiclosei.adjvex=u;closei.lowcost=G->arcski.adj;for(j=1;j<=G->vexnum-1;j+)/n-1條邊(n=G->vexnum)k0=Mini

27、um(G,close);/closek0中存有當(dāng)前最小邊(u0, v0)的信息u0=closek0.lowcost;/u0 Uv0=G->vexsk0; /v0 V-Up->vexsn+=v0;將終點(diǎn)放入數(shù)組中s+=closek0.lowcost;求最小生成樹(shù)的權(quán)值之和printf(" v%d->%dt%d>n",u,v0,closek0.lowcost); /輸出最小生成樹(shù)的路徑closek0.lowcost=0;將頂點(diǎn) v0 納入 U 集合for(i=0;i<G->vexnum;i+)/ 在頂點(diǎn) v0 并入 U之后,更新 closed

28、geiif(G->arcskOi.adj<closei.lowcost)closei.lowcost=G->arcskOi.adj;closei.adjvex=vO;printf("n最小生成樹(shù)中的頂點(diǎn)序列為：");for(i=0;i<G->vexnum;i+)printf(" %d ",p->vexsi);printf("n");printf("n最小生成樹(shù)的權(quán)值之和為：dn",s);輸岀鄰接矩陣算法 void display(AdjMatrix *G) /int i,j;fo

29、r(i=0;i<G->vexnum;i+) printf("t%d",G->vexsi); printf("n");printf("| ");for(i=0;i<G->vexnum;i+)prin tf("");printf("n");for(i=0;i<G->vexnum;i+)printf(" %d | ",G->vexsi);for(j=0;j<G->vexnum;j+) if(G->arcsij.adj

30、=INFINIT) printf("t g");elseprintf("t%d",G->arcsij.adj); printf("n");for(i=0;i<G->vexnum;i+) printf("");printf("n");void main() / 主函數(shù)char ch;int st;AdjMatrix *G,*p;p=(AdjMatrix *)malloc(sizeof(AdjMatrix);printf(”*n");printf("普里姆最小生成樹(shù)算法！n"）;printf("n*n");printf("設(shè)計(jì)者:printf("班 級(jí):printf("指導(dǎo)教師:printf("設(shè)計(jì)時(shí)間:李浩淵n");34010105 班 n");X純龍教師n");2015 年 1 月 15 日 n");printf("n*");printf("n*鍵!*n");假如創(chuàng)建無(wú)向網(wǎng)請(qǐng)輸入