克魯斯卡爾演算法介紹 克魯斯卡爾演算法簡介

1、克魯斯卡爾演算法是求連通網的最小生成樹的另一種方法。與普里姆演算法不同，它的時間複雜度為O（eloge）（e為網中的邊數），所以，適合於求邊稀疏的網的最小生成樹。

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