問題タブ [prims-algorithm]

EXTRACT-MINオペレーションとDECREASE-KEYプライオリティ キュー内のオペレーションの関係は? これは、Prim のアルゴリズムを使用した最小スパン問題の講義で遭遇しました。

MIT の教授は、ビデオの 01:07:16 秒の時点でそれについて言及していますが、私には理解できません。誰かが私のためにこれを片付けてもらえますか?

PS: それ以外の場合は、プライオリティ キューの理解に満足しています。

隣接行列を使用するプリムのアルゴリズムが時間計算量をもたらす理由を誰かが私に説明できますか？O(V2)

Prim のアルゴリズムと Kruskal のアルゴリズムはどちらも最小全域木を生成します。cut プロパティによると、ツリーの総コストはこれらのアルゴリズムで同じになりますが、複数の選択肢に直面したときにアルファベット順に選択することを考えると、これら 2 つのアルゴリズムが同じ総コストで異なる MST を与える可能性はありますか? . たとえば、エッジ A->B および B->C について max(source,dest) を比較し、A->B からの A と B->C からの B を比較します。

ありがとうございました

隣接行列を使用しています。優先キューはデータ構造です。

私の計算によると、複雑さは次のV^3 log Vとおりです。

• Whileループ：V
• 隣接する頂点の確認：V
• エントリがすでに存在する場合はキューをチェックし、同じものを更新します。V log v

しかし、私はどこでも複雑さはV^2

説明してください。

（最小スパニングツリーを作成するために）次のプリムのアルゴリズムを調べましたが、次のコードの入力値が何であるかわからないので、Gはもちろん送信されたグラフ（隣接行列またはリストグラフ）そして私は値sが開始すべき場所であると思いますか？また、それが開始である場合、次のアルゴリズムにどのように開始値を送信しますか？：

どんな助けでも大歓迎です、ありがとう！

これらの中で最も効率的なデータ構造は何ですか？

• エッジリスト
• 隣接リスト
• 隣接行列

Prim-Jarnikのアルゴリズムを実行するためとその理由は？

重複の可能性:
Kruskal vs Prim

Prim のアルゴリズムよりも Kruskal のアルゴリズムを使用して、最小スパニング ツリーを見つけるのはいつですか? 種類ごとに、どのような種類の入力グラフとノードが適していますか? スペースと時間に関して、それらのいずれかを使用する方が効率的なのはどのような場合ですか?

あるものを他のものよりもはるかに優れたものにする彼らの特定のインプットはありますか?

ダイクストラのアルゴリズムとプリムのアルゴリズムの正確な違いは何ですか? PrimがMSTを提供することは知っていますが、Dijkstraによって生成されたツリーもMSTになります。それでは、正確な違いは何ですか？

C++と行列を使用してプリムのアルゴリズムを実装しようとしています。

これが私の問題です：

cNodeは開始ノードです。

graph[][]接続を保持する2次元行列です。

nodeCon[]MST（どのノードが他のノードに接続されているか）の接続を保持するアレイです

node[]=nodeConのコスト値を保持します。

私の質問は、どのようにしてネクストホップに進むのかということです。最小の接続を見つけ、cNode= minConnectionループがどのように見えるかという値を設定するとしますか？すべてのノードを調べたことをどうやって知ることができますか？

前もって感謝します