Java実装を使用したスパニングツリーのためのクラスカルのアルゴリズム

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

1. 概要

前回の記事では、最小全域木を見つけるためのPrimのアルゴリズムを紹介しました。この記事では、別のアプローチであるクラスカルのアルゴリズムを使用して、最小および最大スパニングツリーの問題を解決します。

2. スパニングツリー

無向グラフのスパニングツリーは、可能な限り最小のエッジ数ですべてのグラフノードをカバーする接続されたサブグラフです。一般に、グラフには複数のスパニングツリーが含まれる場合があります。次の図は、スパニングツリーのグラフを示しています（スパニングツリーのエッジは赤で表示されています）。

グラフがエッジで重み付けされている場合、スパニングツリーの重みをそのすべてのエッジの重みの合計として定義できます。最小スパニングツリーは、可能なすべてのスパニングツリーの中で重みが最小のスパニングツリーです。次の図は、エッジ加重グラフの最小スパニングツリーを示しています。

同様に、最大スパニングツリーは、すべてのスパニングツリーの中で最大の重みを持ちます。次の図は、エッジ加重グラフの最大スパニングツリーを示しています。

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

グラフが与えられると、クラスカルのアルゴリズムを使用して最小全域木を見つけることができます。グラフ内のノードの数がVの場合、そのスパニングツリーのそれぞれに（V-1）エッジがあり、サイクルが含まれていない必要があります。クラスカルのアルゴリズムは、次の擬似コードで記述できます。

Initialize an empty edge set T. 
Sort all graph edges by the ascending order of their weight values. 
foreach edge in the sorted edge list
    Check whether it will create a cycle with the edges inside T.
    If the edge doesn't introduce any cycles, add it into T. 
    If T has (V-1) edges, exit the loop. 
return T

サンプルグラフの最小スパニングツリーに対してクラスカルのアルゴリズムを段階的に実行してみましょう。

まず、重みが最小であるエッジ（0、2）を選択します。次に、エッジ（3、4）と（0、1）を追加できます。これらは、サイクルを作成しないためです。次の候補は、重み9のエッジ（1、2）です。ただし、このエッジを含めると、サイクル（0、1、2）が生成されます。したがって、このエッジを破棄して、次に小さいエッジを選択し続けます。最後に、重み10のエッジ（2、4）を追加して、アルゴリズムを終了します。

最大スパニングツリーを計算するために、並べ替え順序を降順に変更できます。他の手順は同じままです。次の図は、サンプルグラフでの最大スパニングツリーの段階的な構築を示しています。

4. 互いに素なセットによる循環検出

クラスカルのアルゴリズムでは、重要な部分は、エッジを既存のエッジセットに追加した場合に、エッジがサイクルを作成するかどうかを確認することです。使用できるグラフサイクル検出アルゴリズムはいくつかあります。たとえば、深さ優先探索（DFS）アルゴリズムを使用してグラフを走査し、サイクルがあるかどうかを検出できます。

ただし、新しいエッジをテストするたびに、既存のエッジでサイクル検出を実行する必要があります。 より高速な解決策は、互いに素なデータ構造でUnion-Findアルゴリズムを使用することです。これは、インクリメンタルエッジ追加アプローチを使用してサイクルを検出するためです。これをスパニングツリー構築に適合させることができます処理する。

4.1. 素集合とスパニングツリーの構築

まず、グラフの各ノードを、1つのノードのみを含む個別のセットとして扱います。次に、エッジを導入するたびに、その2つのノードが同じセットにあるかどうかを確認します。答えが「はい」の場合、サイクルが作成されます。それ以外の場合は、2つの互いに素なセットを1つのセットにマージし、スパニングツリーのエッジを含めます。

スパニングツリー全体を構築するまで、上記の手順を繰り返すことができます。

たとえば、上記の最小スパニングツリーの構築では、最初に5つのノードセットがあります：{0}、{1}、{2}、{3}、{4}。最初のエッジ（0、2）をチェックすると、その2つのノードは異なるノードセットにあります。したがって、このエッジを含めて、{0}と{2}を1つのセット{0、2}にマージできます。

