資料結構與演算法——克魯斯卡爾（Kruskal）演算法 - IT人

克魯斯卡爾演算法圖解 · 第1 步：將邊 E,F [2] 加入R 中。

· 第2 步：將邊 C,D [3] 加入R 中。

· 第3 步：將邊 D,E [4] 加入R 中。

· 第4 步：將邊 B,F [7] ... Togglenavigation IT人 IT人 資料結構與演算法——克魯斯卡爾（Kruskal）演算法 天然呆dull發表於 2021-10-05 演算法 資料結構 目錄應用場景-公交站問題克魯斯卡爾演算法介紹克魯斯卡爾演算法圖解克魯斯卡爾演算法分析如何判斷迴路？程式碼實現無向圖構建克魯斯卡爾演算法實現獲取一個點的終點解釋 應用場景-公交站問題 某城市新增7個站點(A,B,C,D,E,F,G)，現在需要修路把7個站點連通，各個站點的距離用邊線表示(權)，比如A–B距離12公里問：如何修路保證各個站點都能連通，並且總的修建公路總里程最短? 如上圖所示：要求和前面的普利姆演算法中的修路問題是一樣的要求，只是換了一個背景。

克魯斯卡爾演算法介紹 克魯斯卡爾(Kruskal)演算法，是用來求加權連通圖的最小生成樹的演算法。

基本思想：按照權值從小到大的順序選擇n-1條邊，並保證這n-1條邊不構成迴路 具體做法： 首先構造一個只含n個頂點的森林 然後依權值從小到大從連通網中選擇邊加入到森林中，並使森林中不產生迴路，直至森林變成一棵樹為止 克魯斯卡爾演算法圖解 在含有n個頂點的連通圖中選擇n-1條邊，構成一棵極小連通子圖，並使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網的最小生成樹。

例如，對於如上圖G4所示的連通網可以有多棵權值總和不相同的生成樹。

有多種不同的連通方式，但是哪一種權值才是最優的呢？下面是克魯斯卡爾演算法的圖解步驟： 以上圖G4為例，來對克魯斯卡爾進行演示(假設，用陣列R儲存最小生成樹結果)。

第1步：將邊E,F[2]加入R中。

邊E,F的權值最小，因此將它加入到最小生成樹結果R中。

第2步：將邊C,D[3]加入R中。

上一步操作之後，邊C,D的權值最小，因此將它加入到最小生成樹結果R中。

第3步：將邊D,E[4]加入R中。

同理，權值最小 第4步：將邊B,F[7]加入R中。

上一步操作之後，邊C,E[5]的權值最小，但C,E會和已有的邊構成迴路；因此，跳過邊C,E。

同理，跳過邊C,F[6]。

將邊B,F加入到最小生成樹結果R中。

第5步：將邊E,G[8]加入R中。

同理 第6步：將邊A,B[12]加入R中。

上一步操作之後，邊F,G[9]的權值最小，但F,G會和已有的邊構成迴路；因此，跳過邊F,G。

同理，跳過邊B,C[10]。

將邊A,B加入到最小生成樹結果R中。

此時，最小生成樹構造完成！它包括的邊依次是：總里程為36。

動圖： 克魯斯卡爾演算法分析 根據前面介紹的克魯斯卡爾演算法的基本思想和做法，我們能夠了解到，克魯斯卡爾演算法重點需要解決的以下兩個問題： 對圖的所有邊按照權值大小進行排序。

此問題採用排序演算法進行排序即可 將邊新增到最小生成樹中時，怎麼樣判斷是否形成了迴路。

處理方式是：記錄頂點在最小生成樹中的終點，頂點的終點是在最小生成樹中與它連通的最大頂點。

然後每次需要將一條邊新增到最小生存樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構成迴路。

如何判斷迴路？ 在將E,F、C,DD,E加入到最小生成樹R中之後，這幾條邊的頂點就都有了終點： C的終點是F。

