很多朋友對于克魯斯卡爾算法步驟和克魯斯卡爾算法適用于什么圖不太懂，今天就由小編來為大家分享，希望可以幫助到大家，下面一起來看看吧！

什么是布魯斯卡爾算法

布魯斯卡爾算法是一種用來尋找最小生成樹最常用的算法，在剩下的所有未選取的邊中，找到最小邊，如果和已選取的邊構(gòu)成回路，則放棄，選取次小邊?？唆斔箍査惴ǖ臅r間復(fù)雜度為O（eloge），因此它相對于普里姆算法而言，適合于求邊稀疏的網(wǎng)的最小生成樹。

已知一個無向圖如下，分別用普里姆和克魯斯卡爾算法生成最小生成樹（假設(shè)以1為起點，試畫出構(gòu)造過程）

圖看不清，p，樹向外擴張，找最短外擴路徑k，增加一條不會造成回路的邊(現(xiàn)在選中的邊可以暫不相連)

普利姆算法與克魯斯卡爾算法

普利姆算法和克魯斯卡爾算法都是用于解決最小生成樹問題的經(jīng)典算法。普利姆算法以一個初始頂點開始，以貪心的方式逐步選擇與當前樹連通的最小權(quán)值邊，直到所有頂點都被包括進來。

克魯斯卡爾算法通過對邊集合按權(quán)值排序，并逐步選擇權(quán)值最小的邊，但保證不形成回路，直到生成樹涵蓋所有頂點。

兩者的不同在于，普利姆算法是以頂點為驅(qū)動，而克魯斯卡爾算法是以邊為驅(qū)動。

克魯斯卡爾算法的時間復(fù)雜度

克魯斯卡爾算法是在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構(gòu)成回路，則放棄，選取次小邊。

克魯斯卡其爾算法的時間復(fù)雜度為O（eloge）(e為網(wǎng)中邊的數(shù)目)，因此它相對于普里姆算法而言，適合于求邊稀疏的網(wǎng)的最小生成樹。

END，本文到此結(jié)束，如果可以幫助到大家，還望關(guān)注本站哦！