最小生成樹算法 prime算法和克魯斯卡爾算法
克魯斯卡爾算法
思路 優(yōu)先隊列+并查集

Kuskal算法

【算法簡介】：上一篇中的Prime算法是一種“加點式的算法”，而Kuskal算法是一種“加邊式的算法”；Kuskal算法與Prime算法都是一種貪心算法，但Kruskal算法對圖中存在相同權(quán)值的邊時也有效。
【算法思想】：算法對權(quán)值從小到大排序，每次選取當(dāng)前權(quán)值最小的邊加入結(jié)點，直到所有的結(jié)點都已加入結(jié)點。算法中用到了并查集的思想（并查集），通過并查集來判斷兩個結(jié)點是否有共同的父節(jié)點，如果有，則表明兩個結(jié)點已經(jīng)聯(lián)通。如果沒有，就將兩個結(jié)點聯(lián)通，記錄路徑。

Kruskal算法也是采用貪心算法的思想，運行時間為O（nlogn）。

代碼設(shè)計

1、利用優(yōu)先級隊列將權(quán)值小的邊放到隊列最前，優(yōu)先出對，保證了每次選擇的都是權(quán)值最小的邊。

2、利用并查集的查找及結(jié)合把同處同一連通分量中的頂點連到同一父節(jié)點下。這樣，每次判斷是否構(gòu)成回路，只要判斷父節(jié)點是否相同的即可。

1.1 存圖方式

使用結(jié)構(gòu)體數(shù)組來存圖；

//因為每條邊需要保存數(shù)據(jù) 起始節(jié)點 ，到達(dá)節(jié)點 ，花費(路的長度

總結(jié)

以上是生活随笔為你收集整理的数据结构——最小生成树之克鲁斯卡尔算法(Kruskal)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。