普里姆算法求最小生成樹

1、沈陽(yáng)航空航天大學(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)方向）班 級(jí)：學(xué) 號(hào)：姓 名：指導(dǎo)教師： 學(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ā)表或撰寫過的研究結(jié)果，也不包含其它教育機(jī)構(gòu)使用過的材料。與我一同工作的同學(xué)對(duì)本研究所做的任何貢獻(xiàn)均己在報(bào)告中做了明確的說明并表示了謝意。報(bào)告資料及實(shí)驗(yàn)數(shù)據(jù)若有不實(shí)之處，本人愿意接受本教學(xué)環(huán)節(jié)“不及格”和“重

2、修或重做”的評(píng)分結(jié)論并承擔(dān)相關(guān)一切后果。 本人簽名: 日期： 2015 年 1 月 15 日沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)任務(wù)書課程設(shè)計(jì)名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)（物聯(lián)網(wǎng)方向）學(xué)生姓名班級(jí)學(xué)號(hào)題目名稱Prim算法生成最小生成樹起止日期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)的最小生成樹。其中，n個(gè)城市表示n個(gè)節(jié)點(diǎn)，兩個(gè)城市間如果有路則用邊連接，生成一個(gè)n個(gè)節(jié)點(diǎn)的邊權(quán)樹，要求鍵盤輸入。參考資料： 算法與數(shù)據(jù)結(jié)構(gòu)，嚴(yán)蔚敏、 吳偉民，清華大學(xué)出版社

3、，2006C語(yǔ)言程序設(shè)計(jì)，譚浩強(qiáng)，清華大學(xué)出版社，2010教研室審核意見： 教研室主任簽字：指導(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 最小生成樹的定義- 5 -2.2 Prim算法的基本思想- 5 -三 概要分析和設(shè)計(jì)- 7 -3.1 概要分析- 7 -3.2 概要設(shè)計(jì)- 8 -四 測(cè)試結(jié)果- 13 -4.1實(shí)驗(yàn)一- 13 -4.2實(shí)驗(yàn)二- 13 -4.3 實(shí)驗(yàn)三- 14 -參考文獻(xiàn)- 15 -附 錄（關(guān)鍵部分程序清單）-

4、16 - 一 課程設(shè)計(jì)目的和要求1.1 課程設(shè)計(jì)目的(一) 根據(jù)算法設(shè)計(jì)需要，掌握連通網(wǎng)的數(shù)據(jù)表示方法；(二) 掌握最小生成樹的Prim算法；(三) 學(xué)習(xí)獨(dú)立撰寫報(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)的最小生成樹。其中，n個(gè)城市表示n個(gè)節(jié)點(diǎn)，兩個(gè)城市間如果有路則用邊連接，生成一個(gè)n個(gè)節(jié)點(diǎn)的邊權(quán)樹，要求鍵盤輸入。二 實(shí)驗(yàn)原理分析2.1 最小生成樹的定義一個(gè)有 n 個(gè)結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊。最小生成樹可以用kru

5、skal（克魯斯卡爾）算法或Prim（普里姆）算法求出。(1). 最小生成樹的概述在一給定的無向圖G = (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)重生成樹的簡(jiǎn)稱。(2). 最小生成樹的分析構(gòu)造最小生成樹可以用多種算法。其中多數(shù)算法利用了最小生成樹的下面一種簡(jiǎn)稱為MST的性質(zhì)：假設(shè)N=(V,E)是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值（代價(jià)）的邊，其中uU，vV-U，則必存在

6、一棵包含邊(u.v)的最小生成樹。2.2 Prim算法的基本思想假設(shè)G =（V，E）是一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，U和TE的初值均為空集。算法開始時(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），其中ViU,Vj(V-U),并把該邊（i,j）和頂點(diǎn)j分別并入T的邊集TE和頂點(diǎn)集U，如此進(jìn)行下去，每次往生成樹里并入一個(gè)頂點(diǎn)和一條邊，直到n-1次后就把所有n個(gè)頂點(diǎn)都并入到生成樹T的頂點(diǎn)

7、集中，此時(shí)U=V，TE中含有n-1條邊，T就是最后得到的最小生成樹?？梢钥闯?，在普利姆算法中，是采用逐步增加U中的頂點(diǎn)，常稱為“加點(diǎn)法”。為了實(shí)現(xiàn)這個(gè)算法在本設(shè)計(jì)中需要設(shè)置一個(gè)輔助數(shù)組closedge ，以記錄從U到V-U具有最小代價(jià)的邊。當(dāng)輔助數(shù)組中存在兩個(gè)或兩個(gè)以上的最小代價(jià)的邊時(shí)，此時(shí)最小生成樹的形態(tài)就不唯一，此時(shí)可以在程序中采用遞歸的算法思想求出每個(gè)最小生成樹。(1). 在prim算法中要解決兩個(gè)問題1) 在無向網(wǎng)中，當(dāng)從一個(gè)頂點(diǎn)到其他頂點(diǎn)時(shí)，若其邊上的權(quán)值相等，則可能從某一起點(diǎn)出發(fā)時(shí)，會(huì)得到不同的生成樹，但最小生成樹的權(quán)值必定相等，此時(shí)我們應(yīng)該如何把所有的最小生成樹求解出來；2) 每

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

