Bagaimana untuk melaksanakan algoritma pokok rentang minimum menggunakan java

. Artikel ini akan memperkenalkan cara menggunakan bahasa Java untuk melaksanakan algoritma ini dan memberikan contoh kod khusus.

Huraian Masalah

Memandangkan graf bersambung G, di mana setiap tepi mempunyai pemberat, ia dikehendaki mencari pokok rentang minimum T supaya jumlah pemberat semua tepi dalam T adalah minimum.

Algoritma Prim

Algoritma Prim ialah algoritma tamak yang digunakan untuk menyelesaikan masalah pokok rentang minimum. Idea asasnya ialah bermula dari bucu dan kembangkan pokok rentang secara beransur-ansur, memilih bucu yang paling hampir dengan pokok rentang sedia ada setiap kali sehingga semua bucu ditambahkan pada pokok rentang.

1. 
   Berikut ialah contoh pelaksanaan Java bagi algoritma Prim:

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;
    }
}

2. 
   Algoritma Kruskal
Algoritma Kruskal juga merupakan algoritma tamak yang digunakan untuk menyelesaikan masalah pokok rentang minimum. Idea asasnya ialah untuk mengisih semua tepi dalam graf mengikut berat dari kecil ke besar, dan kemudian menambahnya pada pokok rentang secara bergilir-gilir Apabila menambah tepi, jika kedua-dua titik hujung tepi tidak tergolong dalam yang sama komponen yang disambungkan, maka tepi ini boleh ditambah pada pokok rentangan Kedua-dua titik akhir bergabung menjadi komponen yang bersambung.

Berikut ialah contoh pelaksanaan Java bagi algoritma Kruskal:

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];
    }
}

3. 
   Contoh penggunaan
Berikut ialah contoh penggunaan yang mudah:

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);
        }
    }
}

Dengan menjalankan program contoh di atas, anda boleh mendapatkan output berikut:

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

4. Di atas ialah contoh penggunaan kod khusus untuk melaksanakan algoritma pepohon rentang minimum dalam Java. Melalui kod sampel ini, pembaca boleh lebih memahami dan mempelajari proses pelaksanaan dan prinsip algoritma pepohon rentang minimum. Semoga artikel ini bermanfaat kepada pembaca.
   

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma pokok rentang minimum menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!