フィボナッチヒープでPrimのアルゴリズムを実装する方法は？

Question

知っている Primのアルゴリズム そして、私はその実装を知っていますが、いつも私が今尋ねたい部分をスキップします。 Primのアルゴリズムの実装があると書かれています フィボナッチヒープ は O(E + V log(V)) と 私の質問は次のとおりです。

• フィボナッチヒープと簡単に何がありますか？
• どのように実装されていますか？と
• フィボナッチヒープでPrimのアルゴリズムをどのように実装できますか？

Answer 1

フィボナッチヒープは、すべての操作で優れたアモリッツの漸近挙動を備えたかなり複雑な優先キューです - 挿入、検索、および減少キーはすべてo（1）の償却時間で実行されます。 （lg n）時間。このテーマに関する適切な参照が必要な場合は、CLRSによる「アルゴリズムの紹介、第2版」のコピーを選択し、その章を読むことを強くお勧めします。それは非常によく書かれており、非常に説明的です。 フレッドマンとタルジャンによるフィボナッチヒープの元の論文 オンラインで入手できます。チェックアウトしたい場合があります。濃いですが、材料の良い扱いを与えます。

Fibonacci HeapsとPrimのアルゴリズムの実装をご覧になりたい場合は、自分の実装のために恥知らずなプラグを提供する必要があります。

1. フィボナッチヒープの私の実装。
2. フィボナッチヒープを使用したPrimのアルゴリズムの実装。

これらの実装の両方のコメントは、それらがどのように機能するかについてのかなり良い説明を提供するはずです。明確にするためにできることがあるかどうか教えてください！

Answer 2

Primのアルゴリズムは、既に選択されている渦のグループと残りの渦の間の間の最低重量のエッジを選択します。
したがって、Primのアルゴリズムを実装するには、最小限のヒープが必要です。エッジを選択するたびに、すでに選択した渦のグループに新しい渦を追加し、その隣接するエッジはすべてヒープに入ります。
次に、ヒープから再び最小値でエッジを選択します。

だから私たちが得る時間は次のとおりです。
フィボナッチ：
最小エッジの選択= O（最小削除時間）= o（log（e））= o（log（v））
ヒープへのエッジの挿入= o（アイテムをヒープに挿入する時間）= 1

最小ヒープ：
最小エッジの選択= O（ヒープから最小を削除する時間）= o（log（e））= o（log（v））
ヒープへのエッジの挿入= o（アイテムをヒープに挿入する時間）= o（log（e））= o（log（v））

（e = 〜v^2 ... so log（e）== log（v^2）== 2log（v）= o（log（v））

したがって、合計でEインサートとVの最小選択があります（最終的には木です）。

それで、最小ヒープであなたは得る：

o（vlog（v） + elog（v））== o（elog（v））

そして、フィボナッチヒープであなたは得る：

o（vlog（v） + e）

Answer 3

数年前にFibonacci Heapsを使用してDijkstraを実装しましたが、問題はかなり似ています。基本的に、フィボナッチヒープの利点は、セットの最小値を一定の操作にすることです。これは、各ステップでこの操作を実行する必要があるPrimとDijkstraに非常に適しています。

なぜそれが良いのか

二項山（より「標準的な」方法です）を使用したこれらのアルゴリズムの複雑さはO（e * log v）です。二項山（log v）への新しい頂点（log v）（log v）を減らしてから、ヒープの最小値（別のログV）を見つける必要があります。

代わりに、フィボナッチヒープを使用すると、頂点を挿入するか、ヒープのキーを減らすコストが一定であるため、O（e）のみがあります。ただし、頂点の削除はO（log v）です。したがって、最終的にはすべての頂点が削除され、O（v * log v）が追加されるため、合計O（e + v * log v）が削除されます。

したがって、グラフが十分に密度が高い場合（E >> V）、フィボナッチヒープを使用することは二項山よりも優れています。

方法

したがって、フィボナッチヒープを使用して、すでに構築したサブツリーからアクセス可能なすべての頂点を保存し、それにつながる最小のエッジの重量でインデックス付けされています。別のデータ構造を使用することで実装またはPrimのアルゴリズムを理解した場合、代わりにフィボナッチヒープを使用することに実際の困難はありません。 入れる と Deletemin あなたが通常どおりにヒープの方法を使用し、 decraesekey 頂点を更新する方法につながるエッジをリリースしたときに頂点を更新する方法。

唯一の難しい部分は、実際のフィボナッチヒープを実装することです。

ここですべての実装の詳細を提供することはできません（ページを取ります）が、私が自分のことをしたとき、私は大きく依存していました アルゴリズムの紹介（Cormen et al）. 。まだ持っていないが、アルゴリズムに興味がある場合は、コピーを入手することを強くお勧めします！それは言語不可知論者であり、すべての標準アルゴリズムとその証拠に関する詳細な説明を提供し、それらすべてを使用する知識と能力を確実に高め、新しいものを設計し、証明します。 このPDF （リンクしたウィキペディアページから）実装の詳細の一部を提供しますが、それほど明確ではありません アルゴリズムの紹介.

私は持っています 報告 そしてa プレゼンテーション 私はそれをした後に書いた、それは少し進む方法を説明します（ダイクストラの場合 - 擬似コードのフィボナッチヒープ機能のPPTの終わりを参照）が、それはすべてフランス語です...そして私の コード Caml（およびフランス語）にいるので、それが役立つかどうかはわかりません!!!そして、あなたがそれの何かを理解できるなら、私はちょうどプログラミングを始めていたので、私のコーディングスキルは当時かなり貧弱でした...