問題タブ [prims-algorithm]

ここには、重み属性に基づいて Link オブジェクトを格納する最小ヒープ クラスがあります。私の目的は、最小ヒープに格納されているオブジェクトの属性に直接アクセスして変更できるようにすることです。「loc」属性のみに基づいてこれらのオブジェクトにアクセスできる必要があります。
たとえば、loc 値が 6 の Link オブジェクトにアクセスして、その親属性または重み属性を変更したい場合があります。ただし、アクセス時の loc 属性値しかわかりません。
私の理解では、これらのオブジェクトへのポインターの配列を使用する必要がありますが、これをどのように実装するかはわかりません。

ありがとう！

グラフ内のすべての辺の重みが 1 から |V| の範囲の整数であるとします。Prim のアルゴリズムをどれくらい速く実行できますか? ある定数 W に対してエッジの重みが 1 から W の範囲の整数である場合はどうなるでしょうか?

私の教科書によると：

プリムのアルゴリズムの実行時間は、最小優先度キュー Q の実装方法によって異なります。Q をバイナリ最小ヒープとして実装すると、BUILD-MIN-HEAP 手順を使用して、O(V) の 1 ～ 5 行目を実行できます。時間。while ループの本体は |V| を実行します。各 EXTRACT-MIN 操作には O(lg V) 時間がかかるため、EXTRACT-MIN へのすべての呼び出しの合計時間は O(VlgV) です。行 8 ～ 11 の for ループは、すべての隣接リストの長さの合計が 2|E| であるため、全体で O(E) 回実行されます。for ループ内では、Q にあるかどうかを示す各頂点のビットを保持し、頂点が Q から削除されたときにビットを更新することにより、9 行目の Q のメンバーシップのテストを一定時間で実装できます。行 11 の割り当てには、バイナリ最小ヒープが O(lg V) 時間でサポートする、最小ヒープに対する暗黙の DECREASE-KEY 操作が含まれます。したがって、

行 1 ～ 4 には O(V) 時間が必要です。BUILD-MIN-HEAP プロシージャが線形時間を必要とする理由についていくつかの説明を読みましたが、理解できませんでした。MIN-HEAP プロシージャの時間計算量が O(V) である理由を説明していただけますか?

さらに、最小ヒープでは、最小要素がルートにあると考えました。では、各 EXTRACT-MIN 操作に O(lg V) の時間がかかるのはなぜですか?

すると、for ループが O(Σ_{v in VG} deg(v)) 回実行されますね。なぜ Σ_{v in VG} deg(v)=2E なのか説明していただけますか?

また、ある定数 W に対してエッジの重みが 1 から W の範囲の整数であることがわかっているとしたら、何が違うでしょうか?

編集：

グラフ内のすべての辺の重みが 1 から |V| の範囲の整数であるとします。Prim のアルゴリズムをどれくらい速く実行できますか?

プリムのアルゴリズムができるだけ速く実行されるように、上記のアルゴリズムで何を変更できますか?

C++ で MST のプリムのアルゴリズムを実装しようとしています。デザインに関する質問があります

整数を取る最小ヒープを実装し、最小値を抽出し、キーを減らし、キーを挿入できます。

プリムで理解しているように、各頂点の重みと隣接情報を維持する必要があります。私が持っているいくつかのアイデアは次のとおりです。

1]構造を定義する

最小ヒープを使用して、重みが最小のノードを返します。しかし、問題はキーの減少です。キーの減少の場合、呼び出し元はキーを減少させたい頂点を渡す必要があるためです。ヒープは要素を頻繁にスワップするため、リスト全体を調べて頂点を見つけ、そのキーを減らす必要があります。これは O(n) です。これを行うと Prim の状態が悪化すると思います。

2] もう 1 つの方法は、min-heap キュー内の頂点の位置を追跡する別の配列を維持することです。しかし、最小ヒープ操作中に位置を追跡するのは面倒です。

基本的に、reduce-key(v) を実行する必要がある場合、重みに基づく最小ヒープ キューで v を見つける方法。これを行うエレガントな方法はありますか？まだ複雑さを保持できるのはどれですか?

私は Java 開発者です (ただし、CS/IT 以外の教育歴があります)。私はアルゴリズムに興味を持ち、現在、MST を計算するための Prim のアルゴリズムを実装しようとしています。これは、コンテキストを知らせるために話しましたが、私の質問は MST とは無関係です。

Java.util.PriorityQueue を使用する代わりに、独自の MinHeap を実装しました (ただし、コードを変更して使用した場合でも、前に述べたのと同じ問題に直面していました)。

アイテムをヒープに追加しますが、アイテムがヒープに追加された後でも、比較を決定するアイテムの値が変わる可能性があります。値が変更されると、ヒープは変更されないため、アイテムを削除すると間違ったアイテムが飛び出します。

この状況にどう立ち向かうか..

参照用にコードを貼り付けています。MinHeap に Vertex タイプのアイテムを追加しています。各頂点には、頂点の 2 つのオブジェクトを比較するために使用される「int コスト」が関連付けられています。今、私はヒープに頂点のオブジェクトを追加し、ヒープは「コスト」の現在の値に従って調整されますが、頂点のオブジェクトが追加されると、そのコストが変更された場合、それを調整してヒープに反映させる方法について助けが必要です. この点で私を助けてください。また、間違った方向に進んでいる場合は修正してください。

だから私はこのグラフを持っています

最小スパニングツリーを構築しようとしています。頂点 AI から始めて ABFED に進み、その後、D に隣接するすべての頂点が既にツリーの一部であることを考えると、どこにも行きません。どうすれば続行できますか?

また、最小スパニング ツリーの一部となる新しいエッジの値の範囲を計算するにはどうすればよいですか?

よろしくお願いします。

最小頂点を選択する代わりに最大頂点を選択するようにアルゴリズムを変更して、最大スパニング ツリーを計算できますか?

エッジを無効にし、通常のプリムの最小スパニング ツリー アルゴリズムを適用することで、解決策を見つけました。