225

Prim のアルゴリズムをいつ使用し、 Kruskal の最小スパニング ツリーをいつ見つけるべきなのか疑問に思っていました。どちらも簡単なロジックで、最悪のケースも同じです。唯一の違いは、データ構造が少し異なる可能性がある実装です。では、決め手は何ですか？

4

10 に答える 10

228

多くのエッジを持つグラフがある場合は、Prim のアルゴリズムを使用します。

V個の頂点とE個のエッジを持つグラフの場合、 Fibonacci Heapを使用する場合、Kruskal のアルゴリズムはO(E log V)時間で実行され、Prim のアルゴリズムはO(E + V log V)の償却時間で実行できます。

Prim のアルゴリズムは、頂点よりも多くのエッジを持つ非常に密なグラフがある場合、制限内で大幅に高速になります。Kruskal は、より単純なデータ構造を使用するため、典型的な状況 (まばらなグラフ) でより優れたパフォーマンスを発揮します。

于 2009-07-28T18:36:55.007 に答える
36

あなたがこれを求めていないことは知っていますが、より多くの処理ユニットがある場合は、簡単に並列化できる可能性があるため、 Borůvka のアルゴリズムを常に検討する必要があります。したがって、Kruskal および Jarník-Prim アルゴリズムよりもパフォーマンス上の利点があります。

于 2012-03-03T22:14:44.300 に答える
31

Kruskalの時間計算量の最悪のケースはO(E log E)です。これは、エッジを並べ替える必要があるためです。 プリム時間の複雑さの最悪のケースは、優先度キューを使用したO(E log V) 、またはFibonacci Heapを使用したO(E+V log V)です。グラフがまばらな場合、つまり E=O(V) のようにエッジの数が少ない場合、エッジが既にソートされている場合、またはそれらを線形時間でソートできる場合は、Kruskal を使用する必要があります。グラフが密集している場合、つまり E=O(V²) のようにエッジの数が多い場合は Prim を使用する必要があります。

于 2016-06-06T12:34:54.920 に答える
27

クラスカルは、エッジを線形時間で並べ替えることができる場合、またはすでに並べ替えられている場合に、パフォーマンスを向上させることができます。

頂点へのエッジの数が多い場合は、プリムの方が適しています。

于 2009-07-28T18:43:52.497 に答える
5

クラスカルのアルゴリズムの重要なアプリケーションの 1 つは、シングル リンク クラスタリングです。

n 個の頂点を考慮すると、完全なグラフが得られます。これらの n 個の点の ak クラスターを取得するには、並べ替えられた一連のエッジの最初の n-(k-1) 個のエッジに対してクラスカルのアルゴリズムを実行します。グラフの k クラスターを最大で取得します。間隔。

于 2013-09-08T05:45:52.367 に答える
3

Kruskal の最適な時間は O(E logV) です。プリムが fib ヒープを使用している場合、O(E+V lgV) を取得できます。したがって、密なグラフでは、プリムの方がはるかに優れています。

于 2011-10-14T01:34:42.533 に答える
2

kruskal Algorithm では、与えられたグラフに多数の辺と多数の頂点がありますが、各辺には値または重みがあり、その代わりに新しいグラフを準備することができます。これは、循環的でないか、どの側からも接近していてはなりません。たとえば

graph like this 
                  _____________
|                |                     |
|                |                     |
|__________|                     |

任意の頂点 a,b,c,d,e,f に名前を付けます。

于 2016-04-17T01:56:42.957 に答える
2

Prim はより密度の高いグラフに適しています。この場合、主にノードを扱っているため、エッジを追加することでサイクルにあまり注意を払う必要もありません。複雑なグラフの場合、Prim の方が Kruskal よりも高速です。

于 2013-11-23T01:57:31.313 に答える