最速の最小スパニングツリーアルゴリズム

Question

http://en.wikipedia.org/wiki/Minimum_spanning_tree

は私がベンチマークに最高の最高に対してツリーアルゴリズムをまたがる私の最低限を探しています。 誰かが私がこれらのアルゴリズムのC++実装をどこで見つけることができるか知っていますか？私はbingedとグーグルで何も見つかりませんでした。これらのアルゴリズムが最高の場合は、確かにどこかにC++の実装が必要ですか？

日にツリー アルゴリズムをまたがる最速の最小値はBorůvkaのアルゴリズムの 組み合わせと 逆に基づく線形時間に 無作為化アルゴリズムを発見した デイビット・カルガー、フィリップ・クライン、ロバート Tarjan、によって開発されました-deleteアルゴリズム[2] [3] バーナード・シャゼル（Bernard Chazelle）の最速非ランダム化アルゴリズム は、 ソフトヒープに基づいており、おおよその優先度は です。[4] [5]その実行時間はO（m α（m、n））であり、mは の辺の数であり、nは頂点の数であり、 αはAckermann関数の古典的な逆関数 である。 関数αは非常にゆっくりと成長するので、 すべての実用的な目的のために、 は定数よりも大きくないと考えられることがあります。 4;したがって、Chazelleのアルゴリズム は線形時間に非常に近くなります。 エッジ重みが の有界ビット長の整数である場合、決定的な アルゴリズムは、実行時間が直線 であることが分かっています。[6]存在するかどうかは、 一般的な重みのための実行時間が直線 の確定的アルゴリズムであるかどうかは依然として未解決の質問 です。しかし、Seth PetieおよびVijaya Ramachandranは、 が計算上の複雑度が であることが判明していることがわかっています。

私はすでにBoost C++のグラフアルゴリズムに対してテストしています。

Answer 1

Wikipediaのページで「最速最小スパニングツリーアルゴリズム」と表示されている場合、最も漸近的な境界（この場合、O（mα（m、n））、m、n 、およびあなたがペーストした見積もりに定義されたα。簡単に言えば、これは、非常に大きな入力値の場合、Cのある値に対して常にC * m *α（m、n）で境界が取られることを意味します。このアルゴリズムは、非常に大きな入力値に対して他のものよりも高速であるにもかかわらず、より小さい入力値に適用された場合、他よりも遅くなる可能性があります。

2つのアルゴリズムの漸近的な境界を比較すると、どちらが速いかを調べる "テスト"がありません。各アルゴリズムの漸近的な境界を証明し、どちらが低いかを確認するだけです。 （入力サイズが無限大に行くと、「漸近的には」行動 - を指す。そして、それは無限のサイズの入力値を使用してテストを実行するのは難しい）

しかし、あなたは漸近的に使用してはならない場合があることに注意してください最速のアルゴリズム。 「C」が非常に大きい場合は、より小さなデータ値に対してより単純なアルゴリズムを使用するほうがよいでしょう。

私の推測では、あなたのアルゴリズムはCでは改善されるが、漸近的な境界では改善されないだろう。しかし、私が間違っていたら、それをACMに提出してください！

詳細情報については、以下を参照してください。「並べ替え、ヒープ、および最小全域木に」http://en.wikipedia.org/wiki/Big_O_notation

Answer 2

www.dcc.uchile.cl/~raparede/publ/09algorIQS.pdf 、 ゴンサロ・ナバロとロドリゴ・パレデスを

は、コア内外のいくつかの「最高の」最高のメモリ測定値を表示し、より古い 実装への参照を示します。

彼らはとても 原則的にあなたがテストを行うと 者、出版グラフで比較することができ、 グラフのサイズの関数としてのI/OとCPU時間の＃を報告し、よくそのテストケースを記述します。あなたのプリム2 の参考資料（Peter Sandersのコード、 のコードは自由に入手できます）を使用して、 自分の測定値を較正することができます。