9、（共n-k個(gè)頂點(diǎn)）的各一條最短邊，進(jìn)行第k次時(shí)，首先從這n-k條最短邊中，找出一條最最短的邊，它就是從T中到T外的所有邊中的最短邊，假設(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的各一條最短邊都保留下來了，為進(jìn)行第k+1次運(yùn)算做好了準(zhǔn)備，此步需進(jìn)行n-k-1次比較。所以，利用此方法求第k次的

10、最短邊共需比較2(n-k)-1次，即時(shí)間復(fù)雜度為O(n-k)。三 概要分析和設(shè)計(jì)3.1 概要分析通過對(duì)上述算法的分析，將從以下三方面來進(jìn)行分析：(1). 輸入數(shù)據(jù)的類型在本次設(shè)計(jì)中，是對(duì)無向圖進(jìn)行操作，網(wǎng)中的頂點(diǎn)數(shù)，邊數(shù)，頂點(diǎn)的編號(hào)及每條邊的權(quán)值都是通過鍵盤輸入的，他們的數(shù)據(jù)類型均為整型，其中，權(quán)值的范圍為032768（即“”）；(2). 輸出數(shù)據(jù)的類型當(dāng)用戶將無向圖創(chuàng)建成功以后，就可以通過鍵盤任意輸入一個(gè)起點(diǎn)值將其對(duì)應(yīng)的最小生成樹的生成路徑及其權(quán)值顯示出來；(3). 測(cè)試數(shù)據(jù)本次設(shè)計(jì)中是通過用Prim算法求最小生成樹，分別用以下三組數(shù)據(jù)進(jìn)行測(cè)試：(一) 假設(shè)在創(chuàng)建無向圖時(shí)，只輸入一個(gè)頂點(diǎn)，如

11、圖1所示，驗(yàn)證運(yùn)行結(jié)果； A圖1.單一節(jié)點(diǎn)的無向圖(二) 假設(shè)創(chuàng)建的無向圖如圖2所示，驗(yàn)證運(yùn)行結(jié)果；圖2.網(wǎng)中存在權(quán)值相等的邊(三) 假設(shè)創(chuàng)建的無向圖如圖3所示，驗(yàn)證結(jié)果；圖3，網(wǎng)中的權(quán)值各不相等3.2 概要設(shè)計(jì)在本次設(shè)計(jì)中，網(wǎng)的定義為G=(V,E),V表示非空頂點(diǎn)集,E表示邊集,其存儲(chǔ)結(jié)構(gòu)這里采用鄰接矩陣的方式來存儲(chǔ)。 1 數(shù)據(jù)類型的定義 在本設(shè)計(jì)中所涉及到的數(shù)據(jù)類型定義如下：(1). 符號(hào)常量的定義 算法中涉及到兩個(gè)符號(hào)常量，定義如下： #define MAX 20 功能：用于表示網(wǎng)中最多頂點(diǎn)個(gè)數(shù)； #define INFINIT 32768 功能：用于表示權(quán)的最大值，即。(2). 結(jié)構(gòu)體

12、的定義 整個(gè)算法中涉及的結(jié)構(gòu)體定義如下：ü 定義結(jié)構(gòu)體ArcNode 功能：用于存放邊的權(quán)值 typedef struct int adj;/權(quán)值 ArcNode;ü 定義結(jié)構(gòu)體AdjMatrix  功能：用于表示網(wǎng)的結(jié)構(gòu)及存儲(chǔ)方式。  typedef struct  int vexsMAX；/vexs表示頂點(diǎn)向量  int vexnum,arcnum；/分別表示圖的頂點(diǎn)數(shù)和弧數(shù) ArcNode arcsMAXMAX；/鄰接矩陣 Adj

13、Matrix ü 定義結(jié)構(gòu)體Node 功能：用于表示求最小生成樹時(shí)用到的輔助數(shù)組。 typedef struct int 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=0 功能：標(biāo)志變量，當(dāng)創(chuàng)建網(wǎng)時(shí)，輸入的頂點(diǎn)個(gè)數(shù)<=1時(shí)，直接輸出 “不存在最小生成樹”程序不在往后執(zhí)行，否則繼續(xù)往下執(zhí)行。(3). 函數(shù)模塊在本設(shè)計(jì)中一共包括六個(gè)模塊：一、 子函數(shù)int Locate(AdjMatrix *

14、G,int V) 功能：是求出某個(gè)頂點(diǎn)在頂點(diǎn)向量表中的位置，在其函數(shù)體中通過for循環(huán)將某一頂點(diǎn)與頂點(diǎn)向量表中的所有頂點(diǎn)進(jìn)行比較，當(dāng)出現(xiàn)兩者相等時(shí)，將該頂點(diǎn)在vexsMAX數(shù)組中的下標(biāo)通過return語(yǔ)句返回，否則返回-1；二、 子函數(shù)AdjMatrix *creat(AdjMatrix *G) 功能：是完成無向網(wǎng)的創(chuàng)建，在其函數(shù)體中，首先通過鍵盤輸入網(wǎng)中頂點(diǎn)數(shù)，若頂點(diǎn)個(gè)數(shù)<=1時(shí)，將標(biāo)志變量flag置為1并顯示“最小生成樹不存在”，然后返回主調(diào)函數(shù)；否則，繼續(xù)通過鍵盤輸入網(wǎng)中的邊數(shù)，通過二重for循環(huán)初始化鄰接矩陣，然后輸入各個(gè)頂點(diǎn)的編號(hào)及每條邊的權(quán)值，調(diào)用函數(shù)Locate()求出每條

15、邊所對(duì)應(yīng)的兩個(gè)頂點(diǎn)在頂點(diǎn)向量表中的位置后，將對(duì)應(yīng)在鄰接矩陣中的相應(yīng)位置賦予權(quán)值，從而在鄰接矩陣中存放了相關(guān)連的頂點(diǎn)之間邊的權(quán)值，完成無向網(wǎng)的存儲(chǔ)；三、 子函數(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ù)組中的相應(yīng)位置返回主調(diào)函數(shù)中；四、 子函數(shù)void prim(AdjMatrix *G,int u) 功能：是利用PRIM（普里姆）算

16、法求出無向網(wǎng)所對(duì)應(yīng)的最小生成樹，在其函數(shù)體中，首先，定義AdjMatrix *p用于存放最小生成樹中的頂點(diǎn)（按生成最小生成樹時(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ù)中并賦給k0，此時(shí)closek0中存有當(dāng)前最小邊(u0, v0)的信息，將邊所對(duì)應(yīng)的終點(diǎn)放入p的頂點(diǎn)向量表中，累加邊的權(quán)值；然后

17、，輸出<起點(diǎn) 終點(diǎn) 權(quán)值>；最后，在頂點(diǎn)v0并入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)所對(duì)應(yīng)的鄰接矩陣；六、 主函數(shù)void main() 功能：是完成對(duì)上述各子函數(shù)的調(diào)用，完成本次設(shè)計(jì)的要求，在其函數(shù)體中，通過while循環(huán)可以實(shí)現(xiàn)重復(fù)創(chuàng)建網(wǎng)以及可以從網(wǎng)中的不同頂點(diǎn)出發(fā)求出對(duì)應(yīng)的最小生成樹。(4). 流程圖開始輸入ch, 用于判斷是否創(chuàng)建無向網(wǎng)Ch=“Y”結(jié)束輸入起點(diǎn)st1調(diào)用create()函數(shù)2調(diào)用d

