Kruskalのアルゴリズムは、グラフの最小スパニングツリー(MST)を見つけるために使用される欲張りアルゴリズムです。最小スパニングツリーは、グラフのすべての頂点を接続し、最小の合計エッジ重みを持つツリーです。
Kruskalのアルゴリズムは、 最小ウェイト (MSTにはまだない)を繰り返し選択し、そのエッジで接続された2つの頂点がMSTにまだ接続されていない場合は最終結果に追加します。 Union - データ構造を使用して、2つの頂点がすでにMSTに接続されているかどうかを確認できます。 MSTのいくつかのプロパティは次のとおりです。
n
個の頂点を有するグラフのMSTは、厳密にn-1
n
辺を有する。