Javaを使用して最小スパニングツリーアルゴリズムを実装する方法

Java を使用して最小スパニング ツリー アルゴリズムを実装する方法

最小スパニング ツリー アルゴリズムは、グラフ理論の古典的な問題であり、重み付けされた最小値を解くために使用されます。接続されたグラフスパニングツリー。この記事では、Java 言語を使用してこのアルゴリズムを実装する方法を紹介し、具体的なコード例を示します。

1. 問題の説明
   各エッジに重みがある接続グラフ G が与えられた場合、T 内のすべてのエッジの重みの合計が次のような最小スパニング ツリー T を見つける必要があります。は最小です。
2. Prim アルゴリズム
   Prim アルゴリズムは、最小スパニング ツリー問題を解決するために使用される貪欲なアルゴリズムです。その基本的な考え方は、頂点から開始してスパニング ツリーを徐々に拡張し、すべての頂点がスパニング ツリーに追加されるまで、既存のスパニング ツリーに最も近い頂点を毎回選択することです。

以下は、Prim のアルゴリズムの Java 実装例です:

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

class Edge implements Comparable<Edge> {
    int from;
    int to;
    int weight;
    
    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

public class Prim {
    public static List<Edge> calculateMST(List<List<Edge>> graph) {
        int n = graph.size();
        boolean[] visited = new boolean[n];
        Queue<Edge> pq = new PriorityQueue<>();
        
        // Start from vertex 0
        int start = 0;
        visited[start] = true;
        for (Edge e : graph.get(start)) {
            pq.offer(e);
        }
        
        List<Edge> mst = new ArrayList<>();
        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            int from = e.from;
            int to = e.to;
            int weight = e.weight;
            
            if (visited[to]) {
                continue;
            }
            
            visited[to] = true;
            mst.add(e);
            
            for (Edge next : graph.get(to)) {
                if (!visited[next.to]) {
                    pq.offer(next);
                }
            }
        }
        
        return mst;
    }
}

3. Kruskal アルゴリズム
   Kruskal アルゴリズムは、最小スパニング ツリー問題を解決するために使用される貪欲なアルゴリズムでもあります。 。その基本的な考え方は、グラフ内のすべてのエッジを重みに従って小さいものから大きいものまで並べ替え、それらを順番にスパニング ツリーに追加することです。エッジを追加するとき、エッジの 2 つの端点が同じに属していない場合は、接続コンポーネントを作成すると、これらのエッジをスパニング ツリーに追加でき、2 つのエンドポイントが接続コンポーネントにマージされます。

以下は、Kruskal アルゴリズムの Java 実装例です:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Edge implements Comparable<Edge> {
    int from;
    int to;
    int weight;
    
    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

public class Kruskal {
    public static List<Edge> calculateMST(List<Edge> edges, int n) {
        List<Edge> mst = new ArrayList<>();
        Collections.sort(edges);
        
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        for (Edge e : edges) {
            int from = e.from;
            int to = e.to;
            int weight = e.weight;
            
            int parentFrom = findParent(from, parent);
            int parentTo = findParent(to, parent);
            
            if (parentFrom != parentTo) {
                mst.add(e);
                parent[parentFrom] = parentTo;
            }
        }
        
        return mst;
    }
    
    private static int findParent(int x, int[] parent) {
        if (x != parent[x]) {
            parent[x] = findParent(parent[x], parent);
        }
        
        return parent[x];
    }
}

4. 使用例
   以下は簡単な使用例です:

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<List<Edge>> graph = new ArrayList<>();
        graph.add(new ArrayList<>());
        graph.add(new ArrayList<>());
        graph.add(new ArrayList<>());
        graph.add(new ArrayList<>());
        
        graph.get(0).add(new Edge(0, 1, 2));
        graph.get(0).add(new Edge(0, 2, 3));
        graph.get(1).add(new Edge(1, 0, 2));
        graph.get(1).add(new Edge(1, 2, 1));
        graph.get(1).add(new Edge(1, 3, 5));
        graph.get(2).add(new Edge(2, 0, 3));
        graph.get(2).add(new Edge(2, 1, 1));
        graph.get(2).add(new Edge(2, 3, 4));
        graph.get(3).add(new Edge(3, 1, 5));
        graph.get(3).add(new Edge(3, 2, 4));
        
        List<Edge> mst = Prim.calculateMST(graph);
        System.out.println("Prim算法得到的最小生成树：");
        for (Edge e : mst) {
            System.out.println(e.from + " -> " + e.to + "，权重：" + e.weight);
        }
        
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 2));
        edges.add(new Edge(0, 2, 3));
        edges.add(new Edge(1, 2, 1));
        edges.add(new Edge(1, 3, 5));
        edges.add(new Edge(2, 3, 4));
        
        mst = Kruskal.calculateMST(edges, 4);
        System.out.println("Kruskal算法得到的最小生成树：");
        for (Edge e : mst) {
            System.out.println(e.from + " -> " + e.to + "，权重：" + e.weight);
        }
    }
}

上記のサンプル プログラムを実行すると、次の出力が得られます。

Prim算法得到的最小生成树：
0 -> 1，权重：2
1 -> 2，权重：1
2 -> 3，权重：4
Kruskal算法得到的最小生成树：
1 -> 2，权重：1
0 -> 1，权重：2
2 -> 3，权重：4

上記は、Java を使用して最小スパニング ツリー アルゴリズムを実装する具体的なコード例です。これらのサンプル コードを通じて、読者は最小スパニング ツリー アルゴリズムの実装プロセスと原理をより深く理解し学ぶことができます。この記事が読者のお役に立てば幸いです。

以上がJavaを使用して最小スパニングツリーアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。