Comment implémenter l'algorithme Kruskal en utilisant Java

Comment utiliser Java pour implémenter l'algorithme de Kruskal

L'algorithme de Kruskal est un algorithme couramment utilisé pour résoudre le problème de l'arbre couvrant minimum. Il utilise les arêtes comme point d'entrée pour construire progressivement un arbre couvrant minimum. Dans cet article, nous détaillerons comment implémenter l'algorithme de Kruskal à l'aide de Java et fournirons des exemples de code spécifiques.

1. Principe de l'algorithme
   Le principe de base de l'algorithme de Kruskal est de trier toutes les arêtes en fonction de leur poids, de petit à grand, puis de sélectionner les arêtes par ordre de poids de petit à grand, mais ne peut pas former de cycle. Les étapes spécifiques de mise en œuvre sont les suivantes :

   • Trier tous les bords en fonction du poids du petit au grand.
   • Créez un ensemble vide pour stocker les bords de l'arbre couvrant minimum.
   • Parcourez les arêtes triées et déterminez si les deux sommets de l'arête actuelle sont dans le même ensemble. S'il ne se trouve pas dans le même ensemble, ajoutez l'arête actuelle à l'ensemble des arbres couvrant minimum et fusionnez les deux sommets en un seul ensemble.
   • Continuez à parcourir jusqu'à ce que le nombre d'arêtes de l'arbre couvrant minimum soit égal au nombre de sommets moins un.
2. Implémentation du code Java
   Ce qui suit est un exemple de code pour implémenter l'algorithme Kruskal en utilisant le langage Java :

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

Le code ci-dessus implémente une classe graphique simple (Graph), y compris la classe Edge (Edge) et la classe de recherche d'union (Subset ) ). Dans la fonction principale, nous créons un objet graphique, ajoutons des arêtes et appelons la méthode KruskalMST() pour obtenir l'arbre couvrant minimum.

3. Analyse des résultats
   Après le test, le code ci-dessus peut générer correctement les résultats suivants :

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

Cela signifie que l'arbre couvrant minimum construit contient 3 arêtes et que la somme des poids est de 19.

Résumé :
À travers cet article, nous avons présenté en détail comment implémenter l'algorithme de Kruskal à l'aide de Java, et joint des exemples de code spécifiques. J'espère que cet article pourra aider tout le monde à mieux comprendre et appliquer l'algorithme de Kruskal.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!