エッジ（3、4）と（0、1）に対して同様の操作を行うことができます。その後、ノードセットは{0、1、2}および{3、4}になります。次のエッジ（1、2）を確認すると、このエッジの両方のノードが同じセットにあることがわかります。したがって、このエッジを破棄して、次のエッジのチェックを続行します。最後に、エッジ（2、4）は条件を満たし、最小全域木に含めることができます。

4.2. 素集合の実装

ツリー構造を使用して、互いに素な集合を表すことができます。各ノードには、その親ノードを参照するためのparentポインターがあります。各セットには、このセットを表す一意のルートノードがあります。ルートノードには、自己参照親ポインターがあります。

Javaクラスを使用して、互いに素な集合情報を定義しましょう。

public class DisjointSetInfo {
    private Integer parentNode;
    DisjointSetInfo(Integer parent) {
        setParentNode(parent);
    }
 
    //standard setters and getters
}

各グラフノードに0から始まる整数のラベルを付けましょう。リストデータ構造を使用できますが、 リストノード 、グラフの互いに素な集合情報を格納します。最初は、各ノードはそれ自体のセットの代表的なメンバーです。

void initDisjointSets(int totalNodes) {
    nodes = new ArrayList<>(totalNodes);
    for (int i = 0; i < totalNodes; i++) {
        nodes.add(new DisjointSetInfo(i));
    }
}

4.3. 操作を見つける

ノードが属するセットを見つけるために、ルートノードに到達するまでノードの親チェーンを上向きにたどることができます。

Integer find(Integer node) {
    Integer parent = nodes.get(node).getParentNode();
    if (parent.equals(node)) {
        return node;
    } else {
        return find(parent);
    }
}

互いに素な集合に対して、非常に不均衡なツリー構造を持つ可能性があります。 パス圧縮技術を使用して検索操作を改善できます。

ルートノードに向かう途中でアクセスする各ノードは同じセットの一部であるため、ルートノードをその親参照に直接接続できます。次回このノードにアクセスするときは、ルートノードを取得するために1つのルックアップパスが必要です。

Integer pathCompressionFind(Integer node) {
    DisjointSetInfo setInfo = nodes.get(node);
    Integer parent = setInfo.getParentNode();
    if (parent.equals(node)) {
        return node;
    } else {
        Integer parentNode = find(parent);
        setInfo.setParentNode(parentNode);
        return parentNode;
    }
}

4.4. ユニオンオペレーション

エッジの2つのノードが異なるセットにある場合、これら2つのセットを1つに結合します。このunion操作は、一方の代表ノードのルートをもう一方の代表ノードに設定することで実現できます。

void union(Integer rootU, Integer rootV) {
    DisjointSetInfo setInfoU = nodes.get(rootU);
    setInfoU.setParentNode(rootV);
}

この単純な結合操作では、マージされたセットにランダムなルートノードを選択したため、非常に不均衡なツリーが生成される可能性があります。ランクテクニックによるユニオンを使用してパフォーマンスを向上させることができます。

find operation の実行時間に影響を与えるのはツリーの深さであるため、短いツリーのセットを長いツリーのセットにアタッチします。この手法は、元の2つのツリーの深さが同じである場合にのみ、マージされたツリーの深さを増やします。

これを実現するには、最初にランクプロパティをDisjointSetInfoクラスに追加します。

public class DisjointSetInfo {
    private Integer parentNode;
    private int rank;
    DisjointSetInfo(Integer parent) {
        setParentNode(parent);
        setRank(0);
    }
 
    //standard setters and getters
}

最初は、単一ノードの互いに素なランクは0です。 2つのセットの和集合の間、より高いランクのルートノードがマージされたセットのルートノードになります。元の2つのランクが同じである場合にのみ、新しいルートノードのランクを1つ増やします。

