グラフ G の辺の重みが [0,1] に一様に分布しているとします。どちらのアルゴリズム プリムまたはクラスカルが高速になりますか? ソートはクラスカルアルゴリズムのボトルネックステップであるため、特定のソートアルゴリズムを利用できるため、クラスカルになると思います。
1821 次
3 に答える
0
これは、ベンチマークする必要があるものです。ファンシーなデータ構造 (van Emde Boas ツリー) と並べ替えアルゴリズム (一部のカウント並べ替えバリアント) を使用して、両方のアルゴリズムの理論上の予想複雑さを線形に近づけることができます。ただし、そのようなトリックがいずれかのアルゴリズムの実際のパフォーマンスを向上させることができるかどうかは不明です。メモリの局所性を改善するための悪ふざけは、おそらくより大きな違いを生むでしょう。
于 2013-06-09T16:53:24.167 に答える
0
エッジの重みの分布は重要ではありません。
Prims と Kruskals の主な違いは、Prim のアルゴリズムは頂点数の 2 乗に比例する時間で実行されるのに対し、Kruskal のアルゴリズムはエッジ数とエッジ数の対数の積に比例して実行されることです。したがって、密なグラフでは Prim の方が高速であり、疎なグラフでは Kruskal の方が高速です。
たとえば、1000 個の頂点と 3000 個のエッジ (スパース) がある場合、Prim は K1 * 1,000,000 になり、Kruskal は K2 * 24,000 になります。しかし、1000 個の頂点と 250,000 個のエッジ (高密度) がある場合、Kruskal は K2 * 3,100,000 になります。
于 2013-06-09T17:31:59.503 に答える