問題タブ [prims-algorithm]

最小スパニング ツリーの重みを見つけるには、boost ライブラリの kruskals アルゴリズムを使用する必要があります。私はそれを管理したと思います

ここで、頂点 0 とそこから最も遠い頂点の間の距離 (重みの合計) を見つける必要がありますか? どうすればそれができるかについてのヒントはありますか？

頂点イテレータを使用することを考えていましたが、重みを weightMap に格納するので、グラフの頂点を反復処理する場合、どのようにアクセスすればよいでしょうか?

編集: プログラムを修正し、kruskal と prim を使用することにしました

1. スパニング ツリーの重みの kruskal 2. 頂点 0 からの各頂点の距離の prim アルゴリズム (マップの距離に格納されているスパニング ツリー内)

残念ながら、何かがうまくいかず、3 番目の頂点である距離 [*頂点] は答え 2 を与えませんが、1 を与えます

また、スパニング ツリーの重みは 7 ではなく 14 です。

私のダミー入力は次のとおりです。

ここに私のプログラム：

ありがとうございました ：）

STL を使用して C++ で Prim の MST アルゴリズムを実装しようとしています。

しかし、次のプログラムでは、無限ループに入るようです。そして、エラーで終了します。

Prim の MST アルゴリズムの疑似コード ;

私のコード：

このアルゴリズムが実装されているグラフ:

プリムアルゴリズムの疑似コードを理解するのを手伝ってください（コアマンとウィキにあるように） プリムのアルゴリズム。

1 または while ループまで r.key=0 を理解することはできますが、ルートの近隣または隣接が最初にスキャンされることを保証しますが、u は既に Q に属しているため (これまでのノードのキューはプリムの最小スパニング ツリーに含まれていません)、v Q でも、プリム MST の生成には役立ちません。

また、コアマンとウィキの状態の両方

行 6 ～ 11 の while ループの各反復の前に、(v, v.parent) v :: を最小全域木に既に配置されている頂点に接続します。

A が MST であるため、v が既に MST に含まれているため (v ∈ V - {r} - Q で示されているように)、なぜそれを含める必要があるのか​​ 1. が役立ちます。

Prim のアルゴリズムの問​​題について支援が必要です。

Prim のアルゴリズムによって得られたグラフ G の最小全域木を T とする。G に新しい頂点と重み付きのいくつかの辺を追加し、新しい頂点を G のいくつかの頂点に接続して得られるグラフを Gnew とします。新しい辺の 1 つを T に追加することで、Gnew の最小全域木を構成できますか? はいと答えた場合は、その方法を説明してください。いいえの場合は、その理由を説明してください。

前もって感謝します！！

ほぼ完全にランダムになるように、等しいレートを使用して Prim's Maze ジェネレーターを作成しました。アルゴリズムのベンチマークを行ったところ、実行時間が O(5n) であることがわかりました。これは、128 x 128 の迷路を生成するのに 290 秒の実行時間に相当します。

私の質問は、これは良い実行時間ですか? これは高い、低い、平均ですか？スローダウンは、比較的軽量な整数比較よりも、迷路のノードのキャッシュに関係しているように感じます。まともな実装があるのか​​ 、それとも遅すぎるのかを知りたいだけです。

ランダムなグラフを描画するためにこのコードを書きました。線を選択するときにプリムのアルゴリズムを適用し、それらが最小ツリーを見つけたかどうかを確認できるように、グラフ内の線を選択する方法を見つけようとしても無駄でした。

これはstackoverflowで見つけましたが、あまり役に立ちません。HTML5キャンバスに描かれた線を選択するには? . 最初から作成する必要がないように、事前に作成されたコードがあるかどうか疑問に思っていました。

マウスが移動するときにマウスの位置を見つけて、ポイントが線上にあるかどうかを見つけるのように、マウスの位置が線上にあるかどうかを毎回確認できるかどうかを考えていました。私は時間に制限されているため、事前に作成されたコードがあるかどうかを助けて提案してください。前もって感謝します。

次のグラフ演習を解決しようとしています。

無向加重グラフには、V 個の頂点と E 個のエッジがあります。0 とラベル付けされた頂点から開始して、T(T<=V) 頂点を訪問するために必要な最小の重みを見つけます。さらに、2 つの訪問された頂点間にエッジがある場合、その重みは 0 に設定されます。

これは、典型的な巡回セールスマンの問題ではありません。これは、2 つの頂点にアクセスすると、それらの間のエッジの重みが 0 になるという条件が追加されているためです。

Prim の最小スパニング ツリー アルゴリズムを使用してアプローチすると、T == V の場合に問題が解決しますが、必ずしもすべての頂点にアクセスする必要はないため、常に最小の重みが返されるとは限りません。

最小のスパニング ツリーを見つけて、すべての「ターゲット」頂点に到達する能力を妨げないすべてのエッジをカットすることを考えましたが、それは過度であり、おそらく正しくないようです。

何かご意見は？

編集：例を挙げます。0、1、2、および 3 のラベルが付いた 4 つの頂点を持つグラフがあるとします。次の辺 (from、to、weight) があります: (0,1,1) (0,2,2) (1,3,4) ) (2,3,1) 最小スパニング ツリーには、エッジ (0,1,1)、(0,2,2)、および (2,3,1) が含まれます。これを使用すると、すべての頂点に 0 から到達できます。ただし、演​​習の目標は、これらの頂点の T 個に到達することです。そうは言っても、たとえば、頂点 2 と 3 に到達するだけでよく、エッジ (0,1,1) は不要であり、したがって、ターゲット頂点に到達するために必要な合計ウェイトは 1 ではなく 2+1 になります。 +2+1。