1、沈陽(yáng)航空航天大學(xué) 課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告 課程設(shè)計(jì)名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課程設(shè)計(jì)題目：PrimPrim 算法求最小生成樹(shù)算法求最小生成樹(shù) 院（系）：計(jì)算機(jī)學(xué)院 專(zhuān) 業(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ā)表 或撰寫(xiě)過(guò)的研究結(jié)果，也不包含其它教育機(jī)構(gòu)使用過(guò)的材料。與我一 同工作的同學(xué)對(duì)本研究所做的任何貢獻(xiàn)均己在報(bào)告中做了明確的

2、說(shuō)明 并表示了謝意。報(bào)告資料及實(shí)驗(yàn)數(shù)據(jù)若有不實(shí)之處，本人愿意接受本 教學(xué)環(huán)節(jié)“不及格”和“重修或重做”的評(píng)分結(jié)論并承擔(dān)相關(guān)一切后 果。 本人簽名: 日期： 2015 年 1 月 15 日 沈陽(yáng)航空航天大學(xué)沈陽(yáng)航空航天大學(xué) 課課程程設(shè)設(shè)計(jì)計(jì)任任務(wù)務(wù)書(shū)書(shū) 課程設(shè)計(jì)名稱(chēng) 數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)課課程程設(shè)設(shè)計(jì)計(jì)專(zhuān)業(yè) 計(jì)算機(jī)科學(xué)與技術(shù)計(jì)算機(jī)科學(xué)與技術(shù) （物聯(lián)網(wǎng)方向）（物聯(lián)網(wǎng)方向） 學(xué)生姓名班級(jí)學(xué)號(hào) 題目名稱(chēng)Prim 算法生成最小生成樹(shù)算法生成最小生成樹(shù) 起止日期2015年1月5日起至2015年1月16日止 課設(shè)內(nèi)容和要求： 在 n 個(gè)城市之間建立網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法，利用 Prim 算法

3、輸出 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é)出版社，2006 C 語(yǔ)言程序設(shè)計(jì)，譚浩強(qiáng)，清華大學(xué)出版社，2010 教教研研室室審審核核意意見(jiàn)見(jiàn)： 教教研研室室主主任任簽簽字字： 指導(dǎo)教師（簽名）指導(dǎo)教師（簽名） 年月日 學(xué)學(xué) 生（簽名）生（簽名）2015年1 月 15 日 目目 錄錄 學(xué)術(shù)誠(chéng)信聲明學(xué)術(shù)誠(chéng)信聲明 .- 1 - 一一 課程設(shè)計(jì)目的和要求課程設(shè)計(jì)目的和要求 .- 4 - 1.1 課程設(shè)計(jì)目的.- 4 -

4、1.2 課程設(shè)計(jì)的要求.- 4 - 二二 實(shí)驗(yàn)原理分析實(shí)驗(yàn)原理分析 .- 5 - 2.1 最小生成樹(shù)的定義.- 5 - 2.2 PRIM算法的基本思想.- 5 - 三三 概要分析和設(shè)計(jì)概要分析和設(shè)計(jì) .- 7 - 3.1 概要分析.- 7 - 3.2 概要設(shè)計(jì).- 8 - 四四 測(cè)試結(jié)果測(cè)試結(jié)果 .- 13 - 4.1實(shí)驗(yàn)一.- 13 - 4.2實(shí)驗(yàn)二.- 13 - 4.3 實(shí)驗(yàn)三.- 14 - 參考文獻(xiàn)參考文獻(xiàn) .- 15 - 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單） .- 16 - 一 課程設(shè)計(jì)目的和要求 1.1 課程設(shè)計(jì)目的課程設(shè)計(jì)目的 (一)根據(jù)算法設(shè)計(jì)需要，掌握連通網(wǎng)的數(shù)據(jù)

5、表示方法； (二)掌握最小生成樹(shù)的 Prim 算法； (三)學(xué)習(xí)獨(dú)立撰寫(xiě)報(bào)告文檔。 1.2 課程設(shè)計(jì)的要求課程設(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ù)的定義最小生成樹(shù)的定義 一個(gè)有 n 個(gè)結(jié)點(diǎn)的連通圖的生成樹(shù)是原圖的極小連通子圖，且包含原圖中 的所有 n 個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊。最小生成樹(shù)可以用 kruskal（克魯斯卡

6、爾）算法或 Prim（普里姆）算法求出。 (1). 最小生成樹(shù)的概述 在一給定的無(wú)向圖 G = (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à)）的邊，其 中 uU，

7、vV-U，則必存在一棵包含邊(u.v)的最小生成樹(shù)。 2.2 Prim 算法的基本思想算法的基本思想 假設(shè) G =（V，E）是一個(gè)具有 n 個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是 G 的最小生成 樹(shù)，其中 U 是 T 的頂點(diǎn)集，TE 是 T 的邊集，U 和 TE 的初值均為空集。算法開(kāi)始 時(shí)，首先從 V 中任取一個(gè)頂點(diǎn)（假定取 V0） ，將它并入 U 中，此時(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 的邊

8、集 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)為“加點(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

9、)在無(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 次（1kn-1）前，生成樹(shù) T 中已有 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ù)雜度 0（k（n-k） ） ，是很費(fèi)時(shí)間的，是否有好的方法能夠降低查找最短邊的時(shí)間復(fù) 雜度。 (2). 上述

