java - 隣接行列からの最小スパニング ツリー

Question

私には本当に苦労している問題があります。重み付けされたエッジを持つポイントのセットがあり、必要なエッジの最短量を見つけるために最小スパニング ツリーを作成する必要があります。私はJavaでそれを行う必要があります。現在、隣接行列を作成していますが、それが問題です。次にどこに行けばいいのか本当にわかりません。どんな助けでも素晴らしいでしょう。

Answer 1

Kruskal と Prim のアルゴリズムを見てみましょう。実装と理解が非常に簡単なため、私は Prim が本当に好きです: http://en.wikipedia.org/wiki/Prim%27s_algorithm

あなたの質問について、次に何をしますか (Resumed Prim のアルゴリズム): ランダムな頂点を 1 つ選択し、コストが小さいエッジを取得し、それを MST に挿入します。MST にすべての頂点がない場合: MST のエッジからコストが小さいエッジを選択し、MST に挿入します。

Answer 2

最小スパニング ツリーを見つけようとしている場合、常に同じ数のエッジがあり、重みが異なるだけです。この問題を解決するために使用することをお勧めする方法は、Prim のアルゴリズムです。重み付けされた明確なエッジがある場合に最適です。他の誰かがその可能性について議論していますが、無向接続グラフで最小スパニング ツリーの問題を解決するために、ここで完全に説明します。

Prim's への最初のステップは、任意の頂点 V から開始し、それを "Discovered" と呼ばれる (現在) 空の頂点セットに追加することです。そこから、(隣接行列を使用して) V に隣接し、「発見済み」にない頂点に接続されている (発見済みセットを使用して) すべてのエッジを調べ、それらを最小ヒープ構造に追加します。ヒープを使用すると、最小エッジを取得して新しいツリー構造に追加できます。そのエッジのもう一方の端は、次の新しい開始頂点です。最小のスパニング ツリーが得られるまで、このプロセスを繰り返します。