Comment implémenter l'algorithme d'arbre couvrant minimum à l'aide de Java

Comment utiliser Java pour implémenter l'algorithme d'arbre couvrant minimum

L'algorithme d'arbre couvrant minimum est un problème classique de la théorie des graphes, utilisé pour résoudre l'arbre couvrant minimum d'un graphe connecté pondéré. Cet article expliquera comment utiliser le langage Java pour implémenter cet algorithme et fournira des exemples de code spécifiques.

1. Description du problème
   Étant donné un graphe connecté G, dans lequel chaque arête a un poids, il est nécessaire de trouver un arbre couvrant minimum T tel que la somme des poids de toutes les arêtes dans T soit minimale.
2. L'algorithme de Prim
   L'algorithme de Prim est un algorithme glouton utilisé pour résoudre le problème de l'arbre couvrant minimum. Son idée de base est de partir d'un sommet et d'étendre progressivement l'arbre couvrant, en sélectionnant à chaque fois le sommet le plus proche de l'arbre couvrant existant jusqu'à ce que tous les sommets soient ajoutés à l'arbre couvrant.

Ce qui suit est un exemple d'implémentation Java de l'algorithme de 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;
    }
}

3. L'algorithme de Kruskal
   L'algorithme de Kruskal est également un algorithme glouton utilisé pour résoudre le problème de l'arbre couvrant minimum. Son idée de base est de trier toutes les arêtes du graphique en fonction de leur poids, de petit à grand, puis de les ajouter tour à tour à l'arbre couvrant lors de l'ajout d'une arête, si les deux extrémités de l'arête n'appartiennent pas au même. composant connecté, cela peut être Les deux points de terminaison fusionnent en un composant connecté.

Ce qui suit est un exemple d'implémentation Java de l'algorithme 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];
    }
}

4. Exemple d'utilisation
   Ce qui suit est un exemple d'utilisation simple :

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

En exécutant l'exemple de programme ci-dessus, vous pouvez obtenir le résultat suivant :

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

Ce qui précède est l'utilisation d'exemples de code spécifiques pour implémenter l'algorithme d'arbre couvrant minimum en Java. Grâce à ces exemples de codes, les lecteurs peuvent mieux comprendre et apprendre le processus de mise en œuvre et les principes de l'algorithme d'arbre couvrant minimum. J'espère que cet article sera utile aux lecteurs.

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!