void unionByRank(int rootU, int rootV) {
    DisjointSetInfo setInfoU = nodes.get(rootU);
    DisjointSetInfo setInfoV = nodes.get(rootV);
    int rankU = setInfoU.getRank();
    int rankV = setInfoV.getRank();
    if (rankU < rankV) {
        setInfoU.setParentNode(rootV);
    } else {
        setInfoV.setParentNode(rootU);
        if (rankU == rankV) {
            setInfoU.setRank(rankU + 1);
        }
    }
}

4.5. サイクル検出

2つのfind操作の結果を比較することにより、2つのノードが同じ互いに素なセットにあるかどうかを判断できます。それらが同じ代表的なルートノードを持っている場合、サイクルを検出しました。それ以外の場合は、 union 操作を使用して、2つの互いに素なセットをマージします。

boolean detectCycle(Integer u, Integer v) {
    Integer rootU = pathCompressionFind(u);
    Integer rootV = pathCompressionFind(v);
    if (rootU.equals(rootV)) {
        return true;
    }
    unionByRank(rootU, rootV);
    return false;
}

ランク手法のみによるユニオンを使用した循環検出では、の実行時間はO（logV）です。 パス圧縮とユニオンのランク手法の両方を使用すると、パフォーマンスを向上させることができます。実行時間はO（α（V））です。ここで、α（V）はノードの総数の逆アッカーマン関数です。これは、実際の計算では5未満の小さな定数です。

5. クラスカルアルゴリズムのJava実装

GoogleGuavaのValueGraphデータ構造を使用して、エッジ加重グラフを表すことができます。

ValueGraph を使用するには、最初にプロジェクトのpom.xmlファイルにGuava依存関係を追加する必要があります。

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

上記のサイクル検出メソッドをCycleDetectorクラスにラップして、クラスカルのアルゴリズムで使用できます。最小スパニングツリー構築アルゴリズムと最大スパニングツリー構築アルゴリズムにはわずかな違いしかないため、1つの一般的な関数を使用して両方の構築を実現できます。

ValueGraph<Integer, Double> spanningTree(ValueGraph<Integer, Double> graph, boolean minSpanningTree) {
    Set<EndpointPair> edges = graph.edges();
    List<EndpointPair> edgeList = new ArrayList<>(edges);

    if (minSpanningTree) {
        edgeList.sort(Comparator.comparing(e -> graph.edgeValue(e).get()));
    } else {
        edgeList.sort(Collections.reverseOrder(Comparator.comparing(e -> graph.edgeValue(e).get())));
    }

    int totalNodes = graph.nodes().size();
    CycleDetector cycleDetector = new CycleDetector(totalNodes);
    int edgeCount = 0;

    MutableValueGraph<Integer, Double> spanningTree = ValueGraphBuilder.undirected().build();
    for (EndpointPair edge : edgeList) {
        if (cycleDetector.detectCycle(edge.nodeU(), edge.nodeV())) {
            continue;
        }
        spanningTree.putEdgeValue(edge.nodeU(), edge.nodeV(), graph.edgeValue(edge).get());
        edgeCount++;
        if (edgeCount == totalNodes - 1) {
            break;
        }
    }
    return spanningTree;
}

クラスカルのアルゴリズムでは、最初にすべてのグラフのエッジを重みで並べ替えます。この操作にはO（ElogE）の時間がかかります。ここで、Eはエッジの総数です。

次に、ループを使用して、ソートされたエッジリストを調べます。各反復で、現在のスパニングツリーエッジセットにエッジを追加することによってサイクルが形成されるかどうかを確認します。サイクル検出を伴うこのループは、最大で O（ElogV）時間かかります。

したがって、全体の実行時間は O（ELogE + ELogV）です。 Eの値はO（V2）のスケールであるため、クラスカルのアルゴリズムの時間計算量は O（ElogE）または O（ ElogV）。

6. 結論

この記事では、クラスカルのアルゴリズムを使用して、グラフの最小または最大スパニングツリーを見つける方法を学びました。いつものように、記事のソースコードはGitHubでから入手できます。

getdocs

13036