tft每日頭條

 > 教育

 > 克魯斯卡爾算法介紹

克魯斯卡爾算法介紹

教育 更新时间:2025-01-07 11:02:58

  1、克魯斯卡爾算法是求連通網的最小生成樹的另一種方法。與普裡姆算法不同,它的時間複雜度為O(eloge)(e為網中的邊數),所以,适合于求邊稀疏的網的最小生成樹。

  2、克魯斯卡爾(Kruskal)算法從另一途徑求網的最小生成樹。其基本思想是:假設連通網G=(V,E),令最小生成樹的初始狀态為隻有n個頂點而無邊的非連通圖T=(V,{}),圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊,若該邊依附的頂點分别在T中不同的連通分量上,則将此邊加入到T中;否則,舍去此邊而選擇下一條代價最小的邊。依此類推,直至T中所有頂點構成一個連通分量為止 。

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

查看全部

相关教育资讯推荐

热门教育资讯推荐

网友关注

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