隣接リストがPRIMSアルゴリズムを使用した文字列配列にある隣接リストから最小スパニングツリーを見つける

Question

だから私は最低スパニングツリーを見つける方法を育てるための助けが必要です。 隣接リストの形でグラフがあるとします。

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

.

最初の文字はあなたがどのノードを見ているのかを知らせ、その数は他のノードへの接続数を伝えます。たとえば、Aは2つの接続を持っています - それぞれBとIには、文字に続く数字は単にエッジの重みを伝えます。Bは体重12を持ち、私は体重25を持っています。 Graph[8]と呼ばれます。各行は配列内の異なるスロットになります。私は、PrimsまたはKruskallsアルゴリズムのいずれかでこれを達成する方法を考え出すことが困難です。

Answer 1

隣接リストの形で木があるとします

この種の隣接リストに接続されているグラフがあることに注意することが重要ですが、それが字型であると思います。私はこれを編集として提案しますが、私はあなたがそれを知っておくことを望みます。 それがグラフであり、ツリーではなくグラフであるという事実：

A 2 B 12 I 25
B 3 C 10 H 40 I 8

.

ここではすでにa-b-i：にある円があります

     A
  12/_\25
   B 8 I

.

定義によって円を持つことはそれが木になることができないことを意味します！ このサブグラフを提示する方法から見ることができるもう1つのことがあります。 エッジにはノードではなく重み付けがあります。

---

今すぐあなたの提供された例を見てみましょう：

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

.

まず、この隣接リストが誤っているか、必要に応じて最適化されていることがわかります。これは、（例えば）線から見られます。

E 2 F 60 G 38
F 0

.

ここでの最初の行はEからFまでのエッジを示していますが、2行目はfは0の程度が0ですが、次数はITに入射するエッジによって定義されます！

これは、隣接リストが 'complete'であればどのように見えるか：

A 2 B 12 I 25
B 4 A 12 C 10 H 40 I 8
C 3 B 10 D 18 G 55
D 2 C 18 E 44
E 3 D 44 F 60 G 38
F 1 E 60
G 3 C 55 E 38 H 35
H 3 B 40 G 35 I 35

.

私たちはすべてのエッジが2回発生しているため、冗長性がたくさん表示されますが、このような「最適化された」隣接リストがあなたのニーズに合っている理由です - これは「完全な」の例になります。 ただし、コードに与えられたすべてのデータがすでに「最適化されている」（またはこの形式ではむしろ）であることを確認できる場合は、 one のみ依存してください。私は今から与えられたものとしてこれを取ります。

---

あなたのデータ構造について話しましょう。 あなたはもちろんあなたの提案された弦楽的な弦楽を使うかもしれませんが、正直に言うと、@amirafghaniの提案されたデータ構造のような何かをお勧めします。彼のアプローチを使用すると、（彼がすでに指摘したように - あなたの精神表現に近づくでしょう）、さらに効率的になるでしょう（私は推測に頼らないでください）。など、さまざまなの操作を行うように。 タイトルのタイトルでは、あなたがPrimのアルゴリズムの後に尋ねたが、あなたの実際の質問であなたはプリムまたはクルスカルのいずれかを言った。彼のアルゴリズムが簡単で、両方を受け入れるように思われるので、私はクルスカルと一緒に行きます。

---

クラスカルのアルゴリズム

クルスカルのアルゴリズムはかなり単純です、基本的には：

• すべてのノードから始めますが、エッジはありません

  できるだけ頻繁に以下を繰り返します。

  • 未使用/未使用のエッジのすべてから、重量が最も少ないものを選択します（複数の場合：そのうちの1つを選ぶ）
  • このエッジが円を引き起こすかどうかを確認し、それがそうであればそれをマークして '廃棄してください。
  • 円を引き起こさない場合は、それを使用して使用/選択されているとマークします。

    それはすべてです。それは本当にその単純です。 しかし、私はこの時点で一つのことを言及したいと思います、私はそれがここにぴったりフィットすると思います：一般的に「最小スパニングツリー」はありませんが、多くのことがあるように「最小スパニングツリー」はありません。

    ---

    データ構造に戻る！データ構造として文字列の配列を使用するのが悪い考えである理由がわかりました。 （たとえば、すべてのエッジの重さをチェックするなど）、文字列が不変の の文字列に関する多くの操作を繰り返すでしょう。どんな方法でエッジの1つをマークします。 別のアプローチを使用すると、重みを-1に設定することも、エッジのエントリを削除することもできます。

    ---

    深さ - 最初の検索

    私が見たことから、あなたの主な問題はエッジが円を引き起こすかどうかを決めると思いますか？ これを決定するためには、おそらく深さの最初の検索アルゴリズムを呼び出して戻り値を使用する必要があります。 基本的なアイデアはこれです：どちらのノードからの起動（私はこのノードをルートに呼びます）

そして、選択したエッジのもう一方の端にあるノードへの道を見つけるようにしてください（このノードはターゲットノードを呼び出されます）。（もちろんこのエッジがまだありません）

• root にインシデントされていない1つの未訪問のエッジを選択します。
• この選択されたエッジを訪問した（またはそのようなもの、あなたが好きなもの）
• 訪問先のエッジの反対側のノードの最後の2つの手順を繰り返します。
• 訪問されていないエッジがないときはいつでも、1つのエッジに戻る
• あなたがあなたのrootに戻って残っていないエッジが残っていないならば、あなたは完了です。falseを返します。
• 任意の時点でターゲットノードにアクセスした場合は、完了です。trueを返します。

  現在、このメソッドがtrueを返す場合、このエッジは円を引き起こします。

Answer 2

これはあなたの質問に対する直接的な答えではありません（あなたが学校をやっているようです）が、私はそれがあなたが始めるのを助けるのを助けるだろうと思います。 Mental Model をより厳密に一致させ、そこから蓄積するデータ構造を作成しないのはなぜですか？

class GraphNode { 

    final String name;
    final List<GraphEdge> adjacentNodes;

    public GraphNode(String name) { 
        this.name = name;
        adjacentNodes = new ArrayList<GraphEdge>();
    }

    public void addAdjacency(GraphNode node, int weight) { 
        adjacentNodes.add(new GraphEdge(node, weight));
    }

}

class GraphEdge {

    final GraphNode node;
    final int weight;

    public GraphEdge(GraphEdge node, int weight) {
        this.node = node;
        this.weight = weight;
    }

}

.