10、問(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ù)雜度降低到 O(n-k)。具體方法是假定在進(jìn)行第 k 次前已經(jīng)保留著從 T 中到 T 外 的每一頂點(diǎn)（共 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ì)

11、于其中的每個(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ù)雜度為 O(n-k)。 三 概要分析和設(shè)計(jì) 3.1 概要分析概要分析 通過(guò)對(duì)上述算法的分析，將從以下三方面來(lái)進(jìn)行分析： (1). 輸入數(shù)據(jù)的類(lèi)型 在本次設(shè)計(jì)中，是對(duì)無(wú)

12、向圖進(jìn)行操作，網(wǎng)中的頂點(diǎn)數(shù)，邊數(shù)，頂點(diǎn)的編號(hào)及 每條邊的權(quán)值都是通過(guò)鍵盤(pán)輸入的，他們的數(shù)據(jù)類(lèi)型均為整型，其中，權(quán)值的范 圍為 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é)果； 圖 1.單一節(jié)點(diǎn)的無(wú)向圖 (二)假設(shè)創(chuàng)建的無(wú)向圖如圖 2 所示，驗(yàn)證運(yùn)行結(jié)果； A 圖 2.網(wǎng)中存在權(quán)值相等的邊 (三)假設(shè)創(chuàng)建的無(wú)

13、向圖如圖 3 所示，驗(yàn)證結(jié)果； 圖 3，網(wǎng)中的權(quán)值各不相等 3.2 概要設(shè)計(jì)概要設(shè)計(jì) 在本次設(shè)計(jì)中，網(wǎng)的定義為 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)型定義如下： (1). 符號(hào)常量的定義 算法中涉及到兩個(gè)符號(hào)常量，定義如下： #define MAX 20 功能：用于表示網(wǎng)中最多頂點(diǎn)個(gè)數(shù)； #define INFINIT 32768 功能：用于表示權(quán)的最大值，即。 (2). 結(jié)構(gòu)體的定義 整個(gè)算法中涉及的結(jié)構(gòu)體定義如下： 定義結(jié)構(gòu)體 ArcNode 功能：用于存放邊的權(quán)值 typedef s

14、truct 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；/鄰接矩陣 AdjMatrix 定義結(jié)構(gòu)體 Node 功能：用于表示求最小生成樹(shù)時(shí)用到的輔助數(shù)組。 typedef struct int adjvex;/存放頂點(diǎn)編號(hào) int lowcost;/存放頂點(diǎn)權(quán)值 Node; 外部變量的定義 算法中涉及到兩個(gè)外部變量，定義如下： Node closeM

15、AX 功能：存放每個(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í)，直接輸出 “不存在最小生成樹(shù)”程序不在往后執(zhí)行，否則繼續(xù)往下執(zhí)行。 (3). 函數(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(AdjMatri

16、x *G) 功能：是完成無(wú)向網(wǎng)的創(chuàng)建，在其函數(shù)體中，首先通過(guò)鍵盤(pán)輸入網(wǎng)中頂點(diǎn)數(shù)， 若頂點(diǎn)個(gè)數(shù)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)值；然后， 輸出；最后，在頂點(diǎn) v0 并入 U 之后,利用 for 循環(huán)更新 closedgei；當(dāng)所有的頂點(diǎn) v0 都納入 U 集合之后，輸出最小生成樹(shù)中的頂點(diǎn)序 列及最小生成樹(shù)的權(quán)值之和。 五、子函數(shù) void display(AdjMat

17、rix *G) 功能：是創(chuàng)建的無(wú)向網(wǎng)所對(duì)應(yīng)的鄰接矩陣； 六、主函數(shù) void main() 功能：是完成對(duì)上述各子函數(shù)的調(diào)用，完成本次設(shè)計(jì)的要求，在其函數(shù)體中， 通過(guò) while 循環(huán)可以實(shí)現(xiàn)重復(fù)創(chuàng)建網(wǎng)以及可以從網(wǎng)中的不同頂點(diǎn)出發(fā)求出對(duì)應(yīng)的 最小生成樹(shù)。 (4). 流程圖 開(kāi)始 輸入 ch, 用于判斷是否創(chuàng)建 無(wú)向網(wǎng) Ch=“Y” 結(jié)束 輸入起點(diǎn) st 1調(diào)用 create()函數(shù) 2調(diào)用 display()函數(shù) Flog=0 st=0 3調(diào)用 prim()函數(shù) 4調(diào)用 minium()函數(shù) 圖 4.流程圖 上述流程圖反映了整個(gè)算法中各個(gè)子函數(shù)之間的嵌套調(diào)用，從主函數(shù)開(kāi)始順 序往下執(zhí)行，首先調(diào)

