版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授:劉斌克魯斯卡爾算法常州信息職業(yè)技術(shù)學(xué)院02教學(xué)目標(biāo)12克魯斯卡爾算法的具體實現(xiàn)03克魯斯卡爾算法的分析三、鏈表的插入04克魯斯卡爾算法1.5克魯斯卡爾算法實現(xiàn)具體算法void SortEdge(MGraph *G)/對Edge中各元素按權(quán)值從小到大排序int i,j,temp;char ch;for(i=0;ie;i+)for(j=i+1;je;j+)if(Edgei.weightEdgej.weight)temp=Edgei.weight;Edgei.weight=Edgej.weight;Edgej.weight=temp;ch=Edgei
2、.ch1;Edgei.ch1=Edgej.ch1;Edgej.ch1=ch;ch=Edgei.ch2;Edgei.ch2=Edgej.ch2;Edgej.ch2=ch;05克魯斯卡爾算法1.5具體算法int LocateVex(MGraph *G,VertexType ch)/確定頂點ch在圖G-vexs中的位置int i,k;for(i=0;in;i+)if(G-vexsi=ch)k=i;return k;06克魯斯卡爾算法1.5具體算法void KruskalMST(MGraph *G)/克魯斯卡爾算法求最小生成樹int p1,p2,i,j;int CCNumVertexNum;/標(biāo)記連通
3、分量號for(i=0;in;i+)CCNumi=i;/初始時共有n個連通分量,分量號分別為0,1,2,.,n-1SortEdge(G);/將邊數(shù)組元素按權(quán)值從小到大排序for(i=0;ie;i+)p1=CCNumLocateVex(G,Edgei.ch1);/p1表示ch1所在連通分量號p2=CCNumLocateVex(G,Edgei.ch2);/p2表示ch2所在連通分量號if(p1!=p2)/頂點ch1與頂點ch2只要不在同一個連通分量,將該邊加入TEprintf(%c,%c)-%dn,Edgei.ch1,Edgei.ch2,Edgei.weight);for(j=0;jn;j+)/將兩
4、個連通分量合并為一個連通分量p1if(CCNumj=p2)CCNumj=p1;07克魯斯卡爾算法1.5示例:對圖G的Edge數(shù)組進行按權(quán)值排序,下圖的排序結(jié)果如下:V0V3V1V5V4V25626364751Edge0=(v0,v2,1),Edge1=(v3,v5,2),Edge2=(v1,v4,3),Edge3=(v2,v5,4),Edge4=(v0,v3,5),Edge5=(v1,v2,5) ,Edge6=(v0,v1,6),Edge7=(v2,v4,6),Edge8=(v4,v5,6) ,Edge9=(v2,v3,7)。08克魯斯卡爾算法1.5V0V3V1V5V4V25626364751然后選取不在同一個連通分量的頂點,并將新的邊加入到TE中。并將兩個連通分量合并成同一個連通分量。重復(fù)以上操作,直到只有一個連通分量時位置。此時TE便是連通網(wǎng)G最小生成樹的邊集。結(jié)束算法。 09克魯斯卡爾算法1.5算法分析克魯斯卡爾算法的時間復(fù)雜度為O(e
溫馨提示
- 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)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 第五章 第三節(jié) 材料與制造工藝之塑料加工工藝
- 湖南省湘西土家族苗族自治州永順縣2025屆四年級數(shù)學(xué)第一學(xué)期期末調(diào)研試題含解析
- 湖南省張家界市桑植縣2024年數(shù)學(xué)六年級第一學(xué)期期末學(xué)業(yè)質(zhì)量監(jiān)測試題含解析
- 淮安市金湖縣2024年數(shù)學(xué)四上期末質(zhì)量檢測試題含解析
- 初中道德與法治七上第4課《幸福和諧的家庭》教學(xué)設(shè)計
- 健康信息學(xué) 患者健康卡數(shù)據(jù) 第3部分:有限臨床數(shù)據(jù) 編制說明
- 建筑設(shè)各階段具體服務(wù)內(nèi)容
- 辦公室裝修施工方案
- 2024年新人教版七年級上冊數(shù)學(xué)教學(xué)課件 6.1.1 立體圖形與平面圖形 第1課時 認識幾何圖形
- 2024年新人教版七年級上冊數(shù)學(xué)教學(xué)課件 第三章 代數(shù)式 復(fù)習(xí)題3
- QC七大手法和-新QC七大手法(簡體)
- 零星維修工程服務(wù)方案設(shè)計
- 5G技術(shù)在遠程發(fā)電廠監(jiān)控中的應(yīng)用
- 2024骨關(guān)節(jié)炎治療指南
- 新人教版二年級語文上冊第一二單元測試卷
- 人流手術(shù)報告單
- 人教版九年級上冊 第一單元 走進化學(xué)世界 說課稿
- 過度通氣健康宣教課件
- 江蘇鳳凰少年兒童出版社小學(xué)美術(shù)五年級下冊 第13課 詩配畫 全國公開課一等獎
- 電車與燃油車
- 小學(xué)科學(xué)教師專題培訓(xùn)課件
評論
0/150
提交評論