問題タブ [prims-algorithm]

「したがって、プリムのアルゴリズムの合計時間は O(V lg V + E lg V) = O(E lg V) であり、これはクラスカルのアルゴリズムの実装と漸近的に同じです。」

http://serverbob.3x.ro/IA/DDU0137.htmlより

しかし、なぜ O(V lg V + E lg V) = O(E lg V) なのですか??

E が少なくとも V-1 だからですか?

プログラミングの宿題として、Prim のアルゴリズムを実装しています。テスト ケースの入力ファイルの形式は次のとおりです。

入力の最初の行は、テスト ケースの数を示す整数 C になります。各テスト ケースの最初の行には、2 つの整数 N と E が含まれます。ここで、N はグラフ内のノードの数を表し、E はエッジの数をそれぞれ表します。次に、それぞれ 3 つの整数 I、J、P を持つ E 行が続きます。ここで、I と J はエッジのノードを表します (無向グラフ、0 ≤ I、J

私はコードを始めていますが (プログラミングは初めてです)、コードがテストケースのエントリしか読み取らない理由がわかりません。何が間違っていますか?

これは、ファイル entradaA.in を読み取るコードです。

入力ファイル (entradaA.in) は次のようになります。

私の質問が話すように、プリムのアルゴリズムで優先キューを使用する理由を知りたいですか? 単純な方法を使用することからどのように私たちを救うのですか (はい、聞いたことがありますが、理由はわかりません)。

adjacency list について順を追って説明できる人がいれば、とてもうれしいです。コーメンの本を使用しています。

疑似コード:

std::vector を使用してから std::make_heap(); を使用することを考えています。エッジを格納するための優先キューとして。

誰かが2つのアルゴリズムのいくつかのアプリケーション、それらを使用できる場所とアプリケーションを教えてもらえますか？

すべてのグラフ ポイントを含むファイルを使用して、boost ライブラリのprim_minimum_spanning_tree関数でPrim アルゴリズムを使用しようとしています。boost ライブラリのkruskal_minimum_spanning_tree関数を使用して、目的のグラフを作成することに成功しました。

しかし、prim_minimum_spanning_treeを使用すると、各ポイントの直接の親しか得られないため、グラフは完全ではありません。

ブーストのドキュメントに記載されている例を使用しました:

プリムの場合: http://www.boost.org/doc/libs/1_47_0/libs/graph/example/prim-example.cpp

そしてクルスカルのものhttp://www.boost.org/doc/libs/1_47_0/libs/graph/example/kruskal-example.cpp

具体的な例:私はこのポイントのファイルを持っています:

私が得るクルカル関数で：

私が得るプリム関数で：

私はそれらのグラフの描画を持っていますが、画像やいくつかのリンクを投稿することはできません. しかし、ご覧のとおり、3 つのリンクがありません。

prim 関数を使用して kruskal と同じ結果を得るにはどうすればよいですか?

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

PS：私は例のコードをベースとして使用し、成功せずに一連の変更を試みました.Webまたはドキュメントで有用な情報を見つけることができませんでした.

プリムのアルゴリズムを変更して、接続されていないグラフを処理する方法を知っている人はいますか? フォレストを使用する必要があることはわかっていますが、Haskell でそれを実装する方法がわかりません..

最近、MS Prism を使用して新しいプロジェクトを開始しました。私のUIモジュールの1つに、アプリケーションリソースディクショナリに追加する必要があるリソースファイルがあります..だから私はそれを行うためにこのコードを書きました:

私のリソース ファイルには、次のような Datatemplate のセッターがあります。

問題は、リソース ファイルの読み込み時に「'System.Windows.Setter' の初期化で例外がスローされました」というメッセージがスローされることです。しかし、このセッターを削除すると、正常に動作します。何か案が？

javascriptでランダムな迷路ジェネレーターを作成しようとしています。

すでに実用的な例があるかもしれませんが、私はこれを自分で解決しようとしています（まあ、可能な限り）

私が抱えている問題は、スクリプトが数ブロックだけ実行されてから停止することです。

問題は、私がフォローしている説明を理解していることにあると思います（このウィキペディアのページhttp://en.wikipedia.org/wiki/Maze_generation_algorithmから）

このアルゴリズムは、プリムのアルゴリズムのランダム化されたバージョンです。

1. 壁でいっぱいのグリッドから始めます。

2. セルを選択し、迷路の一部としてマークします。セルの壁を壁リストに追加します。

3. リストに壁がありますが：

   1. リストからランダムな壁を選びます。反対側のセルがまだ迷路に入っていない場合：

      1. 壁を通路にし、迷路の一部として反対側のセルに印を付けます。

      2. セルの隣接する壁を壁リストに追加します。

   2. 反対側のセルがすでに迷路に入っている場合は、リストから壁を削除します。

私がハイライトしたように、私の問題はこれの反対側の 部分にあります。これは、ウォールリストにある隣接セルを意味しますか？それとも何か他の意味ですか？

隣接するセルで試してみましたが、でブロックされてしまいます。

任意のアイデアをいただければ幸いです。

動作させることができれば、完了したらコードを投稿します。私が言ったように、私は完全な解決策の助けを得る前に自分で遠くまで行きたいと思っています。

JAVA の MST アルゴリズムに問題がありますか?

JavaでMSTのコードを書こうとしています

ここで、グラフは既に与えられており、ノード (パス上ではない) を追加する addCheapest メソッドを記述しようとしています。これは、パスに追加されると、ある位置で、グラフ内のすべてのノードとすべての位置のパスの結果のコストを最小化します。それらは追加できます。その位置に追加します。

}*