So implementieren Sie den Minimal-Spanning-Tree-Algorithmus mit Java

So verwenden Sie Java, um den Minimum-Spanning-Tree-Algorithmus zu implementieren

Der Minimum-Spanning-Tree-Algorithmus ist ein klassisches Problem in der Graphentheorie, das zur Lösung des Minimum-Spanning-Tree eines gewichteten verbundenen Graphen verwendet wird. In diesem Artikel wird erläutert, wie Sie diesen Algorithmus mithilfe der Java-Sprache implementieren, und es werden spezifische Codebeispiele bereitgestellt.

1. Problembeschreibung
   Gegeben ein zusammenhängender Graph G, in dem jede Kante ein Gewicht hat, muss ein minimaler Spannbaum T gefunden werden, sodass die Summe der Gewichte aller Kanten in T minimal ist.
2. Prims Algorithmus
   Prims Algorithmus ist ein Greedy-Algorithmus, der zur Lösung des Minimum-Spanning-Tree-Problems verwendet wird. Seine Grundidee besteht darin, von einem Scheitelpunkt aus zu beginnen und den Spannbaum schrittweise zu erweitern, wobei jedes Mal der Scheitelpunkt ausgewählt wird, der dem vorhandenen Spannbaum am nächsten liegt, bis alle Scheitelpunkte zum Spannbaum hinzugefügt sind.

Das Folgende ist ein Java-Implementierungsbeispiel des Prim-Algorithmus:

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. Kruskals Algorithmus
   Kruskals Algorithmus ist auch ein Greedy-Algorithmus, der zur Lösung des Minimum-Spanning-Tree-Problems verwendet wird. Die Grundidee besteht darin, alle Kanten im Diagramm nach ihrem Gewicht von klein nach groß zu sortieren und sie dann nacheinander zum Spannbaum hinzuzufügen. Wenn die beiden Endpunkte der Kante nicht zum gleichen gehören Verbundene Komponente, dann können diese Kanten zum Spanning Tree hinzugefügt werden. Die beiden Endpunkte verschmelzen zu einer verbundenen Komponente.

Das Folgende ist ein Beispiel für die Java-Implementierung des Kruskal-Algorithmus:

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. Beispielverwendung
   Das Folgende ist ein einfaches Beispielverwendungsbeispiel:

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

Durch Ausführen des obigen Beispielprogramms können Sie die folgende Ausgabe erhalten:

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

Das Obige ist die Verwendung Spezifische Codebeispiele für die Implementierung des Minimum-Spanning-Tree-Algorithmus in Java. Durch diese Beispielcodes können Leser den Implementierungsprozess und die Prinzipien des Minimum-Spanning-Tree-Algorithmus besser verstehen und lernen. Ich hoffe, dieser Artikel ist für die Leser hilfreich.

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