對(duì)于克魯斯卡爾算法這個(gè)問(wèn)題感興趣的朋友應(yīng)該很多，這個(gè)也是目前大家比較關(guān)注的問(wèn)題，那么下面小好小編就收集了一些克魯斯卡爾算法相關(guān)的知識(shí)回答，來(lái)分享給大家希望能夠幫助到你哦。

1、

1、

2、克魯斯卡爾算法：是一種用來(lái)尋找最小生成樹(shù)的算法。在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構(gòu)成回路，則放棄，選取次小邊。

3、基本思想：先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)、邊集為空的子圖，把子圖中各個(gè)頂點(diǎn)看成各棵樹(shù)上的根結(jié)點(diǎn)，之后，從網(wǎng)的邊集 E 中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹(shù)，則將其加入子圖，即把兩棵樹(shù)合成一棵樹(shù)，反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹(shù)上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直到森林中只有一棵樹(shù)，即子圖中含有 n減1條邊為止。

本文到此結(jié)束，希望對(duì)大家有所幫助。

版權(quán)說(shuō)明：本文由用戶上傳，如有侵權(quán)請(qǐng)聯(lián)系刪除！

標(biāo)簽：