クラスカル法
2008年11月8日 (土) 19:44時点におけるAlbeit-Kun (トーク | 投稿記録)による版
【くらすかるほう (Kruskal's algorithm)】
1956年, クラスカルによって提案された最小木問題を解くためのアルゴリズムの1つ. 枝のない点集合のみの状態から, 枝の重みが小さい順に閉路を構成しない限り1本ずつ枝を加えていく操作を繰り返す. 全張木(全域木)が得られた時点で終了すると, その全張木が1つの最小木になっている. 貪欲算法の一種. 多項式時間アルゴリズムである.