對(duì)于克魯斯卡爾算法這個(gè)問題感興趣的朋友應(yīng)該很多,這個(gè)也是目前大家比較關(guān)注的問題,那么下面小好小編就收集了一些克魯斯卡爾算法相關(guān)的知識(shí)回答,來分享給大家希望能夠幫助到你哦。1、
2、克魯斯卡爾算法:是一種用來尋找最小生成樹的算法。在剩下的所有未選取的邊中,找最小邊,如果和已選取的邊構(gòu)成回路,則放棄,選取次小邊。
3、基本思想:先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)、邊集為空的子圖,把子圖中各個(gè)頂點(diǎn)看成各棵樹上的根結(jié)點(diǎn),之后,從網(wǎng)的邊集 E 中選取一條權(quán)值最小的邊,若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹,則將其加入子圖,即把兩棵樹合成一棵樹,反之,若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上,則不可取,而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推,直到森林中只有一棵樹,即子圖中含有 n減1條邊為止。
本文到此結(jié)束,希望對(duì)大家有所幫助。