克魯斯卡爾算法最小生成樹（克魯斯卡爾算法）

大家好,小霞來為大家解答以上的問題。克魯斯卡爾算法最小生成樹，克魯斯卡爾算法這個很多人還不知道,現在讓我們一起來看看吧！

1、設有一個有n個頂點的連通網N={V,E},最初先構造一個只有n個頂點，沒有邊的非連通圖T={V, E},圖中每個頂點自成一個連通分量。

2、當在E中選到一條具有最小權值的邊時,若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T中；否則將此邊舍去，重新選擇一條權值最小的邊。

3、如此重復下去，直到所有頂點在同一個連通分量上為止。

4、2算法描述編輯克魯斯卡爾算法的時間復雜度為O（eloge）(e為網中邊的數目)，因此它相對于普里姆算法而言，適合于求邊稀疏的網的最小生成樹。

5、克魯斯卡爾算法從另一途徑求網的最小生成樹。

6、假設連通網N=（V，{E}），則令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=（V，{∮}），圖中每個頂點自成一個連通分量。

7、在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。

8、依次類推，直至T中所有頂點都在同一連通分量上為止。

9、例如圖為依照克魯斯卡爾算法構造一棵最小生成樹的過程。

10、代價分別為1，2，3，4的四條邊由于滿足上述條件，則先后被加入到T中，代價為5的兩條邊（1，4）和（3，4）被舍去。

11、因為它們依附的兩頂點在同一連通分量上，它們若加入T中，則會使T中產生回路，而下一條代價（=5）最小的邊（2，3）聯結兩個連通分量，則可加入T。

12、因此，構造成一棵最小生成樹。

13、上述算法至多對 e條邊各掃描一次，假若以“堆”來存放網中的邊，則每次選擇最小代價的邊僅需O（loge）的時間（第一次需O（e））。

14、又生成樹T的每個連通分量可看成是一個等價類，則構造T加入新的過程類似于求等價類的過程，由此可以以“樹與等價類”中介紹的 mfsettp類型來描述T，使構造T的過程僅需用O（eloge）的時間，由此，克魯斯卡爾算法的時間復雜度為O（eloge）。

15、[1]。

本文到此分享完畢，希望對大家有所幫助。