克魯斯卡爾算法的時(shí)間復(fù)雜度是多少（什么是克魯斯卡爾算法）

關(guān)于克魯斯卡爾算法的時(shí)間復(fù)雜度是多少，什么是克魯斯卡爾算法這個(gè)問題很多朋友還不知道，今天小六來為大家解答以上的問題，現(xiàn)在讓我們一起來看看吧！

1、計(jì)算最小生成樹的算法克魯斯卡爾算法 假設(shè) WN=(V,{E}) 是一個(gè)含有 n 個(gè)頂點(diǎn)的連通網(wǎng)，則按照克魯斯卡爾算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)，而邊集為空的子圖，若將該子圖中各個(gè)頂點(diǎn)看成是各棵樹上的根結(jié)點(diǎn)，則它是一個(gè)含有 n 棵樹的一個(gè)森林。

2、之后，從網(wǎng)的邊集 E 中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹，則將其加入子圖，也就是說，將這兩個(gè)頂點(diǎn)分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。

3、依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。

本文分享完畢，希望對(duì)大家有所幫助。

標(biāo)簽：