18、isplay()函數(shù)Flog=0st=03調(diào)用prim()函數(shù)4調(diào)用minium()函數(shù)圖 4.流程圖上述流程圖反映了整個(gè)算法中各個(gè)子函數(shù)之間的嵌套調(diào)用，從主函數(shù)開始順序往下執(zhí)行，首先調(diào)用creat()函數(shù)創(chuàng)建無向網(wǎng)并采用鄰接矩陣的方式來存儲(chǔ)；然后將該網(wǎng)對(duì)應(yīng)的鄰接矩陣通過調(diào)用display()函數(shù)輸出；最后調(diào)用prim ()函數(shù)求出該網(wǎng)所對(duì)應(yīng)的最小生成樹，并且在prim ()函數(shù)中通過嵌套調(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)的無向圖。圖5. 只含一個(gè)頂點(diǎn)的

19、無向圖4.2 實(shí)驗(yàn)二假定創(chuàng)建的無向網(wǎng)的頂點(diǎn)個(gè)數(shù)>1，并且網(wǎng)中有些邊的權(quán)值相等。圖7.運(yùn)行結(jié)果分析：在上述創(chuàng)建的無向網(wǎng)中，有些頂點(diǎn)之間沒有邊相連接，所以在鄰接矩陣中用表示，由于是以頂點(diǎn)1作為起點(diǎn)生成最小生成樹，所以上述運(yùn)行結(jié)果對(duì)應(yīng)的生成樹如圖7所示。4.3 實(shí)驗(yàn)三假定創(chuàng)建的無向網(wǎng)的頂點(diǎn)個(gè)數(shù)>1，并且網(wǎng)中有些邊的權(quán)值不相等。運(yùn)行結(jié)果如下： 參考文獻(xiàn)(1). 吳玉蓉，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），中國(guó)水利水電出版社，2008年；(2). 徐孝凱，數(shù)據(jù)結(jié)構(gòu)實(shí)用教程，清華大學(xué)出版社，2005年7月；(3). 譚浩強(qiáng)，C語(yǔ)言程序設(shè)計(jì)教程，高等教育出版社，2004年5月。附 錄（關(guān)鍵部分程序清單）#in

