0

クラスカルのアルゴリズムを Java で実装する必要があります。

エッジを重み順に並べる部分があるのですが、各木の集合を保存する構造を考えないといけないので少し迷います。

各セットがツリーを表すセットのベクトルを持つことを考えました。しかし、2 つのツリーを結合する必要がある場合、どうすればよいかわかりません。ベクターから両方の要素を削除し、結合された新しい要素を追加しますか?

それを簡単にする構造はありますか？

私が必要とするのは：

  • 主要なセットからすべてのセットを反復する
  • セットの 1 つに要素を追加するか、または
  • 新しいセットを作成してメジャー セットに追加する
  • それらのセットの 2 つを結合します (もちろん、それらの特異なバージョンを削除します)
4

1 に答える 1

1

質問でリンクしたウィキペディアの記事で参照されている素集合のデータ構造は、必要な構造のタイプです。実装にクラスがあり、接続されたコンポーネントを形成する一連の頂点を表すためにVertexを使用して、Java で「単純なアプローチ」がどのように見えるかの例を示します。ArrayList<Vertex>

Vertexクラスを次のように変更します

public class Vertex {

    // other data members
    private ArrayList<Vertex> component;

    public Vertex(/* arguments */) {
        // other initialization
        component = new ArrayList<>();
        component.add(this);
    }

    // other methods

    public ArrayList<Vertex> getComponent() {
        return component;
    }

    public void setComponent(ArrayList<Vertex> updatedComponent) {
        component = updatedComponent;
    }
}

これは、コンストラクターが新しいコンポーネントの作成と独自のコンポーネントへの頂点の追加を処理するため、要素をセットに追加するアルゴリズムの部分を既に満たしています。

2 つの頂点uとvが同じコンポーネント内にあるかどうかを確認するには、次を使用します。

if (u.getComponent() == v.getComponent()) {
    // they are in the same component
} else {
    // the components are different
}

とが同じコンポーネントにない場合はu、v次のようなコードでコンポーネントを結合できます。

ArrayList<Vertex> larger;
ArrayList<Vertex> smaller;
if (u.getComponent().size() < v.getComponent().size()) {
    larger = v.getComponent();
    smaller = u.getComponent();
} else {
    larger = u.getComponent();
    smaller = v.getComponent();
}
for (Vertex aVtx : smaller) {
    aVtx.setComponent(larger);
}
larger.addAll(smaller);

Kruskal のアルゴリズムを正しく実装するために本当に必要なのはこれだけだと思いますが、主要なセットに関するコメントにはまだ対応していません。アルゴリズムの任意の時点でコンポーネントがどのように見えるかを確認できるように、すべてのコンポーネントを追跡したい場合は、HashSet<ArrayList<Vertex>> majorSet. 各頂点を作成すると、コンポーネントを に追加できます。また、2 つのコンポーネントを結合すると、からmajorSet削除できます。標準的な方法で繰り返すことができます。smallermajorSetmajorSet.values()

于 2015-09-26T05:32:17.373 に答える