18、用 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)一實(shí)驗(yàn)一 只含一個(gè)頂點(diǎn)的無(wú)向圖。 圖 5. 只含一個(gè)頂點(diǎn)的無(wú)向圖 4.2實(shí)驗(yàn)二實(shí)驗(yàn)二 假定創(chuàng)建的無(wú)向網(wǎng)的頂點(diǎn)個(gè)數(shù)1，并且網(wǎng)中有些邊的權(quán)值相等。 圖 7.運(yùn)行結(jié)果 分析：在上述創(chuàng)建的無(wú)向網(wǎng)中，有些頂點(diǎn)之間沒(méi)有邊相

19、連接，所以在鄰接矩 陣中用表示，由于是以頂點(diǎn) 1 作為起點(diǎn)生成最小生成樹(shù)，所以上述運(yùn)行結(jié)果對(duì) 應(yīng)的生成樹(shù)如圖 7 所示。 4.3 實(shí)驗(yàn)三實(shí)驗(yàn)三 假定創(chuàng)建的無(wú)向網(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)鍵部分程序清單） #includestdio.h #includestring.h #includemalloc.h #in

20、cludeiostream.h #includeiomanip.h #define MAX 20 /最多頂點(diǎn)個(gè)數(shù) #define INFINIT 32768/表示極大值，即 typedef struct int adj; /adj 是權(quán)值類(lèi)型 ArcNode; typedef struct int vexsMAX,vexnum,arcnum; /*vexs 表示頂點(diǎn)向量;vexnum,arcnum 分別表示圖的頂點(diǎn)數(shù)和弧數(shù)*/ ArcNode arcsMAXMAX; /*鄰接矩陣*/ AdjMatrix; typedef struct int adjvex;/存放頂點(diǎn)編號(hào) int lowcos

21、t;/存放頂點(diǎn)權(quán)值 Node; Node closeMAX;/求最小生成樹(shù)時(shí)的輔助數(shù)組 int flag=0; /功能：標(biāo)志變量，當(dāng)創(chuàng)建網(wǎng)時(shí)，輸入的頂點(diǎn)個(gè)數(shù)=1 時(shí)，直接輸出 “不存在最小生成樹(shù)”程序 不在往后執(zhí)行，否則繼續(xù)往下執(zhí)行 int Locate(AdjMatrix *G,int V) /求頂點(diǎn)位置函數(shù) int j=-1,k; for(k=0;kvexnum;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)輸

22、入網(wǎng)中的頂點(diǎn)數(shù)：); scanf(%d, if(G-vexnumarcnum); for(i=0;ivexnum;i+) /初始化鄰接矩陣 for(j=0;jvexnum;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;ivexnum;i+) scanf(%d, printf(輸入每條弧所對(duì)應(yīng)的兩個(gè)頂點(diǎn)及權(quán)值!n); for(k=0;karcnum;k+) printf(請(qǐng)輸入第%d 條邊:,m); m+; scanf(%d %d %d, /輸入一條弧的

23、兩個(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)/close中權(quán)值最小的邊 int i,min,k; min=INFINIT;/置最小權(quán)值為 INFINIT for(i=0;ivexnum;i+) if(closei.lowcostvexsn+=u; closek.lowcost=0;/初始化 U=u for(i=0;ivexnum;i+) if(i!=k) /對(duì) V-U 中的頂點(diǎn) i,初

24、始化 closei closei.adjvex=u; closei.lowcost=G-arcski.adj; for(j=1;jvexnum-1;j+)/n-1 條邊(n=G-vexnum) k0=Minium(G,close);/closek0中存有當(dāng)前最小邊(u0, v0)的信息 u0=closek0.lowcost;/u0U v0=G-vexsk0; /v0V-U p-vexsn+=v0;/將終點(diǎn)放入數(shù)組中 s+=closek0.lowcost;/求最小生成樹(shù)的權(quán)值之和 printf( %dt%dn,u,v0,closek0.lowcost); /輸出最小生成樹(shù)的路徑 closek0.

25、lowcost=0;/將頂點(diǎn) v0 納入 U 集合 for(i=0;ivexnum;i+)/在頂點(diǎn) v0 并入 U 之后,更新 closedgei if(G-arcsk0i.adjarcsk0i.adj; closei.adjvex=v0; printf(n 最小生成樹(shù)中的頂點(diǎn)序列為：); for(i=0;ivexnum;i+) printf( %d ,p-vexsi); printf(n); printf(n 最小生成樹(shù)的權(quán)值之和為：%dn,s); void display(AdjMatrix *G) /輸出鄰接矩陣算法 int i,j; for(i=0;ivexnum;i+) printf

26、(t%d,G-vexsi); printf(n); printf(); for(i=0;ivexnum;i+) printf(); printf(n); for(i=0;ivexnum;i+) printf( %d ,G-vexsi); for(j=0;jvexnum;j+) if(G-arcsij.adj=INFINIT) printf(t); else printf(t%d,G-arcsij.adj); printf(n); for(i=0;ivexnum;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ì) 者：李浩淵n); printf( 班 級(jí)：班n); printf( 指導(dǎo)老師：范純龍老師n); printf( 設(shè)計(jì)時(shí)間：2015 年 1