問題タブ [prims-algorithm]

私のプロジェクトは、Java を使用して最小スパニング ツリーを実装することです。プリムのアルゴリズムを使用してタスクを実行することを目指しています。

グラフの定義は G = (V, E) です。ここで、V はピンのセット、E はピンのペア間の可能な相互接続のセットであり、E の各エッジ (u,v) に対して重み w( u,v) u と v を接続するためのコストを指定します。

私の考えは、2 つのハッシュマップを使用することです。まず、ピンをキーとして、近隣のリストを値として持ちます。2 番目のハッシュマップは、エッジ (u,v) のリストをキーとして取得し、値はその重みになります。

グラフを保存する最良の方法は何だと思いますか?

クラスカルとプリムのアルゴリズムを使用して、指定された無向加重グラフの MST を見つけるプログラムを作成しようとしています。クラスカルのアルゴリズムをプログラムにうまく実装できましたが、プリムのアルゴリズムに問題があります。より正確に言えば、Prim 関数を実際に構築して、グラフ内のすべての頂点を反復処理する方法がわかりません。プログラムの実行中に IndexOutOfBoundsException エラーが発生します。私がこれまでに行ったことを他の人が理解するのにどれだけの情報が必要かはわかりませんが、役に立たない情報が多すぎないことを願っています.

これは私がこれまでに持っているものです:

、およびクラスGraphがあります。EdgeVertex

• 頂点クラスは、ほとんどの場合、頂点の名前 (番号) を含む単なる情報ストレージです。

• Edge クラスは、gets parameters を持つ新しい Edge を作成できます(Vertex start, Vertex end, int edgeWeight)。このクラスには、開始頂点、終了頂点、重みなどの通常の情報を返すメソッドがあります。

• Graph クラスは、テキスト ファイルからデータを読み取り、新しい Edge を ArrayList に追加します。テキスト ファイルには、グラフに含まれる頂点の数も示され、それも保存されます。

クラスにはGraph、MST を計算するはずの Prim() メソッドがあります。

メソッド findClosesNeighbour() は次のようになります。

ArrayList<Vertex> visitedArrayList<Edges> graph新しいグラフを作成するときに構築されます。

Visited() メソッドは、移動しようとしている Vertex が Visited ArrayList に含まれているかどうかを確認する単純なブール値チェックです。私は独立してテストしましたfindClosestNeighbour()が、動作しているように見えましたが、誰かが何か問題を見つけた場合は、そのフィードバックも歓迎します.

主に、私の問題は Prim() メソッドで実際にメインループを構築することにありますが、必要な追加情報があれば喜んで提供します。

ありがとうございました。

編集: Prim() メソッドを使用した私の思考の流れを明確にするため。私がやりたいことは、まずグラフの開始点をランダム化することです。その後、その開始点に最も近い隣人を見つけます。次に、これらの 2 つのポイントを接続するエッジを MST に追加し、後で確認するために頂点を訪問済みリストに追加して、グラフにループが形成されないようにします。

スローされるエラーは次のとおりです。

203行目: return neighbour.get(0);in findClosestNeighbour()

179行目: Edge e = findClosestNeighbour(startingVertex);in Prim()

ブーストのプリムのアルゴリズムを使用して、エッジの重みだけでなく、エッジの重みと ID 番号を使用して最小スパニング ツリーを見つけようとしています。

たとえば、両方のエッジの重みが 1 の場合、ID が比較され、どちらか小さい方が引き分けになります。

EdgeWeight クラスを作成し、これを行うために < および + 演算子をオーバーロードしてから、動作することを期待して edge_weight_t プロパティを int から EdgeWeight に変更しました。

「c:\program files (x86)\microsoft visual studio 10.0\vc\include\limits(92): error C2440: '' : cannot convert from 'int' to 'D' 1> No constructor could というエラーが表示されましたソース型を取るか、コンストラクターのオーバーロードの解決があいまいでした」

私はこれを正しい方法でやっていますか？これを行うより良い方法はありますか？

