クラスカル法

OR事典

クラスカル法

読み方：くらすかるほう
【英】：Kruskal's algorithm

1956年, クラスカルによって提案された最小木問題を解くためのアルゴリズムの1つ. 枝のない点集合のみの状態から, 枝の重みが小さい順に閉路を構成しない限り1本ずつ枝を加えていく操作を繰り返す. 全張木(全域木)が得られた時点で終了すると, その全張木が1つの最小木になっている. 貪欲算法の一種. 多項式時間アルゴリズムである.

「OR事典」の他の用語

グラフ･ネットワーク：

NP困難  PERT  TSP多面体  クラスカル法  クラスター分析  グラフ  シュタイナー最小木

ウィキペディア

クラスカル法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/30 08:14 UTC 版)

クラスカル法（英: Kruskal's algorithm）は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。