20、clude"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 struct int adj; /adj是權(quán)值類型 ArcNode; typedef struct int vexsMAX,vexnum,arcnum; /*vexs表示頂點(diǎn)向量;vexnum,

21、arcnum分別表示圖的頂點(diǎn)數(shù)和弧數(shù)*/ ArcNode arcsMAXMAX; /*鄰接矩陣*/ AdjMatrix; typedef struct int adjvex;/存放頂點(diǎn)編號(hào) int lowcost;/存放頂點(diǎn)權(quán)值 Node; Node closeMAX;/求最小生成樹時(shí)的輔助數(shù)組 int flag=0; /功能：標(biāo)志變量，當(dāng)創(chuàng)建網(wǎng)時(shí)，輸入的頂點(diǎn)個(gè)數(shù)<=1時(shí)，直接輸出 “不存在最小生成樹”程序不在往后執(zhí)行，否則繼續(xù)往下執(zhí)行int Locate(AdjMatrix *G,int V) /求頂點(diǎn)位置函數(shù) int j=-1,k; for(k=0;k<G->vexnum

22、;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("請(qǐng)輸入網(wǎng)中的頂點(diǎn)數(shù)："); scanf("%d",&G->vexnum); if(G->vexnum<=1) printf("n*最小生成樹不存在!*n"); flag=1;return G; else printf("請(qǐng)輸入網(wǎng)中的邊數(shù)："); scanf(

23、"%d",&G->arcnum); for(i=0;i<G->vexnum;i+) /初始化鄰接矩陣 for(j=0;j<G->vexnum;j+) if(i=j) G->arcsij.adj=0; else G->arcsij.adj=INFINIT; printf("請(qǐng)輸入網(wǎng)中的頂點(diǎn)編號(hào)："); /輸入網(wǎng)中的頂點(diǎn)編號(hào) for(i=0;i<G->vexnum;i+)scanf("%d",&G->vexsi); printf("輸入每條弧所對(duì)應(yīng)的兩個(gè)

24、頂點(diǎn)及權(quán)值<格式：起點(diǎn) 終點(diǎn) 權(quán)值>!n"); for(k=0;k<G->arcnum;k+) printf("請(qǐng)輸入第%d條邊:",m);m+;scanf("%d %d %d",&v1,&v2,&weight); /輸入一條弧的兩個(gè)頂點(diǎn)及權(quán)值 i=Locate(G,v1); j=Locate(G,v2); G->arcsij.adj=weight; G->arcsji.adj=weight; return(G); int Minium(AdjMatrix *G,Node close)

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

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

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

28、sk0i.adj<closei.lowcost) closei.lowcost=G->arcsk0i.adj; closei.adjvex=v0; 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; for(i=0;i&l

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

30、f("t"); 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ì) 者：李浩淵n"); printf(" 班 級(jí)：34010105班n"); printf(" 指導(dǎo)老師：范純龍老師n"); printf(" 設(shè)計(jì)時(shí)間：2015年1月15日n"); printf("n*"); printf("n*若創(chuàng)建無向網(wǎng)請(qǐng)輸入'Y',否則按任意鍵!*n");scanf("%c