tft每日頭條

 > 知識

 > 克魯斯卡爾算法

克魯斯卡爾算法

知識 更新时间:2024-07-03 15:21:00

  克魯斯卡爾算法:是一種用來尋找最小生成樹的算法。在剩下的所有未選取的邊中,找最小邊,如果和已選取的邊構成回路,則放棄,選取次小邊。

  基本思想:先構造一個隻含 n 個頂點、邊集為空的子圖,把子圖中各個頂點看成各棵樹上的根結點,之後,從網的邊集 E 中選取一條權值最小的邊,若該條邊的兩個頂點分屬不同的樹,則将其加入子圖,即把兩棵樹合成一棵樹,反之,若該條邊的兩個頂點已落在同一棵樹上,則不可取,而應該取下一條權值最小的邊再試之。依次類推,直到森林中隻有一棵樹,即子圖中含有 n減1條邊為止。

更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!

查看全部

相关知識资讯推荐

热门知識资讯推荐

网友关注

Copyright 2023-2024 - www.tftnews.com All Rights Reserved