Java実装によるプリムのアルゴリズム

投稿日: 2022-10-24 2022-10-24
タグ: Algorithms, Java

1. 序章

このチュートリアルでは、最初に最小全域木とは何かを学びます。その後、Primのアルゴリズムを使用して1つを見つけます。

2. 最小スパニングツリー

最小スパニングツリー（MST）は、重み付きの無向接続グラフであり、重いエッジを削除することでエッジの総重みが最小化されています。つまり、グラフのすべての頂点をそのまま保持しますが、すべてのエッジの合計が最小になるように、いくつかのエッジを削除する場合があります。

エッジに重みがまったくない場合、エッジの合計の重みを最小化することは意味がないため、重み付きグラフから始めます。グラフの例を見てみましょう。

上記のグラフは、重み付けされた無向の連結グラフです。そのグラフのMSTは次のとおりです。

ただし、グラフのMSTは一意ではありません。グラフに複数のMSTがある場合、各MSTの合計エッジの重みは同じになります。

3. プリムのアルゴリズム

Primのアルゴリズムは、重み付けされた無向の連結グラフを入力として受け取り、そのグラフのMSTを出力として返します。

貪欲に動作します。最初のステップでは、任意の頂点を選択します。その後、新しいステップごとに、切断された頂点がなくなるまで、これまでに構築されたツリーに最も近い頂点が追加されます。

このグラフでプリムのアルゴリズムを段階的に実行してみましょう。

アルゴリズムを開始する任意の頂点がBであると仮定すると、A、C、およびEの3つの選択肢があります。エッジの対応する重みは2、2、および5であるため、最小値は2です。この場合、2つのエッジの重さが2あるので、どちらかを選択できます（どちらを選択してもかまいません）。 Aを選びましょう：

これで、2つの頂点AとBを持つツリーができました。追加されていない頂点につながる、まだ追加されていないAまたはBのエッジのいずれかを選択できます。したがって、AC、BC、またはBEを選択できます。

プリムのアルゴリズムは、最小値である2、つまりBCを選択します。

これで、前進する3つの頂点と3つの可能なエッジ（CD、CE、またはBE）を持つツリーができました。 ACはツリーに新しい頂点を追加しないため、含まれていません。これら3つの中で最小の重みは1です。

ただし、両方とも1の重さの2つのエッジがあります。したがって、プリムのアルゴリズムは、このステップでそれらの1つを選択します（これもどちらでも構いません）。

結合する頂点は1つだけなので、CEとBEから選択できます。ツリーをツリーに接続できる最小の重みは1であり、Primのアルゴリズムがそれを選択します。

入力グラフのすべての頂点が出力ツリーに存在するようになると、Primのアルゴリズムは終了します。したがって、このツリーは入力グラフのMSTです。

4. 実装

頂点とエッジはグラフを作成するため、これらの要素を格納するためのデータ構造が必要です。クラスEdgeを作成しましょう。

public class Edge {

    private int weight;
    private boolean isIncluded = false;

}

Primのアルゴリズムは重み付きグラフで機能するため、各Edgeには重みが必要です。 isIncluded は、Edgeが最小スパニングツリーに存在するかどうかを示します。

それでは、Vertexクラスを追加しましょう。

public class Vertex {

    private String label = null;
    private Map<Vertex, Edge> edges = new HashMap<>();
    private boolean isVisited = false;

}

各Vertexは、オプションでlabelを持つことができます。 edges マップを使用して、頂点間の接続を保存します。最後に、 isVisited は、頂点がプリムのアルゴリズムによってこれまでに訪問されたかどうかを示します。

ロジックを実装するPrimクラスを作成しましょう。

public class Prim {

    private List<Vertex> graph;

}

頂点のリストは、グラフ全体を格納するのに十分です。 バーテックス 、私たちは地図すべての接続を識別します。 Prime内で、 run（）メソッドを作成します。

