Javaの最小スパニングツリーのためのBoruvkaのアルゴリズム

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

1. 概要

このチュートリアルでは、エッジ加重グラフの最小スパニングツリー（MST）を見つけるためのBoruvkaのアルゴリズムのJava実装を見ていきます。

これは、PrimのおよびKruskalのアルゴリズムよりも前のものですが、それでも2つの間のクロスと見なすことができます。

2. Boruvkaのアルゴリズム

手元のアルゴリズムに飛び込みます。少し歴史を見てから、アルゴリズム自体を見てみましょう。

2.1. 歴史

与えられたグラフのMSTを見つける方法は、1926年に OtakarBoruvkaによって最初に策定されました。これは、コンピューターが存在する前の方法であり、実際には、効率的な配電システムを設計するためにモデル化されました。

Georges Sollinは1965年にそれを再発見し、並列コンピューティングで使用しました。

2.2. アルゴリズム

アルゴリズムの中心的な考え方は、各頂点が孤立したツリーを表す一連のツリーから開始することです。次に、接続されたツリーが1つになるまで、エッジを追加して孤立したツリーの数を減らす必要があります。

グラフの例を使って、これを段階的に見てみましょう。

ステップ0：グラフを作成する
ステップ1：接続されていないツリーの束から開始します（ツリーの数=頂点の数）
ステップ2：接続されていないツリーがある間、接続されていないツリーごとに：
- より軽い重量でそのエッジを見つける
- このエッジを追加して、別のツリーを接続します

3. Javaの実装

次に、これをJavaで実装する方法を見てみましょう。

3.1. UnionFindデータ構造

まず、頂点の親とランクを格納するためのデータ構造が必要です。

この目的のために、unionとfindの2つのメソッドを使用して、クラスUnionFindを定義しましょう。

public class UnionFind {
    private int[] parents;
    private int[] ranks;

    public UnionFind(int n) {
        parents = new int[n];
        ranks = new int[n];
        for (int i = 0; i < n; i++) {
            parents[i] = i;
            ranks[i] = 0;
        }
    }

    public int find(int u) {
        while (u != parents[u]) {
            u = parents[u];
        }
        return u;
    }

    public void union(int u, int v) {
        int uParent = find(u);
        int vParent = find(v);
        if (uParent == vParent) {
            return;
        }

        if (ranks[uParent] < ranks[vParent]) { 
            parents[uParent] = vParent; 
        } else if (ranks[uParent] > ranks[vParent]) {
            parents[vParent] = uParent;
        } else {
            parents[vParent] = uParent;
            ranks[uParent]++;
        }
    }
}

このクラスは、頂点間の関係を維持し、MSTを徐々に構築するためのヘルパー構造と考えることができます。

2つの頂点uとvが同じツリーに属しているかどうかを調べるために、find（u）がfind（v）と同じ親を返すかどうかを確認します。 union メソッドは、ツリーを結合するために使用されます。この使用法はまもなくわかります。

3.2. ユーザーからグラフを入力する

次に、ユーザーからグラフの頂点とエッジを取得し、実行時にアルゴリズムで使用できるオブジェクトにマップする方法が必要です。

JUnitを使用してアルゴリズムをテストするため、この部分は@Beforeメソッドで実行されます。

@Before
public void setup() {
    graph = ValueGraphBuilder.undirected().build();
    graph.putEdgeValue(0, 1, 8);
    graph.putEdgeValue(0, 2, 5);
    graph.putEdgeValue(1, 2, 9);
    graph.putEdgeValue(1, 3, 11);
    graph.putEdgeValue(2, 3, 15);
    graph.putEdgeValue(2, 4, 10);
    graph.putEdgeValue(3, 4, 7);
}

ここでは、グアバを使用しました MutableValueGraph グラフを保存します。次に、 ValueGraphBuilder を使用して、無向の重み付きグラフを作成しました。

メソッドputEdgeValueは、 MutableValueGraph で指定されているように、頂点に2つの Integer 、重みに3番目のIntegerの3つの引数を取ります。の総称型宣言。

ご覧のとおり、これは前の図に示したものと同じ入力です。

3.3. 最小スパニングツリーを導出する

最後に、問題の核心であるアルゴリズムの実装について説明します。

これは、BoruvkaMSTというクラスで行います。まず、いくつかのインスタンス変数を宣言しましょう。

