最小のスパンニングツリーは、すべてのノードをグラフ内のすべてのノードを、少なくとも総エッジ重量に接続するために使用されます。これらのツリーを見つけるための2つの一般的なアルゴリズムは、KruskalのアルゴリズムとPrimのアルゴリズムです。どちらも効率的ですが、アプローチと実装が異なります。

カルスカルのアルゴリズム

カルのアルゴリズムは、重みでグラフのすべてのエッジをソートします。 それから、最小限から始めて、サイクルが形成されないように、スパンニングツリーにエッジを追加します。 このプロセスは、すべてのノードが接続されるまで続きます。

アルゴリズムは、スパースグラフに特に有効です。 エッジを追加するかどうかを効率的に確認するために、disjointセットのデータ構造を使用します。

プライムのアルゴリズム

Prim のアルゴリズムは、任意のノードから始まり、ツリーを新しいノードに接続する最小端を追加することで、スパンニングツリーを成長させます。すべてのノードが含まれているまで、それは継続します。

この方法は、多くの場合、密なグラフに優先されます。 優先キューを使用して、次のエッジを最小重量で効率的に選択します。

比較・実装

どちらのアルゴリズムも最小のスパンツリーを見つけることを保証しますが、その効率はグラフの構造によって異なります。 Kruskalのは、ソートエッジの焦点を合わせる方が簡単です。 Primのは、優先キューを使用して密なグラフでより効率的なことができます。

  • カルスのソートは、グローバルに展開
  • Prim のツリーは、開始ノードから成長します
  • 両方の使用効率のための別のデータ構造
  • 選択はグラフ密度およびサイズによって決まります