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

沈陽(yáng)航空航天大學(xué) 課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告 課程設(shè)計(jì)名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課程設(shè)計(jì)題目 PrimPrim 算法求最小生成樹(shù)算法求最小生成樹(shù) 院 系 計(jì)算機(jī)學(xué)院 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 物聯(lián)網(wǎng)方向 班 級(jí) 學(xué) 號(hào) 姓 名 指導(dǎo)教師 0 學(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í)之處 本人愿意接受本 教學(xué)環(huán)節(jié) 不及格 和 重修或重做 的評(píng)分結(jié)論并承擔(dān)相關(guān)一切后 果 本人簽名 日期 2015 年 1 月 15 日 1 沈陽(yáng)航空航天大學(xué)沈陽(yáng)航空航天大學(xué) 課課程程設(shè)設(shè)計(jì)計(jì)任任務(wù)務(wù)書(shū)書(shū) 課程設(shè)計(jì)名稱 數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)課課程程設(shè)設(shè)計(jì)計(jì)專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù)計(jì)算機(jī)科學(xué)與技術(shù) 物聯(lián)網(wǎng)方向 物聯(lián)網(wǎng)方向 學(xué)生姓名班級(jí)學(xué)號(hào) 題目名稱Prim 算法生成最小生成樹(shù)算法生成最小生成樹(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é)出版社 2006 C 語(yǔ)言程序設(shè)計(jì) 譚浩強(qiáng) 清華大學(xué)出版社 2010 教教研研室室審審核核意意見(jiàn)見(jiàn) 教教研研室室主主任任簽簽字字 指導(dǎo)教師 簽名 指導(dǎo)教師 簽名 年月日 2 學(xué)學(xué) 生 簽名 生 簽名 2015年1 月 15 日 3 目目 錄錄 學(xué)術(shù)誠(chéng)信聲明學(xué)術(shù)誠(chéng)信聲明 1 一一 課程設(shè)計(jì)目的和要求課程設(shè)計(jì)目的和要求 4 1 1 課程設(shè)計(jì)目的 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 4 一 課程設(shè)計(jì)目的和要求 1 1 課程設(shè)計(jì)目的課程設(shè)計(jì)目的 一 根據(jù)算法設(shè)計(jì)需要 掌握連通網(wǎng)的數(shù)據(jù)表示方法 二 掌握最小生成樹(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)輸入 5 二 實(shí)驗(yàn)原理分析 2 1 最小生成樹(shù)的定義最小生成樹(shù)的定義 一個(gè)有 n 個(gè)結(jié)點(diǎn)的連通圖的生成樹(shù)是原圖的極小連通子圖 且包含原圖中 的所有 n 個(gè)結(jié)點(diǎn) 并且有保持圖連通的最少的邊 最小生成樹(shù)可以用 kruskal 克魯斯卡爾 算法或 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)稱 2 最小生成樹(shù)的分析 構(gòu)造最小生成樹(shù)可以用多種算法 其中多數(shù)算法利用了最小生成樹(shù)的 下面一種簡(jiǎn)稱為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 是 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 其中 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)都并入到 6 生成樹(shù) T 的頂點(diǎn)集中 此時(shí) U V TE 中含有 n 1 條邊 T 就是最后得到的最小生 成樹(shù) 可以看出 在普利姆算法中 是采用逐步增加 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í)最小生成樹(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 中已有 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 上述問(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ì)于其中的每個(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) 7 行第 k 1 次運(yùn)算做好了準(zhǔn)備 此步需進(jìn)行 n k 1 次比較 所以 利用此方法求第 k 次的最短邊共需比較 2 n k 1 次 即時(shí)間復(fù)雜度為 O n k 8 三 概要分析和設(shè)計(jì) 3 1 概要分析概要分析 通過(guò)對(duì)上述算法的分析 將從以下三方面來(lái)進(jìn)行分析 1 輸入數(shù)據(jù)的類型 在本次設(shè)計(jì)中 是對(duì)無(wú)向圖進(jìn)行操作 網(wǎng)中的頂點(diǎn)數(shù) 邊數(shù) 頂點(diǎn)的編號(hào)及 每條邊的權(quán)值都是通過(guò)鍵盤(pán)輸入的 他們的數(shù)據(jù)類型均為整型 其中 權(quán)值的范 圍為 0 32768 即 2 輸出數(shù)據(jù)的類型 當(dāng)用戶將無(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 9 圖 2 網(wǎng)中存在權(quán)值相等的邊 三 假設(shè)創(chuàng)建的無(wú)向圖如圖 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ù)類型的定義 在本設(shè)計(jì)中所涉及 10 到的數(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)體的定義 整個(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 vexs MAX vexs 表示頂點(diǎn)向量 int vexnum arcnum 分別表示圖的頂點(diǎn)數(shù)和弧數(shù) ArcNode arcs MAX MAX 鄰接矩陣 AdjMatrix 定義結(jié)構(gòu)體 Node 功能 用于表示求最小生成樹(shù)時(shí)用到的輔助數(shù)組 typedef struct int adjvex 存放頂點(diǎn)編號(hào) int lowcost 存放頂點(diǎn)權(quán)值 Node 外部變量的定義 算法中涉及到兩個(gè)外部變量 定義如下 11 Node close MAX 功能 存放每個(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) 在 vexs MAX 數(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ù)vexnum 其中 調(diào) 用函數(shù) Minium 求出輔助數(shù)組 close 中權(quán)值最小的邊 并將其在輔助數(shù)組中的 相應(yīng)位置返回到主調(diào)函數(shù)中并賦給 k0 此時(shí) close k0 中存有當(dāng)前最小邊 u0 v0 的信息 將邊所對(duì)應(yīng)的終點(diǎn)放入 p 的頂點(diǎn)向量表中 累加邊的權(quán)值 然后 輸出 最后 在頂點(diǎn) v0 并入 U 之后 利用 for 循環(huán)更新 closedge i 當(dāng)所有的頂點(diǎn) v0 都納入 U 集合之后 輸出最小生成樹(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)用 完成本次設(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 流程圖 13 開(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)用 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ì)的要求 14 四 測(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)值相等 15 圖 7 運(yùn)行結(jié)果 分析 在上述創(chuàng)建的無(wú)向網(wǎng)中 有些頂點(diǎn)之間沒(méi)有邊相連接 所以在鄰接矩 陣中用 表示 由于是以頂點(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é)果 如下 16 參考文獻(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 月 17 附 錄 關(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 struct int adj adj 是權(quán)值類型 ArcNode typedef struct int vexs MAX vexnum arcnum vexs 表示頂點(diǎn)向量 vexnum arcnum 分別表示圖的頂點(diǎn)數(shù)和弧數(shù) ArcNode arcs MAX MAX 鄰接矩陣 AdjMatrix typedef struct int adjvex 存放頂點(diǎn)編號(hào) int lowcost 存放頂點(diǎn)權(quán)值 Node Node close MAX 求最小生成樹(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 vexs k V j k 18 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 if G vexnumarcnum for i 0 ivexnum i 初始化鄰接矩陣 for j 0 jvexnum j if i j G arcs i j adj 0 else G arcs i j 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 輸入一條弧的兩個(gè)頂點(diǎn)及權(quán)值 i Locate G v1 j Locate G v2 G arcs i j adj weight G arcs j i adj weight return G 19 int Minium AdjMatrix G Node close close 中權(quán)值最小的邊 int i min k min INFINIT 置最小權(quán)值為 INFINIT for i 0 ivexnum i if close i lowcostvexs n u close k lowcost 0 初始化 U u for i 0 ivexnum i if i k 對(duì) V U 中的頂點(diǎn) i 初始化 close i close i adjvex u close i lowcost G arcs k i adj for j 1 jvexnum 1 j n 1 條邊 n G vexnum k0 Minium G close close k0 中存有當(dāng)前最小邊 u0 v0 的信息 u0 close k0 lowcost u0 U v0 G vexs k0 v0 V U p vexs n v0 將終點(diǎn)放入數(shù)組中 s close k0 lowcost 求最小生成樹(shù)的權(quán)值之和 printf d t d n u v0 close k0 lowcost 輸出最小生成樹(shù)的路徑 close k0 lowcost 0 將頂點(diǎn) v0 納入 U 集合 for i 0 ivexnum i 在頂點(diǎn) v0 并入 U 之后 更新 closedge i 20 if G arcs k0 i adjarcs k0 i adj close i adjvex v0 printf n 最小生成樹(shù)中的頂點(diǎn)序列為 for i 0 ivexnum i printf d p vexs i printf n printf n 最小生成樹(shù)的權(quán)值之和為 d n s void display AdjMatrix G 輸出鄰接矩陣算法 int i j for i 0 ivexnum i printf t d G vexs i printf n printf for i 0 ivexnum i printf printf n for i 0 ivexnum i printf d G vexs i for j 0 jvexnum j if G arcs i j adj INFINIT printf t else printf t d G arcs i j adj printf n for i 0 ivexnum i printf printf n void main 主函數(shù) char ch int st 21 AdjMatrix G p p AdjMatrix malloc sizeof AdjMatrix printf n printf 普里姆最小生成樹(shù)算法 n printf n n printf 設(shè) 計(jì) 者 李浩淵 n printf 班 級(jí) 34010105 班 n printf 指導(dǎo)老師 范純龍老師 n printf 設(shè)計(jì)時(shí)間 201