普里姆算法求最小生成樹

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

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

3、2006C程序設(shè)計(jì)，譚浩強(qiáng)，清華大學(xué)，2010教研室審核意見：教研室主任簽字：指導(dǎo)教師簽名年月日學(xué)生簽名2015 年 1 月15 日目錄學(xué)術(shù)誠信聲明-1 -一課程設(shè)計(jì)目的和要求-4 -1.1課程設(shè)計(jì)目的-4-1.2課程設(shè)計(jì)的要求-4- 二實(shí)驗(yàn)原理分析-5 -2.1最小生成樹的定義-5 -2.2 Prim算法的根本思想-5 -三概要分析和設(shè)計(jì)-8 -3.1概要分析-8-3.2概要設(shè)計(jì)-9 -四測試結(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、方法;（二）掌握最小生成樹的Prim算法；（三）學(xué)習(xí)獨(dú)立撰寫報(bào)告文檔。1.2 課程設(shè)計(jì)的要求在n個城市之間建立網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法，利用Prim算法輸出n個城市之間網(wǎng)絡(luò)圖，輸出n個節(jié)點(diǎn)的最小生成樹。其中，n個城 市表示n個節(jié)點(diǎn)，兩個城市間如果有路如此用邊連接，生成一個 n個節(jié)點(diǎn)的邊權(quán) 樹，要求鍵盤輸入。二實(shí)驗(yàn)原理分析2.1最小生成樹的定義一個有n個結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖， 且包含原圖中的 所有n個結(jié)點(diǎn)，并且有保持圖連通的最少的邊。最小生成樹可以用 kruskal 克 魯斯卡爾算法或Prim普里姆算法求出。(1) .最小生成樹的概述在一給定的無向圖G =

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

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

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

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

9、外的所有邊中的最短邊，假 設(shè)為i,j丨，此步需進(jìn)展n-k次比擬；然后把邊i,j和頂點(diǎn)j分別并入T中的 邊集TE和頂點(diǎn)集U中，此時T外只有n-(k+1)個頂點(diǎn)，對于其中的每個頂點(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的各一條最短邊都保存下 來了，為進(jìn)展第k+1次運(yùn)算做好了準(zhǔn)備，此步需進(jìn)展 n-k-1次比擬。所以，利用 此方法求第k次的最短邊共需比擬2(n-k)-1次，即時間復(fù)雜度為0(n-k)。三概要分析和設(shè)計(jì)3.1概要分析通過對

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

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

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

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

14、盤輸入網(wǎng)中的邊數(shù)，通過二重for循環(huán)初始化鄰接矩陣，然后輸入各個頂點(diǎn)的編號與每條邊的權(quán)值，調(diào)用函數(shù)Locate()求出每條邊所對應(yīng)的兩個頂點(diǎn)在頂點(diǎn)向量表中的位置后，將對應(yīng)在鄰接矩陣中的相 應(yīng)位置賦予權(quán)值，從而在鄰接矩陣中存放了相關(guān)連的頂點(diǎn)之間邊的權(quán)值，完成無 向網(wǎng)的存儲；三、子函數(shù) int Minium(AdjMatrix *G,Node close)功能：是求出輔助數(shù)組 close中權(quán)值最小的邊，在其函數(shù)體中，首先將最 小權(quán)值min置為INFINIT，通過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ǎng)所對應(yīng)的最小生成樹，在其函 數(shù)體中，首先，定義AdjMatrix *p用于存放最小生成樹中的頂點(diǎn)按生成最小生 成樹時的順序存放，調(diào)用函數(shù)Locate()求出起點(diǎn)u在頂點(diǎn)向量表中的位置，將 u存放到p的頂點(diǎn)向量表中，初始化初始化U=u，利用for循環(huán)對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,此時closek0中存有當(dāng)前最小邊(uO, vO)的 信息，將邊所對應(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)集合之后，輸出最小生成樹中的頂點(diǎn)序 列與最小生成樹的權(quán)值之和。五、子函數(shù) void display(AdjMatrix *G)功能：是創(chuàng)建的無向網(wǎng)所對應(yīng)的鄰接矩陣；六、主函數(shù) void main()功能：是完成對上述各子函數(shù)的調(diào)用，完本錢次設(shè)計(jì)的要求，在其函數(shù)體中，通過while循環(huán)可以實(shí)現(xiàn)重復(fù)創(chuàng)建網(wǎng)以與可以從網(wǎng)中的不同頂點(diǎn)出發(fā)求出

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

18、 “*是忙叵R5 flTpl 昨胡HLriffiwifmftfifif!憚導(dǎo)*百 魚逹無 問用:手帝I人叫P .否ill|占任 螢密丫號押胃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.只含一個頂點(diǎn)的無向圖4.2 實(shí)驗(yàn)二假定創(chuàng)建的無向網(wǎng)的頂點(diǎn)個數(shù)1，并且網(wǎng)中有些邊的權(quán)值相等。分析：在上述創(chuàng)建的無向網(wǎng)中，有些頂點(diǎn)之間沒有邊相連接，所以在鄰接矩 陣

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

20、版，中國水利水電，2008年;(2) .徐孝凱，數(shù)據(jù)結(jié)構(gòu)實(shí)用教程，清華大學(xué)，2005年7月；(3) .譚浩強(qiáng)，C語言程序設(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)個數(shù)#define INFINIT 32768表示極大值，即®typedef struc

21、tint adj; /adj是權(quán)值類型Arode;typedef structint vexsMAX,vexnum,arum; /*vexs表示頂點(diǎn)向量；vexnum,arum分別表示圖的頂點(diǎn)數(shù)和弧數(shù)*/Arode arcsMAXMAX; /*鄰接矩陣 */AdjMatrix;typedef structint adjvex;/ 存放頂點(diǎn)編號 int lowcost;/存放頂點(diǎn)權(quán)值Node;Node closeMAX;/求最小生成樹時的輔助數(shù)組int flag=O; /功能：標(biāo)志變量，當(dāng)創(chuàng)建網(wǎng)時，輸入的頂點(diǎn)個數(shù)<=1時，直接輸岀“不存在最小生成樹"求頂點(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ǎng)int i,j,k,v1,v2,weight,m=1;printf（”請輸入網(wǎng)中的頂點(diǎn)數(shù)："）;scanf("%d",&G->vexnum);if(G->vexnum<=1)printf("n*flag=1; return

23、 G; elseprintf(" 請輸入網(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;最小生成樹不存在!*n"）;"）;初始化鄰接矩陣printf（"請輸入網(wǎng)中的頂點(diǎn)編號："）;/輸入網(wǎng)中的頂點(diǎn)編號for(i=0;i<G->vexnum;i+) scanf（&q

24、uot;%d",&G-vexsi）;printf（"輸入每條弧所對應(yīng)的兩個頂點(diǎn)與權(quán)值格式：起點(diǎn)終點(diǎn)權(quán)值!n"）;for(k=0;k<G->arum;k+)printf(" 請輸入第d條邊:",m);輸入一條弧的兩個頂點(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)樹，并輸岀生成樹的每條邊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) / 對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;求最小生成樹的權(quán)值之和printf(" v%d->%dt%d>n",u,v0,closek0.lowcost); /輸出最小生成樹的路徑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最小生成樹中的頂點(diǎn)序列為：");for(i=0;i<G->vexnum;i+)printf(" %d ",p->vexsi);printf("n");printf("n最小生成樹的權(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("普里姆最小生成樹算法！n"）;printf("n*n");printf("設(shè)計(jì)者:printf("班 級:printf("指導(dǎo)教師:printf("設(shè)計(jì)時間:李浩淵n");34010105 班 n");X純龍教師n");2015 年 1 月 15 日 n");printf("n*");printf("n*鍵!*n");假如創(chuàng)建無向網(wǎng)請輸入