public class BoruvkaMST {
    private static MutableValueGraph<Integer, Integer> mst = ValueGraphBuilder.undirected().build();
    private static int totalWeight;
}

ご覧のとおり、 MutableValueGraph ここではMSTを表します。

次に、すべての魔法が発生するコンストラクターを定義します。これには1つの引数が必要です。以前に作成したgraphです。

最初に行うことは、入力グラフの頂点のUnionFindを初期化することです。最初は、すべての頂点がそれぞれの親であり、それぞれのランクは0です。

public BoruvkaMST(MutableValueGraph<Integer, Integer> graph) {
    int size = graph.nodes().size();
    UnionFind uf = new UnionFind(size);

次に、MSTの作成に必要な反復回数を定義するループを作成します。最大でlog V回、またはV-1エッジが得られるまで、Vは頂点の数です。

for (int t = 1; t < size && mst.edges().size() < size - 1; t = t + t) {
    EndpointPair<Integer>[] closestEdgeArray = new EndpointPair[size];

ここでは、エッジの配列 closestEdgeArray – も初期化して、最も近く、重みの少ないエッジを格納します。

その後、内側の for ループを定義して、グラフのすべてのエッジを反復処理し、closestEdgeArrayにデータを入力します。

2つの頂点の親が同じである場合、それは同じツリーであり、配列に追加しません。それ以外の場合は、現在のエッジの重みをその親頂点のエッジの重みと比較します。それより少ない場合は、 closestEdgeArray：に追加します

for (EndpointPair<Integer> edge : graph.edges()) {
    int u = edge.nodeU();
    int v = edge.nodeV();
    int uParent = uf.find(u);
    int vParent = uf.find(v);
    
    if (uParent == vParent) {
        continue;
    }

    int weight = graph.edgeValueOrDefault(u, v, 0);

    if (closestEdgeArray[uParent] == null) {
        closestEdgeArray[uParent] = edge;
    }
    if (closestEdgeArray[vParent] == null) {
        closestEdgeArray[vParent] = edge;
    }

    int uParentWeight = graph.edgeValueOrDefault(closestEdgeArray[uParent].nodeU(),
      closestEdgeArray[uParent].nodeV(), 0);
    int vParentWeight = graph.edgeValueOrDefault(closestEdgeArray[vParent].nodeU(),
      closestEdgeArray[vParent].nodeV(), 0);

    if (weight < uParentWeight) {
        closestEdgeArray[uParent] = edge;
    }
    if (weight < vParentWeight) {
        closestEdgeArray[vParent] = edge;
    }
}

次に、ツリーを作成するための2番目の内部ループを定義します。同じエッジを2回追加せずに、上記の手順のエッジをこのツリーに追加します。さらに、UnionFindでunionを実行して、新しく作成された木の頂点の親とランクを導出して保存します。

for (int i = 0; i < size; i++) {
    EndpointPair<Integer> edge = closestEdgeArray[i];
    if (edge != null) {
        int u = edge.nodeU();
        int v = edge.nodeV();
        int weight = graph.edgeValueOrDefault(u, v, 0);
        if (uf.find(u) != uf.find(v)) {
            mst.putEdgeValue(u, v, weight);
            totalWeight += weight;
            uf.union(u, v);
        }
    }
}

これらの手順を最大でlogV回繰り返した後、またはV-1エッジが得られるまで、結果のツリーはMSTになります。

4. テスト

最後に、実装を検証するための簡単なJUnitを見てみましょう。

@Test
public void givenInputGraph_whenBoruvkaPerformed_thenMinimumSpanningTree() {
   
    BoruvkaMST boruvkaMST = new BoruvkaMST(graph);
    MutableValueGraph<Integer, Integer> mst = boruvkaMST.getMST();

    assertEquals(30, boruvkaMST.getTotalWeight());
    assertEquals(4, mst.getEdgeCount());
}

ご覧のとおり、図の例と同じように、重みが30と4のエッジを持つMSTを取得しました。

5. 結論

このチュートリアルでは、BoruvkaアルゴリズムのJava実装を見ました。 その時間計算量はO（E log V）です。ここで、Eはエッジの数、Vは頂点の数です。

いつものように、ソースコードはGitHubで入手できます。

getdocs

13036