希賽教育計算機專業考研專業課輔導招生
希賽教育計算機專業考研專業課輔導視頻
希賽教育計算機考研專業課在線測試系統
克魯斯卡爾算法的基本思想為為使生成樹上總的權值之和達到最小則應使每一條邊上的權值盡可能地小自然應從權值最小的邊選起直至選出n條互不構成回路的權值最小邊為止具體作法如下首先構造一個只含n個頂點的森林然後依權值從小到大從連通網中選擇不使森林中產生回路的邊加入到森林中去直至該森林變成一棵樹為止這棵樹便是連通網的最小生成樹
由於生成樹上不允許有回路因此並非每一條居當前權值最小的邊都可選例如在依次選中了(ef)(bc)(ed) 和 (fg) 的四條邊之後權值最小邊為 (gd)由於 g 和 d 已經連通若加上(gd) 這條邊將使生成樹上產生回路顯然這條邊不可取同理邊 (fd) 也不可取之後則依次取 (ag) 和 (ab) 兩條邊加入到生成樹
