algorithm - krukshalのアルゴリズムまたはPrimsアルゴリズムのどちらが最小全域木を見つけるのに優れていますか？

Question

重複の可能性：
クラスカルvsプリム

krukshalのアルゴリズムまたはPrimsアルゴリズムのどちらが最小全域木を見つけるのに優れていますか？

Answer 1

言及されていない Prim のアルゴリズムを支持する点を 1 つ追加します。N 個の点と x と y の間の距離の距離関数 d(x,y) が与えられた場合、空間 O(N) (ただし時間は N^2) を使用して Prim のアルゴリズムを実装するのは簡単です。

任意の点 A から始めて、サイズ N-1 の配列を作成し、A から他のすべての点までの距離を示します。最短距離に関連付けられたポイント B を選択し、スパニング ツリーで A と B をリンクし、配列内の距離を更新して、その他のポイントまでの距離と、B からその他のポイントまでの距離の最小値になるようにします。最短リンクが B からどこにあり、A からどこにあるかを書き留めます。続けます。

距離関数で指定された密なグラフに対してクラスカルのアルゴリズムを処理する同様の方法を知りません。大きな N の場合、時間 O(N^ 2)。