D的終點是F。

E的終點是F。

F的終點是F。

終點的說明：（備註：光看這個沒有接觸過該演算法的不明白，在程式碼後面有詳細的解釋） 就是將所有頂點按照從小到大的順序排列好之後；某個頂點的終點就是與它連通的最大頂點。

難道是說CD、DE、EF他們是一條線，從小到大，所以他們的終點都是F? 因此，接下來，雖然C,E是權值最小的邊。

但是C和E的終點都是F，即它們的終點相同，因此，將C,E加入最小生成樹的話，會形成迴路。

這就是判斷迴路的方式。

也就是說，我們加入的邊的兩個頂點不能都指向同一個終點，否則將構成迴路。

【後面有程式碼說明】 程式碼實現 無向圖構建 這裡使用上一章的普利姆演算法中實現的無向圖構建，簡單修改下 /** *克魯斯而 */ publicclassKruskalCase{ //不連通的預設值：0則代表同一個點 intINF=100000; /** *圖：首先需要有一個帶權的連通無向圖 */ classMGraph{ intvertex;//頂點個數 int[][]weights;//鄰接矩陣 char[]datas;//村莊資料 intedgeNum;//共有多少條邊 /** *@paramvertex村莊數量，會按照數量，按順序生成村莊，如A、B、C... *@paramweights需要你自己定義好那些點是連通的，那些不是連通的 */ publicMGraph(intvertex,int[][]weights){ this.vertex=vertex; this.weights=weights; this.datas=newchar[vertex]; for(inti=0;io.weight)); } //演算法主體 publicEdata[]kruskal(MGraphmGraph,Edata[]edatas){ //存放結果，陣列最大容量為所有邊的容量 Edata[]rets=newEdata[mGraph.edgeNum]; intretsIndex=0; /* 按照演算法思路： 記錄頂點在**最小生成樹**中的終點，頂點的終點是**在最小生成樹中與它連通的最大頂點**。

然後每次需要將一條邊新增到最小生存樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構成迴路。

*/ //用於存所有的終點：該陣列中的內容隨著被選擇的邊增加，終點也會不斷的增加 int[]ends=newint[mGraph.edgeNum];//解釋：陣列下標含義為起點索引，ends[i]為起點i的終點索引 //對所有邊進行遍歷 for(Edataedata:edatas){ //獲取這條邊的兩個頂點下標: //第一次：E,F->4,5 intp1=getPosition(mGraph.datas,edata.start); intp2=getPosition(mGraph.datas,edata.end); //獲取對應頂點的終點 /* 第1次：E,F->4,5 ends=[0,0,0,0,0,0,0,0,0,0,0,0] m:獲取4的終點：ends[4]為0，說明此點還沒有一個終點，那麼就返回它自己4 n:獲取5的終點：同上 m!=n,選擇這一條邊。

那麼此時E,F->4,5已有邊的終點就是5 ends=[0,0,0,0,5,0,0,0,0,0,0,0] 終點表中讀法：↑index=4,value=5那麼表示4這個頂點的終點為5 第2次：C,D->2,3 ends=[0,0,0,0,5,0,0,0,0,0,0,0] m:獲取2的終點，ends[2]=0，說明此點還沒有一個終點，則返回它自己2 n:獲取3的終點 m!=n,選擇這一條邊。

那麼此時C,D->2,3已有邊的終點就是3 ends=[0,0,3,0,5,0,0,0,0,0,0,0] 第3次：D,E->3,4 ends=[0,0,3,0,5,0,0,0,0,0,0,0] m:獲取3的終點，ends[3]=0，說明此點還沒有一個終點，則返回它自己3 n:獲取4的終點,!!前面第一次，已經將4的終點5放進來了 那麼將獲取到的終點為5，getEnd()還會嘗試去獲取5的終點，發現為0，則4的終點是5 m!=n->3!=5,選擇這一條邊。

那麼此時D,E->3,4已有邊的終點就是5 ends=[0,0,3,5,5,0,0,0,0,0,0,0] */ intm=getEnd(ends,p1); intn=getEnd(ends,p2); //判斷終點是否重合 if(m!=n){ ends[m]=n; rets[retsIndex++]=edata; } } returnrets; } /** *獲取該頂點的：終點 *這個演算法值得好好想想，下面有解析 *@paramends *@paramvertexIndex *@return */ privateintgetEnd(int[]ends,intvertexIndex){ inttemp=vertexIndex; while(ends[temp]!=0){ temp=ends[temp]; } returntemp; } /** *獲取此頂點的下標 * *@paramvertexs *@paramvertex *@return */ privateintgetPosition(char[]vertexs,charvertex){ for(inti=0;iitem!=null).mapToInt(item->item.weight).sum(); System.out.println("總里程數為："+total); } privatevoidprintEdatas(Edata[]edatas){ for(Edataedata:edatas){ if(edata==null){ continue; } System.out.println(edata); } } 測試輸出 ABCDEFG A0121000001000001000001614 B120101000001000007100000 C100000100356100000 D100000100000304100000100000 E10000010000054028 F167100000100000209 G1410000010000010000089100000 共有12條邊 邊陣列為： A,B[12] A,F[16] A,G[14] B,C[10] B,F[7] C,D[3] C,E[5] C,F[6] D,E[4] E,F[2] E,G[8] F,G[9] 排序後的邊陣列為： E,F[2] C,D[3] D,E[4] C,E[5] C,F[6] B,F[7] E,G[8] F,G[9] B,C[10] A,B[12] A,G[14] A,F[16] 克魯斯卡爾演算法計算結果的邊為： E,F[2] C,D[3] D,E[4] B,F[7] E,G[8] A,B[12] 總里程數為：36 獲取一個點的終點解釋 /** *獲取該頂點的：終點 * *@paramends *@paramvertexIndex *@return */ privateintgetEnd(int[]ends,intvertexIndex){ inttemp=vertexIndex; while(ends[temp]!=0){ temp=ends[temp]; } returntemp; } .... intp1=getPosition(mGraph.datas,edata.start); intp2=getPosition(mGraph.datas,edata.end); intm=getEnd(ends,p1); intn=getEnd(ends,p2); if(m!=n){ ends[m]=n; rets[retsIndex++]=edata; } 第1次：E,F->4,5 ends=[0,0,0,0,0,0,0,0,0,0,0,0] m:獲取4的終點：ends[4]為0，說明此點還沒有一個終點，那麼就返回它自己4 n:獲取5的終點：同上 m!=n,選擇這一條邊。

那麼此時E,F->4,5已有邊的終點就是5 ends=[0,0,0,0,5,0,0,0,0,0,0,0] 終點表中讀法：↑index=4,value=5那麼表示4這個頂點的終點為5 第2次：C,D->2,3 ends=[0,0,0,0,5,0,0,0,0,0,0,0] m:獲取2的終點，ends[2]=0，說明此點還沒有一個終點，則返回它自己2 n:同理，獲取3的終點 m!=n,選擇這一條邊。

那麼此時C,D->2,3已有邊的終點就是3 ends=[0,0,3,0,5,0,0,0,0,0,0,0] 第3次：D,E->3,4 ends=[0,0,3,0,5,0,0,0,0,0,0,0] m:獲取3的終點，ends[3]=0，說明此點還沒有一個終點，則返回它自己3 n:獲取4的終點,!!前面第一次，已經將4的終點5放進來了 那麼將獲取到的終點為5，getEnd()還會嘗試去獲取5的終點，發現為0，返回5，則4的終點是5 m!=n->3!=5,選擇這一條邊。

那麼此時D,E->3,4已有邊的終點就是5 ends=[0,0,3,5,5,0,0,0,0,0,0,0] 從以上的步驟執行來看，這個終點的判定是這樣的： E,F->4,5由於終點列表中沒有，那麼第一條邊的起點E的終點就是F 記為： ends=[0,0,0,0,5,0,0,0,0,0,0,0] 終點表中讀法：↑index=4,value=5那麼表示4這個頂點的終點為5 C,D->2,3 [0,0,3,0,5,0,0,0,0,0,0,0] 選擇這一條邊後，終點列表中成了上面這樣，如何理解？看上圖：這兩條邊新增之後，他們並不能連通，所以此時的ends列表裡面的含義就是這樣的： 2：3，C的終點是D，因為這條邊暫時沒有和其他邊連線 4：5，E的終點是F，因為這條邊暫時沒有和其他邊連線 D,E->3,4 此時：可以看到，加入我們要選擇這條邊，那麼DE就會和EF相連，獲取邊的終點時 [0,0,3,0,5,0,0,0,0,0,0,0] 先獲取D的終點：ends[3]=0，返回它自己； 獲取E的終點時：edns[4]=5，你會發現，其實E它已經和F連通了 那麼此時：往終點列表裡面存放的則是D的終點是F，而不是E（這裡可以看到獲取終點的演算法中的那個迴圈的妙用了） ends=[0,0,3,5,5,0,0,0,0,0,0,0] 最終選擇完後的終點列表中的資料為 [6,5,3,5,5,6,0,0,0,0,0,0] ABCDEFG 0123456 A的終點是G B的終點是F→G C的終點是D→F→G D的終點是F→G E的終點是F→G F的終點是G 選擇看明白了嗎？它利用這一個陣列，對於每次新增的邊和已經存在的邊，計算出，新增加的邊的起始點，對應的終點是什麼。

當整個最小生成樹都完成的時候，他們最終所對應的終點都是一樣的。

相關文章 excel模板資料填充：tablefill 2021-10-01 Excel 送你一個Python資料排序的好方法 2021-10-02 Python 【Golang】Go通過結構(struct)實現介面(interface) 2021-10-02 Go chan資料結構與理解 2021-10-02 資料結構 T-SQL——關於表資料的複製插入 2021-10-02 SQL FastAPI（44）-操作關係型資料庫 2021-10-02 資料庫 ESET：資料顯示Android對網路犯罪者來說比iOS更有吸引力 2021-10-02 AndroidiOS LeetCode演算法題系列（第一週25道） 2021-10-03 演算法LeetCode 【Go進階—資料結構】slice 2021-10-03 資料結構Go 全球46%的On-Prem資料庫包含漏洞：法國最“脆弱”，中國平均bug數最多 2021-10-03 資料庫 【資料結構與演算法】中綴表示式轉字尾表示式以及字尾表示式的計算 2021-10-04 演算法資料結構 Slice在使用過程中需要懂的一些資料結構 2021-10-05 資料結構 旅行好幫手：精準可靠的航班動態資料服務 2021-10-06 go中map的資料結構理解 2021-10-06 資料結構Go 排序演算法解析 2021-10-06 演算法 資料結構與演算法——迪傑斯特拉（Dijkstra）演算法 2021-10-06 演算法資料結構 最新文章 從2021分散式資料庫開發者大會裡，我們找出了這8個關鍵詞 c#多程式通訊，今天，它來了 .netcore和WPF開發升訊威線上客服系統：呼叫百度翻譯介面實現實時自動翻譯 【Spring專場】「AOP容器」不看原始碼就帶你認識核心流程以及運作原理 資料型別與函式索引-Oracle篇 mongodb基礎整理篇————常規操作[二] C語言execve()函式 Photoshop破解版百度網盤（百度雲）資源附序號產生器 XCOrganizerforMac-專案標籤分配追蹤軟體 在實驗中觀察指標——C++函式引數的壓棧順序 劍指offer-Go版實現第五章：優化時間和空間效率 js中的toString方法