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