http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/prim_minimum_spanning_tree.html http://www.boost.org/doc/libs/1_38_0/boost/graph/prim_minimum_spanning_tree.hpp

編集：わかりましたので、今のところcjmの摂動法を使用して重みを実装しましたが、将来的には上記の方法を何らかの形で使用する必要があると思いますが、どうすればよいかまだ疑問に思っています

edit2: Jeremiah の応答に基づいて、vertex_distance_t を int から EdgeWeight に変更しましたが、同じエラーが発生しました

与えられた重みの最小値が既にわかっている場合、プリムのアルゴリズムをどのように変更できますか? たとえば、グラフがエッジの重み 0 と 1 で構成されている場合、プリムのアルゴリズムを高速化するにはどうすればよいでしょうか?

重みのある無向連結グラフが与えられます。w:E->{1,2,3,4,5,6,7} - 可能な重みは 7 つしかないことを意味します。O(n+m) の Prim のアルゴリズムと O( m*a(m,n)) の Kruskal のアルゴリズムを使用してスパニング ツリーを見つける必要があります。

これを行う方法がわかりません。ここでウェイトがどのように役立つかについてのガイダンスが本当に必要です.

プリム迷路生成アルゴリズムを実装しようとしています:

• 壁でいっぱいのグリッドから始めます。
• セルを選択し、迷路の一部としてマークします。セルの壁を壁リストに追加します。
• リストに壁がある場合:
  • リストからランダムな壁を選択します。反対側のセルが
    まだ迷路に入っていない場合:
    • 壁を通路にして、反対側のセルを迷路の一部としてマークします。
    • セルの隣接する壁を壁リストに追加します。
  • 反対側のセルが既に迷路内にある場合は、リストから壁を削除します。

いくつかの実装の詳細を削除すると、私の実装は次のようになります。

セルを含むマトリックスです。各セルには、左/右/上/ボタンの壁があります。とマークされたフロンティアの壁boolean frontierは実装の一部ではありません。迷路の枠を維持したいからです。

私の問題は、迷路が完成しておらず、すべてのセルが横断されていないことです。場合によっては、少数のセルのみが通過し、ほとんどすべてのセルが完了します。私は何かが欠けていると信じています。バーは何がわからないのですか。

助けてください。

部分横断迷路については、下の図を参照してください。

I am trying to create a C implementation of Prim's Algorithm using priority queues using the pseudocode which is similar to many sources online. The end goal is (hopefully) some nifty maze generation. I'm just having confusion with the details of the implementation.

input: An adjacency matrix with random weights

desired output: The adjacency matrix for a minimal spanning tree

*EDIT: Added my (not working) attempt. I'm still getting an incorrect tree, I'm not sure where I'm going wrong. I think I would benefit from another set of eyes over this code.

私は C で Prim MST を使用しており、関数は隣接行列を取ります。もちろんの重みを考えるとA[i][j]。

これまでに見つけた最小エッジを追跡する先行配列があるとします。 predecessor[u]=v{これも最後の MST です}

ここで、現在の行列を変更し、重みを 1 に変更したいと考えていA[i][j]ます。これは、先行配列にもエッジ (インデックス) が存在していたときです。それ以外の場合は、ゼロに変更します。

どうすればいいですか？これが私の解決策です：

私は教科書でこの質問に出くわしました：

「一般に、プリム、クラスカル、ダイクストラのアルゴリズムの時間計算量は何に依存していますか?」

a. グラフ内の頂点の数。
b. グラフ内のエッジの数。
c. 両方とも、グラフ内の頂点とエッジの数について。

あなたの選択を説明してください。

したがって、ウィキペディアのプリム、クラスカル、およびダイクストラのアルゴリズムによると、最悪の場合の時間の複雑さはO(ElogV)、それぞれO(ElogV)およびO(E+VlogV)です。答えはcだと思いますか？しかし、なぜ？

このグラフでアルゴリズム Prim を実行することで、グラフ G の最小スパニング ツリーを提供できるかどうか疑問に思っていました。

Prim アルゴリズムは、考えられるすべての MST を提供してくれますか?