「クラスカル法」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【くらすかるほう (Kruskal's algorithm)】''' 1956年, クラスカルによって提案された最小木問題を解くためのアルゴリズムの1つ. 枝の...') |
細 ("クラスカル法" を保護しました。 [edit=sysop:move=sysop]) |
(相違点なし)
| |
2007年7月20日 (金) 09:33時点における版
【くらすかるほう (Kruskal's algorithm)】
1956年, クラスカルによって提案された最小木問題を解くためのアルゴリズムの1つ. 枝のない点集合のみの状態から, 枝の重みが小さい順に閉路を構成しない限り1本ずつ枝を加えていく操作を繰り返す. 全張木(全域木)が得られた時点で終了すると, その全張木が1つの最小木になっている. 貪欲算法の一種. 多項式時間アルゴリズムである.