Looking for algorithm Answers? Try Ask4KnowledgeBase
Looking for algorithm Keywords? Try Ask4Keywords

algorithmKruskalのアルゴリズム


備考

Kruskalのアルゴリズムは、グラフの最小スパニングツリー(MST)を見つけるために使用される欲張りアルゴリズムです。最小スパニングツリーは、グラフのすべての頂点を接続し、最小の合計エッジ重みを持つツリーです。

Kruskalのアルゴリズムは、 最小ウェイト (MSTにはまだない)を繰り返し選択し、そのエッジで接続された2つの頂点がMSTにまだ接続されていない場合は最終結果に追加します。 Union - データ構造を使用して、2つの頂点がすでにMSTに接続されているかどうかを確認できます。 MSTのいくつかのプロパティは次のとおりです。

  1. n個の頂点を有するグラフのMSTは、厳密にn-1 n辺を有する。
  2. 各頂点から他のすべての頂点までの固有のパスが存在します。

Kruskalのアルゴリズム 関連する例