public void run() {
    if (graph.size() > 0) {
        graph.get(0).setVisited(true);
    }
    while (isDisconnected()) {
        Edge nextMinimum = new Edge(Integer.MAX_VALUE);
        Vertex nextVertex = graph.get(0);
        for (Vertex vertex : graph) {
            if (vertex.isVisited()) {
                Pair<Vertex, Edge> candidate = vertex.nextMinimum();
                if (candidate.getValue().getWeight() < nextMinimum.getWeight()) {
                    nextMinimum = candidate.getValue();
                    nextVertex = candidate.getKey();
                }
            }
        }
        nextMinimum.setIncluded(true);
        nextVertex.setVisited(true);
    }
}

まず、の最初の要素を設定しますリストグラフ訪問したように。最初の要素は、最初にリストに追加された順序に応じて、任意の頂点にすることができます。 isDisconnected（）は、これまでにアクセスされていない Vertex がある場合、trueを返します。

private boolean isDisconnected() {
    for (Vertex vertex : graph) {
        if (!vertex.isVisited()) {
            return true;
        }
    }
    return false;
}

最小スパニングツリーisDisconnected（）で、すでにアクセスした頂点をループし、 nextVertex：の候補として最小の重みを持つEdgeを見つけます。

public Pair<Vertex, Edge> nextMinimum() {
    Edge nextMinimum = new Edge(Integer.MAX_VALUE);
    Vertex nextVertex = this;
    Iterator<Map.Entry<Vertex,Edge>> it = edges.entrySet()
        .iterator();
    while (it.hasNext()) {
        Map.Entry<Vertex,Edge> pair = it.next();
        if (!pair.getKey().isVisited()) {
            if (!pair.getValue().isIncluded()) {
                if (pair.getValue().getWeight() < nextMinimum.getWeight()) {
                    nextMinimum = pair.getValue();
                    nextVertex = pair.getKey();
                }
            }
        }
    }
    return new Pair<>(nextVertex, nextMinimum);
}

メインループ内のすべての候補の最小値を見つけて、nextVertexに保存します。次に、nextVertexをvisitedとして設定します。ループは、すべての頂点にアクセスするまで続きます。

最後に、trueに等しいisIncludedを持つ各エッジが存在します。

nextMinimum（）はエッジを反復処理するため、この実装の時間計算量は O（V2）であることに注意してください。代わりに、エッジを優先キュー（重みでソート）に格納すると、アルゴリズムは O（E log V）で実行されます。

5. テスト

さて、コードができたので、実際の例でテストしてみましょう。まず、グラフを作成します。

public static List<Vertex> createGraph() {
    List<Vertex> graph = new ArrayList<>();
    Vertex a = new Vertex("A");
    ...
    Vertex e = new Vertex("E");
    Edge ab = new Edge(2);
    a.addEdge(b, ab);
    b.addEdge(a, ab);
    ...
    Edge ce = new Edge(1);
    c.addEdge(e, ce);
    e.addEdge(c, ce);
    graph.add(a);
    ...
    graph.add(e);
    return graph;
}

Prime クラスのコンストラクターはそれを受け取り、クラス内に格納します。 originalGraphToString（）メソッドを使用して入力グラフを印刷できます。

Prim prim = new Prim(createGraph());
System.out.println(prim.originalGraphToString());

この例では、次のように出力します。

A --- 2 --- B
A --- 3 --- C
B --- 5 --- E
B --- 2 --- C
C --- 1 --- E
C --- 1 --- D

ここで、Primのアルゴリズムを実行し、 minimumSpanningTreeToString（）メソッドを使用して結果のMSTを出力します。

prim.run();
prim.resetPrintHistory();
System.out.println(prim.minimumSpanningTreeToString());

最後に、MSTを印刷します。

A --- 2 --- B
B --- 2 --- C
C --- 1 --- E
C --- 1 --- D

6. 結論

この記事では、プリムのアルゴリズムがグラフの最小全域木を見つける方法を学びました。コードはGitHubでから入手できます。

getdocs

13036