




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、1最小生成樹算法-prim& Kruskal2生成樹的概念q生成樹一個連通圖的生成樹是一個極小連通子圖,它含有圖中全部頂點(diǎn),但只有足以構(gòu)成一棵樹的n-1條邊。生成樹不唯一V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5生成樹3最小代價生成樹q生成樹的代價等于其邊上的權(quán)值之和。生成樹的代價等于其邊上的權(quán)值之和。V4V1V3V2V6V56512665534V4V1V3V2V6V561654V4V1V3V2V6V5125344最小代價生成樹F兩種常用的構(gòu)造最小生成樹的方法:普里姆算法(prim)克魯斯卡爾算法( Kruskal Kruskal)
2、5普里姆(Prim)算法q假設(shè)假設(shè)N=(VN=(V,E)E)是連通網(wǎng),是連通網(wǎng),TETE是是N N上最小生成樹中邊的集合。上最小生成樹中邊的集合。q算法從算法從U=uU=u0 0(u(u0 0V)V),TE=TE=開始,重復(fù)執(zhí)行下述操作:開始,重復(fù)執(zhí)行下述操作:F在所有在所有uUuU,vV-UvV-U的邊的邊(u(u,v)v)中找一條代價最小的邊中找一條代價最小的邊(u(u0 0 ,v,v0 0),),將將其并入集合其并入集合TETE,同時將,同時將v v0 0并入并入U U集合。集合。F當(dāng)當(dāng)U=VU=V則結(jié)束,此時則結(jié)束,此時TETE中必有中必有n-1n-1條邊,則條邊,則T=(VT=(V,
3、TE)TE)為為N N的最小生的最小生成樹。成樹。q普里姆算法構(gòu)造最小生成樹的過程是從一個頂點(diǎn)普里姆算法構(gòu)造最小生成樹的過程是從一個頂點(diǎn)U=uU=u0 0 作初作初態(tài),不斷尋找與態(tài),不斷尋找與U U中頂點(diǎn)相鄰且代價最小的邊的另一個頂點(diǎn),中頂點(diǎn)相鄰且代價最小的邊的另一個頂點(diǎn),擴(kuò)充到擴(kuò)充到U U集合直至集合直至U=VU=V為止。為止。6V4V1V3V2V6V56512665534V4V1V3V2V6V512534UV-UV1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V1 ,V3 ,V6 V2 ,V4 , V5 (2)V1 ,V3 ,V6
4、 ,V4 V2, V5 (3)V1 ,V3 ,V6 ,V4 ,V2 V5 (4)V1 ,V3 ,V6 ,V4 ,V2 ,V5 (5)最小代價生成樹q普里姆算法求最小生成樹:從生成樹中只有一個頂點(diǎn)開始,到頂點(diǎn)全部進(jìn)入生成樹為止7V4V1V3V2V6V5165V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)UV-Uq普里姆算法求最小生成樹:從生成樹中只有一個頂點(diǎn)開始,到頂點(diǎn)全部進(jìn)入生成樹為止最小代價生成樹8V4V1V3V2V6V565V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 ,
5、 V5 ,V6 (1)V6V1 ,V3 ,V6 V2 ,V4 , V5 (2)46554UV-Uq普里姆算法求最小生成樹:從生成樹中只有一個頂點(diǎn)開始,到頂點(diǎn)全部進(jìn)入生成樹為止最小代價生成樹9V4V1V3V2V6V565V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V6V1 ,V3 ,V6 V2 ,V4 , V5 (2)4655V1 ,V3 ,V6 ,V4 V2, V5 (3)262UV-Uq普里姆算法求最小生成樹:從生成樹中只有一個頂點(diǎn)開始,到頂點(diǎn)全部進(jìn)入生成樹為止最小代價生成樹10V4V1V3V2V6V56V4V1V
6、31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V1 ,V3 ,V6 V2 ,V4 , V5 (2)465V1 ,V3 ,V6 ,V4 V2, V5 (3)62V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5UV-Uq普里姆算法求最小生成樹:從生成樹中只有一個頂點(diǎn)開始,到頂點(diǎn)全部進(jìn)入生成樹為止最小代價生成樹11V4V1V3V2V6V5V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)4
7、6V1 ,V3 ,V6 ,V4 V2, V5 (3)62V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5V1 ,V3 ,V6 ,V4 ,V2 ,V5 (5)33UV-Uq普里姆算法求最小生成樹:從生成樹中只有一個頂點(diǎn)開始,到頂點(diǎn)全部進(jìn)入生成樹為止最小代價生成樹12q普里姆算法求最小生成樹:從生成樹中只有一個頂點(diǎn)開始,到頂點(diǎn)全部進(jìn)入生成樹為止V4V1V3V2V6V5V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)4V1 ,V3 ,V6 ,V4 V2, V5
8、 (3)2V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5V1 ,V3 ,V6 ,V4 ,V2 ,V5 (5)3UV-U最小代價生成樹13普里姆(Prim)算法生成樹中只放置一個頂點(diǎn)在關(guān)聯(lián)生成樹頂點(diǎn)的邊中(即邊的一個頂點(diǎn)在生成樹中,另一個頂點(diǎn)不在)取權(quán)值最小者將選中的邊加入生成樹,同時將該邊的關(guān)聯(lián)頂點(diǎn)加入生成樹中生成樹中頂點(diǎn)數(shù)小于n?是否結(jié)束開始14l從鍵盤(或數(shù)據(jù)文件)輸入圖的信息,用普里姆算法求解從鍵盤(或數(shù)據(jù)文件)輸入圖的信息,用普里姆算法求解給定無向連通圖的最小生成樹,最后輸出最小生成樹中的給定無向連通圖的最小生成樹,最后輸出最小生成樹中的權(quán)值和所有的邊,圖的存儲結(jié)構(gòu)自行設(shè)定。權(quán)值
9、和所有的邊,圖的存儲結(jié)構(gòu)自行設(shè)定?;疽蠡疽驠例如 下圖的輸出為weight:15(v1, v3) (v3, v6) (v6, v4) (v3, v2) (v2, v5)或者(1, 3) (3, 6) (6, 4) (3, 2) (2, 5)15普里姆算法的實(shí)現(xiàn)q頂點(diǎn)集合如何表示?頂點(diǎn)集合如何表示?q最小邊如何選擇?最小邊如何選擇?q一個頂點(diǎn)加入一個頂點(diǎn)加入U U集合(生成樹中)集合(生成樹中) 如何表示?如何表示?struct int adjvex; double lowcost;closedgeMAX_VERTEX_NUM;closedgei.adjvex=kclosedgei.lo
10、wcost頂點(diǎn)i與頂點(diǎn)k鄰接頂點(diǎn)k已經(jīng)在U集合中頂點(diǎn)i加入U集合時= 016adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedgeclosedge2.adjvex=1 .lowcost=6closedge3.adjvex=1 .lowcost=1closedge4.adjvex=1 .lowcost=5V4V1V3V2V6V5165F當(dāng)當(dāng)U U集合中加入一個新頂點(diǎn)時,集合中加入一個新頂點(diǎn)時,V-UV-U集合中的頂點(diǎn)到集合中的頂點(diǎn)到U U的最小代價邊可能會更新的最小代價邊可能會更新V4V1V3V2V6V56512665
11、534U集合的成員:V-U集合的成員:closedge5.adjvex=1 .lowcost=closedge6.adjvex=1 .lowcost=17adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedgeV4V1V3V2V6V55564U集合的成員:V-U集合的成員:F當(dāng)當(dāng)U U集合中加入一個新頂點(diǎn)時,集合中加入一個新頂點(diǎn)時,V-UV-U集合中的頂點(diǎn)到集合中的頂點(diǎn)到U U的最小代價邊可能會更新的最小代價邊可能會更新V4V1V3V
12、2V6V56512665534closedge2.adjvex=3 .lowcost=5closedge4.adjvex=1 .lowcost=5closedge5.adjvex=3 .lowcost=6closedge6.adjvex=3 .lowcost=418adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66adjvexlowcostv350v62v360v1,v3,v6v2,v4,v5 4v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedgeV4V1V3V2V6V5562V
13、4V1V3V2V6V56512665534F當(dāng)U集合中加入一個新頂點(diǎn)時,V-U集合中的頂點(diǎn)到U的最小代價邊可能會更新U集合的成員:V-U集合的成員:closedge2.adjvex=3 .lowcost=5closedge4.adjvex=6 .lowcost=2closedge5.adjvex=3 .lowcost=619adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66adjvexlowcostv350v62v360v1,v3,v6v2,v4,v5 4adjvexlowcost
14、v3500v360v1,v3,v6,v4v2,v5 v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedge2V4V1V3V2V6V556F當(dāng)U集合中加入一個新頂點(diǎn)時,V-U集合中的頂點(diǎn)到U的最小代價邊可能會更新U集合的成員:V-U集合的成員:V4V1V3V2V6V56512665534closedge2.adjvex=3 .lowcost=5closedge5.adjvex=3 .lowcost=620adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66adjvexlowcostv3
15、50v62v360v1,v3,v6v2,v4,v5 4adjvexlowcostv3500v360v1,v3,v6,v4v2,v5 2adjvexlowcost000v230v1,v3,v6,v4,v2v5 v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedge5V4V1V3V2V6V53F當(dāng)U集合中加入一個新頂點(diǎn)時,V-U集合中的頂點(diǎn)到U的最小代價邊可能會更新V4V1V3V2V6V56512665534U集合的成員:V-U集合的成員:21adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5
16、,v66adjvexlowcostv350v62v360v1,v3,v6v2,v4,v5 4adjvexlowcostv3500v360v1,v3,v6,v4v2,v5 2v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedgeV4V1V3V2V6V5adjvexlowcost00000v1,v3,v6,v4,v2,v5adjvexlowcost000v230v1,v3,v6,v4,v2v5 514253U集合的成員:V-U集合的成員:V4V1V3V2V6V5651266553422 圖采用鄰接矩陣表示普里姆算法求最小生成樹普里姆算法求最小生成樹 6 1 5 6 5 3 1 5 5 6 4 5
17、5 2 3 6 6 4 2 6 1234561 2 3 4 5 6graph. arac = 23 #include #include #include #define INIT 63355 #define NUM 20 using namespace std; typedef int Elemtype; typedef struct Tnode Elemtype vexNUM; int aracNUMNUM; int v,e; graph; void Init_Graph(graph &g) for(int i = 1;i=g.v;i+) for(int j = 1;j=g.v;j+
18、) g.aracij = INIT; void Create_Graph(graph &g) cout輸入頂點(diǎn),邊數(shù)目:g.vg.e; Init_Graph(g); cout輸入頂點(diǎn)信息:endl; for(int i = 1;ig.vexi; cout輸入頂點(diǎn)間下標(biāo)和權(quán)值:endl; int k,t,w; for(int i = 1;iktw; g.arackt = w; g.aractk = g.arackt; 24 void Prim(graph &g) int min_cost = 0; int lowcostNUM; /當(dāng)前最短距離 int closestNUM; /
19、頂點(diǎn)的相鄰頂點(diǎn)(closesti則為i的鄰接點(diǎn)) int sNUM; /標(biāo)志訪問節(jié)點(diǎn) for(int i = 1;i=g.v;i+) closesti = 1; /初始置各頂點(diǎn)得鄰接點(diǎn)為1 lowcosti = g.arac1i; /初始置各頂點(diǎn)的最短距離為1到頂點(diǎn)的距離 si = 0; for(int i = 1;ig.v;i+) int min = INIT; /min初始化無窮大 int j = 1; for(int k = 2;k=g.v;k+) if(lowcostkmin&!sk) /找出與源點(diǎn)相連,且權(quán)值最小的頂點(diǎn) min = lowcostk; j = k; min_c
20、ost+=min; coutclosestjjendl; /輸出符合最小生成樹的頂點(diǎn) sj = 1; /已訪問頂點(diǎn)置1 for(int t = 2;t=g.v;t+) if(g.aracjtlowcostt&!st) /從新添加的頂點(diǎn)j出發(fā),將與j相鄰的頂點(diǎn)間的權(quán)值 /與上一頂點(diǎn)的相鄰頂點(diǎn)間的權(quán)值進(jìn)行比較。選出最小權(quán)值和相應(yīng)頂點(diǎn). lowcostt = g.aracjt; closestt = j; cout最小生成樹得最短路徑為:min_costendl; 25KruskalKruskal最小生成樹KruskalKruskal算法步驟:算法步驟:5642311653465265a.帶權(quán)圖此算法可以稱為“加邊法”,初始最小生成樹邊數(shù)為0,每迭代一次就選擇一條滿足條件的最小代價邊,加入到最小生成樹的邊集合里。1. 把圖中的所有邊按代價(權(quán)值)從小到大排序;2.將圖中的所有邊都去掉。 3.將邊按權(quán)值從小到大的順序添加到圖中,保證添加的過程中不會形成環(huán) (用并查集檢測 )4. 重復(fù)(3),直到所有頂點(diǎn)都在一顆樹內(nèi)或者有n-1條邊為止。261KruskalKrus
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- DB14-T 1586-2025 SH系矮化中間砧蘋果園滴灌技術(shù)規(guī)程
- 礦石石頭裝車合同安全運(yùn)輸與責(zé)任保險協(xié)議
- 土地抵押貸款及財產(chǎn)分配協(xié)議
- 創(chuàng)新型個人創(chuàng)業(yè)項目投資借款合同
- 供應(yīng)鏈金融財務(wù)顧問與風(fēng)險管理協(xié)議
- 2025年心理測量與評估考試題及答案
- 標(biāo)樣本橋梁技術(shù)范本
- 健康餐廳委托經(jīng)營及菜品創(chuàng)新合作協(xié)議范本
- 拆遷工程臨時用電設(shè)施拆除與施工合同
- 義工活動活動方案
- 2025年安全月安全有獎答題考試題庫(附答案)
- 浙江省寧波市2025年八年級下學(xué)期期末數(shù)學(xué)試題及答案及答案
- 北京歷史文化街區(qū)風(fēng)貌保護(hù)與更新設(shè)計導(dǎo)則
- 國能集團(tuán)工會工作報告
- 2025年商業(yè)管理與商業(yè)模式創(chuàng)新能力考核題及答案
- T/CBMCA 012-2020室內(nèi)環(huán)境清潔消毒服務(wù)規(guī)范
- 廣東省深圳市南山區(qū)2023-2024學(xué)年七年級下學(xué)期期末語文試題(含答案)
- 工程力學(xué)(山東科技大學(xué))知到智慧樹期末考試答案題庫2025年山東科技大學(xué)
- 補(bǔ)繳社保員工協(xié)議書
- 輻照滅菌委托協(xié)議書
- 2025標(biāo)準(zhǔn)勞動合同范本及模板
評論
0/150
提交評論