Kruskal のアルゴリズムを実装する Java コード

Kruskal アルゴリズム

Kruskal アルゴリズムは、最小スパニング ツリー問題を解決するために使用される貪欲なアルゴリズムです。最小スパニング ツリーは、接続された無向グラフ内のエッジの重みの合計が最小のスパニング ツリーです。クラスカルのアルゴリズムは、エッジの重みが小さいものから順にエッジを選択し、選択されたエッジがサイクルを形成しない場合はスパニング ツリーに追加します。具体的な実装プロセスは次のとおりです。

• すべてのエッジをエッジの重みに従って小さいものから大きいものに並べ替えます。

• エッジを順番に選択します。選択したエッジの 2 つの端点が同じ接続コンポーネント内にない場合は、このエッジを最小スパニング ツリーに追加し、2 つの端点を同じ接続コンポーネントにマージします。成分。

• 最小スパニング ツリーにグラフ内のすべての頂点が含まれるまで。

このアルゴリズムの利点は、エッジの重みのみに注意を払う必要があり、頂点の次数とは関係がないため、より優れたパフォーマンスを発揮できることです。密なグラフで。同時に、Kruskal のアルゴリズムは優れたスケーラビリティも備えており、重み付きグラフでの最小スパニング フォレスト問題を簡単に処理できます。

実行プロセス

• すべてのエッジを重みに従って小さいものから大きいものに並べ替えます。

• 各エッジを順番に走査します。 , このエッジによって接続されている 2 つのノードが同じ接続コンポーネント内にない場合は、このエッジをスパニング ツリーに追加し、2 つのノードを 1 つの接続コンポーネントにマージします。

• ステップ 2 を繰り返します。すべてのノードが同じ接続コンポーネント内にある場合、この時点で生成されるツリーが最小スパニング ツリーになります。

実装プロセスでは、通常、union-find セットを使用して接続を維持し、効率を向上させます。

コードの実装

import java.util.*;

public class KruskalAlgorithm {
    
    // 定义边的数据结构
    class Edge implements Comparable<Edge> {
        int src, dest, weight;
 
        public int compareTo(Edge edge) {
            return this.weight - edge.weight;
        }
    }
    
    // 并查集数据结构
    class Subset {
        int parent, rank;
    }
 
    int V, E; // V是顶点数，E是边数
    Edge edge[]; // 存储边的数组
 
    // 构造函数，初始化边和顶点数
    KruskalAlgorithm(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }
 
    // 查找父节点
    int find(Subset subsets[], int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
        return subsets[i].parent;
    }
 
    // 合并两个子集
    void union(Subset subsets[], int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);
 
        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }
 
    // 执行克鲁斯卡尔算法
    void kruskal() {
        Edge result[] = new Edge[V]; // 存储结果的数组
        int e = 0; // 表示result数组中的下标
 
        // 将边按照权重从小到大排序
        Arrays.sort(edge);
 
        // 创建V个子集
        Subset subsets[] = new Subset[V];
        for (int i = 0; i < V; ++i)
            subsets[i] = new Subset();
 
        // 初始化每个子集的父节点和秩
        for (int v = 0; v < V; ++v) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }
 
        // 取E-1条边
        int i = 0;
        while (e < V - 1) {
            Edge next_edge = new Edge();
            next_edge = edge[i++];
 
            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);
 
            // 如果两个节点不在同一个集合中，合并它们
            if (x != y) {
                result[e++] = next_edge;
                union(subsets, x, y);
            }
        }
 
        // 打印结果
        System.out.println("Following are the edges in the constructed MST");
        for (i = 0; i < e; ++i){
            System.out.println(result[i].src + " - " + result[i" - " + result[i].weight);
            return;
        }
        
        // 定义一个辅助函数，用于查找结点所在的集合 
        private int find(int parent[], int i) { 
            if (parent[i] == -1) 
                return i; 
            return find(parent, parent[i]); 
        }

        // 定义一个辅助函数，用于合并两个集合 
        private void union(int parent[], int x, int y) { 
            int xset = find(parent, x); 
            int yset = find(parent, y); 
            parent[xset] = yset; 
        } 
    }
}

この関数は、Arrays クラスの sort メソッドを使用して、重みに従ってエッジを小さいものから大きいものへと並べ替えます。次に、関数はソートされたエッジを順番に走査し、エッジごとに find 関数を使用して、その src と dest が配置されているセットのルート ノードを見つけます。ルート ノードが異なる場合は、2 つのセットが接続されていないためマージでき、エッジが最小スパニング ツリーの結果配列に追加されることを意味します。最後に、関数は最小スパニング ツリーの結果配列を走査し、各エッジの開始点、終了点、および重みを出力します。

この実装では、集合を迅速に検索する方法、つまり和集合検索を使用してそれを実現します。各ノードには親配列があり、parent[i] はノード i の親ノードを表します。parent[i] == -1 の場合、ノード i はルート ノードです。ノードが配置されているセットを検索する場合、現在のノードの親ノードが -1 の場合、そのノードはルート ノードであることを意味し、直接返されます。それ以外の場合は、親ノードが配置されているセットが再帰的に検索されます。 。 2 つのコレクションをマージする場合は、マージする 2 つのコレクションのルート ノードを見つけて、一方のルート ノードの親ノードをもう一方のルート ノードのインデックスに設定します。つまり、一方のコレクションのルート ノードを、コレクションのルート ノードの下にマージします。他のコレクションです。

この方法で実装されたクラスカルのアルゴリズムの時間計算量は O(ElogE) で、E はグラフ内のエッジの数を表します。主な時間コストはエッジをソートするプロセスにあります。空間の複雑さは O(V E) で、V はグラフ内の頂点の数を表します。空間の主なオーバーヘッドは、エッジと親配列を格納することです。

以上がKruskal のアルゴリズムを実装する Java コードの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。