導(dǎo)讀 關(guān)于克魯斯卡爾算法的時間復(fù)雜度是多少，什么是克魯斯卡爾算法這個問題很多朋友還不知道，今天小六來為大家解答以上的問題，現(xiàn)在讓我們一起
關(guān)于克魯斯卡爾算法的時間復(fù)雜度是多少，什么是克魯斯卡爾算法這個問題很多朋友還不知道，今天小六來為大家解答以上的問題，現(xiàn)在讓我們一起來看看吧！
1、計算最小生成樹的算法克魯斯卡爾算法 假設(shè) WN=(V,{E}) 是一個含有 n 個頂點(diǎn)的連通網(wǎng)，則按照克魯斯卡爾算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個只含 n 個頂點(diǎn)，而邊集為空的子圖，若將該子圖中各個頂點(diǎn)看成是各棵樹上的根結(jié)點(diǎn)，則它是一個含有 n 棵樹的一個森林。
2、之后，從網(wǎng)的邊集 E 中選取一條權(quán)值最小的邊，若該條邊的兩個頂點(diǎn)分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點(diǎn)分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。
3、依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。
本文分享完畢，希望對大家有所幫助。
標(biāo)簽：
免責(zé)聲明：本文由用戶上傳，如有侵權(quán)請聯(lián)系刪除！