So implementieren Sie den Kruskal-Algorithmus mit Java

So implementieren Sie den Kruskal-Algorithmus mit Java

Der Kruskal-Algorithmus ist ein Algorithmus, der häufig zur Lösung des Minimum-Spanning-Tree-Problems verwendet wird. Er verwendet Kanten als Einstiegspunkt, um schrittweise einen Minimum-Spanning-Tree aufzubauen. In diesem Artikel erklären wir detailliert, wie der Kruskal-Algorithmus mit Java implementiert wird, und stellen spezifische Codebeispiele bereit.

1. Algorithmusprinzip
   Das Grundprinzip des Kruskal-Algorithmus besteht darin, alle Kanten nach Gewicht von klein nach groß zu sortieren und dann Kanten in der Reihenfolge ihres Gewichts von klein nach groß auszuwählen, kann jedoch keinen Zyklus bilden. Die konkreten Umsetzungsschritte sind wie folgt:

   • Sortieren Sie alle Kanten nach Gewicht von klein nach groß.
   • Erstellen Sie einen leeren Satz, um die Kanten des minimalen Spannbaums zu speichern.
   • Durchqueren Sie die sortierten Kanten und bestimmen Sie, ob sich die beiden Scheitelpunkte der aktuellen Kante im selben Satz befinden. Wenn nicht im selben Satz, fügen Sie die aktuelle Kante zum Satz der minimal aufspannenden Bäume hinzu und führen Sie die beiden Eckpunkte zu einem Satz zusammen.
   • Fahren Sie weiter, bis die Anzahl der Kanten des minimalen Spannbaums gleich der Anzahl der Scheitelpunkte minus eins ist.
2. Java-Code-Implementierung
   Das Folgende ist ein Codebeispiel zur Implementierung des Kruskal-Algorithmus mithilfe der Java-Sprache:

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

Der obige Code implementiert eine einfache Diagrammklasse (Graph), einschließlich Kantenklasse (Edge) und Union-Suchklasse (Subset). ) ). In der Hauptfunktion erstellen wir ein Diagrammobjekt, fügen Kanten hinzu und rufen die KruskalMST()-Methode auf, um den minimalen Spannbaum zu erhalten.

3. Ergebnisanalyse
   Nach dem Testen kann der obige Code die folgenden Ergebnisse korrekt ausgeben:

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

Dies bedeutet, dass der konstruierte minimale Spannbaum 3 Kanten enthält und die Summe der Gewichte 19 beträgt.

Zusammenfassung:
In diesem Artikel haben wir detailliert beschrieben, wie der Kruskal-Algorithmus mit Java implementiert wird, und spezifische Codebeispiele beigefügt. Ich hoffe, dieser Artikel kann jedem helfen, den Kruskal-Algorithmus besser zu verstehen und anzuwenden.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Kruskal-Algorithmus mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!