克魯斯卡爾算法介紹?克魯斯卡爾算法是求連通網的最小生成樹的另一種方法與普裡姆算法不同,它的時間複雜度為O(eloge)(e為網中的邊數),所以,适合于求邊稀疏的網的最小生成樹,今天小編就來說說關于克魯斯卡爾算法介紹?下面更多詳細答案一起來看看吧!
克魯斯卡爾算法是求連通網的最小生成樹的另一種方法。與普裡姆算法不同,它的時間複雜度為O(eloge)(e為網中的邊數),所以,适合于求邊稀疏的網的最小生成樹。
克魯斯卡爾(Kruskal)算法從另一途徑求網的最小生成樹。其基本思想是:假設連通網G=(V,E),令最小生成樹的初始狀态為隻有n個頂點而無邊的非連通圖T=(V,{}),圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊,若該邊依附的頂點分别在T中不同的連通分量上,則将此邊加入到T中;否則,舍去此邊而選擇下一條代價最小的邊。依此類推,直至T中所有頂點構成一個連通分量為止 。
更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!