問題タブ [minimum-spanning-tree]

今日、このスライドの 13 ページのために、Kruskal 最小スパニング ツリー アルゴリズムについて誰かと議論しました。

プレゼンテーションの著者は、(二重) リンク リストを使用して素集合を実装すると、MakeとFindのパフォーマンスはそれぞれ O (1)とO(1 )になると述べています。Union(u,v)操作の時間はmin(nu,nv)です。ここで、nuとnvは u と v を格納するセットのサイズです。

セットの実表現へのポインターを含むロケーターを指す各メンバーの表現ポインターを作成することにより、 Union(u,v)がO(1)になる時間を改善できると述べました。

Java では、データ構造は次のようになります。

ミニマルなコードで申し訳ありません。この方法で作成できる場合、互いに素な集合操作 ( Make,Find,Union )ごとの実行時間はO(1)になります。しかし、私が話し合った人は改善を見ることができません。これについてあなたの意見を知りたいです。

また、さまざまな実装における Find/Union の最速のパフォーマンスは? 私はデータ構造の専門家ではありませんが、インターネットをざっと見てみると、これを行う一定時間のデータ構造やアルゴリズムがないことがわかりました。

Prim と Kruskal の両方のアルゴリズムを記述して、C++ または Java で最小全域木を見つけることができますが、O(mlogm) または O(mlogn) を使用して Haskell でそれらを実装する方法を知りたいです (純粋な関数型プログラムの方が優れています)。どうもありがとう。

スパニング ツリー T0 のエッジが最小スパニング ツリー T* に含まれている場合、これは T0 が最小スパニング ツリーでもあることを意味しますか?

現在、そうではないことを証明するために、いくつかのグラフを紙に描こうとしています。そうである場合は修正してください。そうでない場合は、例を見つけるのを手伝ってください。

前もって感謝します。

グラフの隣接行列から最小スパニング ツリーを取得する方法を理解するのを手伝ってください! 私はそれについて Java でコースワークを書いています。締め切りは 2010 年 12 月 16 日ですが、失敗するだろうと感じています。今、私のプログラムは次のことができます：

1. ノードを描画
2. エッジを描く
3. エッジの重みを使用して、図面の地下にグラフの隣接行列を生成します
4. ノードに接続された最小エッジを見つける
5. 他のいくつかのテスト/テスト済み機能があります

しかし、Java で Prim/Kruskal アルゴリズムを実現する方法がわかりません。Googleでいくつかの解決策を見つけようとしましたが、.objファイルを動作させる必要があるJavaアプレットしか見つけられず、実行できません。

グラフの隣接行列を生成して出力する単純なコンソール Java パターンを作成します。次のようなグラフの最小スパニング ツリーの隣接行列を返す関数を誰でも追加できますか。

どこ：

• グラフ - n で生成されたグラフ
• 頂点 (ノード) の量

前もって感謝します！

Prim のアルゴリズムと有向グラフの最短経路を計算する Bellman-Ford アルゴリズムを使用して、有向グラフで最小スパニング ツリーを見つける方法を学習するためのリソースを提案してください。

PRIM アルゴリズムを使用して MST を見つける方法を教えてください。MST のエッジを強調表示し、ノードが MST に追加される順序を書きます..ありがとう

重複の可能性:
すべての最小スパニング ツリーの実装

無向グラフのすべての最小全域木を効率的に見つけるにはどうすればよいですか?

正月ですが、スパニング ツリー アルゴリズムに関する私の問題はまだ解決できません。まだ写真を挿入できないので、環境を言葉で説明する必要があります。

36 ノードで、各ノードまでの距離は均等です。問題は、距離が偶数である場合、ID 1 (ルート) のノードから ID 36 の最後のノードにメッセージを渡す方法は問題ではないということです。距離が均等であるため、時間の節約、エネルギーの節約、またはメッセージはありません。アルゴリズムを保存しますか？誰かが私の質問を理解してくれることを願っています

編集:

1. 環境

   /li>

これが私の選択したスパニング ツリーです。ID 36 のノードは、30,24,18,12,6,5,4,3,2,1 (1 つはルート) を介して情報を送信し、ノード 1 は基地局に情報を送信します。コストがないため、ノード 36 からノード 1 に情報を送信するためにどのパスを選択しても、コストは変わらないため、実際には問題になりません。

1. 私のスパニングツリーアルゴリズム

   • 開始時には、ルートのみがマークされます。
   • ルートは検索メッセージをネイバーに送信します
   • ノードがマークされていない場合、他のノードから検索メッセージを受信すると、次のようになります。
   • それはそれ自体をマークします
   • IDが最も低いノードを「親」として選択し、他のノードには「非親」と返信します
   • ノードがすでにマークされている場合、「非親」と応答します
   • ノードがすでにマークされていて、親メッセージを受信した場合、送信者を子としてマークします

2. 画像を挿入する権限がないため、フローチャートをお見せできません。

3. 疑似コード (まだ行っていません)

4. 結論 - ここで私のアルゴリズムの長所と短所を書き留める必要がありますが、今のところ長所と短所は思いつきません。

いくつかのメトリック空間（たとえば、 Jaccard Distanceを装備）に多数のポイント（n> 10000）があります。メトリックをエッジの重みとして使用して、それらを最小スパニング ツリーで接続したいと考えています。

• ^{O(n 2} ) 時間未満で実行されるアルゴリズムはありますか?
• ^{そうでない場合、O(n 2} ) 平均時間未満で実行されるアルゴリズムはありますか (ランダム化を使用する可能性があります)?
• ^{そうでない場合、O(n 2} ) 時間未満で実行され、最小スパニング ツリーの適切な近似を与えるアルゴリズムはありますか?
• そうでない場合、そのようなアルゴリズムが存在できない理由はありますか?

前もって感謝します！

以下のポスターの編集: 最小スパニング ツリーを見つけるための従来のアルゴリズムは、ここでは機能しません。それらは実行時間に E ファクターを持っていますが、私の場合、完全なグラフを実際に考慮しているため、 E = n ^2です。また、49995000 を超える可能性のあるすべてのエッジを保存するのに十分なメモリがありません。

Vertex-Cover 問題 (VC、既知の Np-Complete 問題) の 2 近似アルゴリズムに関する質問を見たことがありますが、答えがわかりません。問題は次のとおりです。「スパニング ツリー」を使用して、頂点カバー問題の 2 近似アルゴリズムを見つけます。さて、VC に関しては既に多くの貪欲なアプローチが提示されていますが、「スパニング ツリー」を使用した特殊なアルゴリズムは挑戦的です。何か案が？