「クラスカル法」の版間の差分
ナビゲーションに移動
検索に移動
細 ("クラスカル法" を保護しました。 [edit=sysop:move=sysop]) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
1956年, クラスカルによって提案された最小木問題を解くためのアルゴリズムの1つ. 枝のない点集合のみの状態から, 枝の重みが小さい順に閉路を構成しない限り1本ずつ枝を加えていく操作を繰り返す. 全張木(全域木)が得られた時点で終了すると, その全張木が1つの最小木になっている. 貪欲算法の一種. 多項式時間アルゴリズムである. | 1956年, クラスカルによって提案された最小木問題を解くためのアルゴリズムの1つ. 枝のない点集合のみの状態から, 枝の重みが小さい順に閉路を構成しない限り1本ずつ枝を加えていく操作を繰り返す. 全張木(全域木)が得られた時点で終了すると, その全張木が1つの最小木になっている. 貪欲算法の一種. 多項式時間アルゴリズムである. | ||
| + | |||
| + | [[Category:グラフ･ネットワーク|くらすかるほう]] | ||
2008年11月8日 (土) 19:44時点における最新版
【くらすかるほう (Kruskal's algorithm)】
1956年, クラスカルによって提案された最小木問題を解くためのアルゴリズムの1つ. 枝のない点集合のみの状態から, 枝の重みが小さい順に閉路を構成しない限り1本ずつ枝を加えていく操作を繰り返す. 全張木(全域木)が得られた時点で終了すると, その全張木が1つの最小木になっている. 貪欲算法の一種. 多項式時間アルゴリズムである.