Bagaimana untuk melaksanakan algoritma Kruskal menggunakan java

Cara menggunakan Java untuk melaksanakan algoritma Kruskal

Algoritma Kruskal ialah algoritma yang biasa digunakan untuk menyelesaikan masalah pokok rentang minimum yang menggunakan tepi sebagai titik input, dan secara beransur-ansur membina pokok rentang minimum. Dalam artikel ini, kami akan memperincikan cara melaksanakan algoritma Kruskal menggunakan Java dan memberikan contoh kod khusus.

1. Prinsip Algoritma
   Prinsip asas algoritma Kruskal adalah untuk mengisih semua tepi mengikut berat dari kecil ke besar, dan kemudian pilih tepi mengikut urutan dari berat kecil hingga besar, tetapi tidak boleh membentuk cincin. Langkah-langkah pelaksanaan khusus adalah seperti berikut:

   • Isih semua tepi mengikut berat dari kecil ke besar.
   • Buat set kosong untuk menyimpan tepi pokok rentang minimum.
   • Lintas tepi yang diisih dan tentukan sama ada dua bucu tepi semasa berada dalam set yang sama. Jika mereka tidak berada dalam set yang sama, tambahkan tepi semasa pada set pokok rentang minimum dan gabungkan dua bucu menjadi satu set.
   • Teruskan melintasi sehingga bilangan tepi pokok rentang minimum adalah sama dengan bilangan bucu tolak satu.
2. Pelaksanaan kod Java
   Berikut ialah contoh kod menggunakan bahasa Java untuk melaksanakan algoritma Kruskal:

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;

    public int compareTo(Edge edge) {
        return this.weight - edge.weight;
    }
}

class Subset {
    int parent, rank;
}

class Graph {
    int V, E;
    Edge[] edges;

    public Graph(int v, int e) {
        V = v;
        E = e;
        edges = new Edge[E];
        for (int i = 0; i < e; ++i)
            edges[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 KruskalMST() {
        Edge[] result = new Edge[V];
        int e = 0;
        int i = 0;
        for (i = 0; i < V; ++i)
            result[i] = new Edge();

        Arrays.sort(edges);

        Subset[] subsets = new Subset[V];
        for (i = 0; i < V; ++i)
            subsets[i] = new Subset();

        for (int v = 0; v < V; ++v) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }

        i = 0;

        while (e < V - 1) {
            Edge next_edge = edges[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:");
        int minimumCost = 0;
        for (i = 0; i < e; ++i) {
            System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
            minimumCost += result[i].weight;
        }
        System.out.println("Minimum Cost Spanning Tree: " + minimumCost);
    }
}

public class KruskalAlgorithm {
    public static void main(String[] args) {
        int V = 4;
        int E = 5;
        Graph graph = new Graph(V, E);

        graph.edges[0].src = 0;
        graph.edges[0].dest = 1;
        graph.edges[0].weight = 10;

        graph.edges[1].src = 0;
        graph.edges[1].dest = 2;
        graph.edges[1].weight = 6;

        graph.edges[2].src = 0;
        graph.edges[2].dest = 3;
        graph.edges[2].weight = 5;

        graph.edges[3].src = 1;
        graph.edges[3].dest = 3;
        graph.edges[3].weight = 15;

        graph.edges[4].src = 2;
        graph.edges[4].dest = 3;
        graph.edges[4].weight = 4;

        graph.KruskalMST();
    }
}

#🎜 Kod di atas Kelas graf ringkas (Graf) dilaksanakan, termasuk kelas tepi (Tepi) dan kelas pencarian kesatuan (Subset). Dalam fungsi utama, kami mencipta objek graf, menambah tepi dan memanggil kaedah KruskalMST() untuk mendapatkan pokok rentang minimum.

Analisis Keputusan
3. Selepas ujian, kod di atas boleh mengeluarkan keputusan berikut dengan betul:
   

Following are the edges in the constructed MST:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost Spanning Tree: 19

Ini bermakna span minimum pokok yang dibina mengandungi Terdapat 3 sisi, dan jumlah pemberatnya ialah 19.
Ringkasan:

Melalui artikel ini, kami memperkenalkan secara terperinci cara menggunakan Java untuk melaksanakan algoritma Kruskal, dan melampirkan contoh kod khusus. Saya harap artikel ini dapat membantu semua orang memahami dan menggunakan algoritma Kruskal dengan lebih baik.


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