問題タブ [prims-algorithm]

プリムのアルゴリズムのウィキペディアのエントリを見ていましたが、隣接行列を使用した時間の複雑さが O(V^2) であり、ヒープと隣接リストを使用した時間の複雑さが O(E lg(V)) であることに気付きました。ここで、E はV はグラフの頂点の数です。

Prim のアルゴリズムはより密なグラフで使用されるため、E は V^2 に近づくことができますが、近づくと、ヒープの時間計算量は O(V^2 lg(V)) になり、O(V^2) よりも大きくなります。明らかに、ヒープは単に配列を検索するよりもパフォーマンスを向上させますが、時間の複雑さはそうではありません。

改善によってアルゴリズムの速度が実際にどのように低下​​するのでしょうか?

私の CS クラスでは、Prim のアルゴリズムを Java で実装する必要があり、プライオリティ キュー ステップに問題があります。私はプライオリティ キューを使用した経験があり、それらが一般的に機能することを理解していますが、特定のステップで問題が発生しています。

キー値 (ノードに接続されている最も軽いエッジであると想定) と親ノードを含むノード クラスを作成しました。私の問題は、ノードを優先キューに追加する方法を理解していないことです。親が NIL に設定され、キーが ∞ に設定されている場合、すべてのノードを優先キューに追加しても意味がありません。

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

私が使用した擬似コード：

私の理解によると：

• 1行目：実行V-1回数。
• 2行目：すべての頂点の次数の合計時間…..つまり2E時間

2行目ごとに2行目と4行目は、すべてのエッジを1つずつlog E追加/削除しているため、時間がかかります。PQ

したがって、合計time= V-1+2E.logE=E.log E

しかし、本はそれがそうだと言っていE.logVます、それがなぜであるか説明できますか？

Prim のアルゴリズムを C (www.bubblellicious.es/prim.tar.gz) で実装しましたが、これをKruskal のアルゴリズムに変換する方法を考えていました。

それらは非常に似ているようですが、古いコードを新しいコードに変更する方法が想像できません。アドバイスなど頂ければ有難いです。それが簡単なのはわかっていますが、私はまだ C プログラミングの初心者です ...

JGraphTには素晴らしいフィボナッチヒープクラスがあります。これを使用して、プリムの最小スパニングツリーアルゴリズムを実装するにはどうすればよいですか？

JGraphT で Prim の最小スパニング ツリー アルゴリズムを実装しようとしています。それはどのように見えますか？

私が遭遇した 1 つの問題は、JGraphT が指示どおりにすべてを処理することでした。そのため、リバースするためにいくつかのぎこちない呼び出しを行う必要がg.getEdgeSource(e)ありg.getEdgeTarget(e)、それらがたまたま正しくなかった場合があります。

JGraphT の Fibonacci Heap を使ってこれを最初に実装しようとしましたが、難しすぎたので、通常の PQ を行いました。

存在しないエッジの重みを無限に設定する代わりに、それをキューに追加しませんでした。

アドバイス？スタイルの問題？明らかな非効率性？独自のコードをロールバックする代わりに使用する必要があるコードはありますか?

プリムのアルゴリズムを使用してグラフの最小スパニングツリーを見つける場合、どのルートノードを選択するかは問題ではなく、結果のMSTの重みは同じになると直感的に感じます。これは正しいです？

私はコーメンらの本から勉強してきましたが、彼らが提供したアルゴリズムについて少し混乱しています。Prim のアルゴリズムの概念がウィキペディアでどのように機能するかを理解しましたが、私の本で提供されているアルゴリズムを使用してその動作を模倣することはできません。

章の次のオンライン コピーを参照して ください。

アルゴは上記リンクの 13 ページに記載されており、図の例は前のページにあります。

ここで、最初のステップで、例のケースでアルゴリズムを使用します。

u <--- ExtractMin(Q) を介したノード A。次に、図のように、Adj[u] にノード b とノード h の 2 つのエントリがあります。

最初に v <---- ノード b を設定します。次に、v が Q に属しているかどうかを確認します。そうです。w(u,v) < key[v] かどうかを確認します。真実。したがって、PI[v] <--- u およびキー [v] <--- w(u, v) です。こんなに取れました。これは 12 ページの図の (b) に示されています。

しかし、アルゴリズムは「Adj[u]の各vに対して」と言います。

したがって、次のステップでは v <--- ノード h を設定する必要があります。次に、v が Q に属しているかどうかを確認します。そうです! w(u,v) < key[v] ですか? です！key[v] = 無限だから! しかし、この図では (c) の部分で別のステップが示されています。

あああああ！なんで？

疎なグラフと密なグラフに関して、Prim と Kruskal の時間の複雑さが異なる理由を理解しようとしています。それぞれがどのように機能するかを示すいくつかのアプレットを使用した後でも、グラフの密度がアルゴリズムにどのように影響するかについて、まだ少し混乱しています。誰かが私に正しい方向への微調整をしてくれることを願っています。