So implementieren Sie den Minimum-Spanning-Tree-Algorithmus für Diagramme mit Java

So verwenden Sie Java, um den Minimum Spanning Tree-Algorithmus für Diagramme zu implementieren

Einführung in das Konzept:
Minimum Spanning Tree (MST) bezieht sich auf das Finden eines Baums in einem gewichteten gerichteten Diagramm oder einem ungerichteten Diagramm. Stellen Sie sicher, dass er alle Scheitelpunkte umfasst im Diagramm und haben die kleinste Summe der Gewichte. Es gibt viele Minimum-Spanning-Tree-Algorithmen. Die beiden klassischsten Algorithmen sind der Prim-Algorithmus und der Kruskal-Algorithmus.

Prim-Algorithmus:
Prim-Algorithmus ist ein punktbasierter Greedy-Algorithmus, der an einem Scheitelpunkt beginnt und sich dann schrittweise erweitert, bis der gesamte minimale Spannbaum generiert ist. Das Folgende ist ein Beispielcode für die Implementierung des Prim-Algorithmus mit Java:

import java.util.Arrays;

public class PrimAlgorithm {

    // 表示无穷大
    private static final int INF = Integer.MAX_VALUE;

    public static void primMST(int[][] graph) {
        int vertices = graph.length;

        // 创建一个数组用来保存最小生成树的顶点
        int[] parent = new int[vertices];

        // 创建一个数组用来保存每个顶点与最小生成树的最小权值
        int[] key = new int[vertices];

        // 创建一个数组用来标记顶点是否已经加入最小生成树
        boolean[] mstSet = new boolean[vertices];

        // 初始化key数组和mstSet数组的值
        Arrays.fill(key, INF);
        Arrays.fill(mstSet, false);

        //将第一个顶点加入最小生成树
        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < vertices - 1; count++) {
            // 选择key值最小的顶点
            int minKey = getMinKey(key, mstSet);
            mstSet[minKey] = true;

            // 更新与该顶点相邻的顶点的key值
            for (int v = 0; v < vertices; v++) {
                if (graph[minKey][v] != 0 && !mstSet[v] && graph[minKey][v] < key[v]) {
                    parent[v] = minKey;
                    key[v] = graph[minKey][v];
                }
            }
        }

        // 输出最小生成树
        printMST(parent, graph);
    }

    // 获得key值最小的顶点
    private static int getMinKey(int[] key, boolean[] mstSet) {
        int minKey = INF, minIndex = -1;
        for (int v = 0; v < key.length; v++) {
            if (!mstSet[v] && key[v] < minKey) {
                minKey = key[v];
                minIndex = v;
            }
        }
        return minIndex;
    }

    // 输出最小生成树
    private static void printMST(int[] parent, int[][] graph) {
        System.out.println("Edge   Weight");
        for (int i = 1; i < graph.length; i++) {
            System.out.println(parent[i] + " - " + i + "    " + graph[i][parent[i]]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {{0, 2, 0, 6, 0},
                         {2, 0, 3, 8, 5},
                         {0, 3, 0, 0, 7},
                         {6, 8, 0, 0, 9},
                         {0, 5, 7, 9, 0}};
        primMST(graph);
    }
}

Kruskals Algorithmus:
Kruskals Algorithmus ist ein kantenbasierter Greedy-Algorithmus, der Kanten in der Reihenfolge von klein bis groß auswählt und nur Kanten auswählt, die keine Zyklen erzeugen , bis der gesamte minimale Spannbaum generiert ist. Das Folgende ist ein Beispielcode für die Verwendung von Java zur Implementierung des Kruskal-Algorithmus:

import java.util.*;

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

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

class KruskalAlgorithm {
    public List<Edge> kruskalMST(List<Edge> edges, int vertices) {
        List<Edge> result = new ArrayList<>();
        Collections.sort(edges);

        int[] parent = new int[vertices];
        for (int i = 0; i < vertices; i++) {
            parent[i] = i;
        }

        int count = 0, i = 0;
        while (count < vertices - 1) {
            Edge currentEdge = edges.get(i);

            int x = find(parent, currentEdge.src);
            int y = find(parent, currentEdge.dest);

            if (x != y) {
                result.add(currentEdge);
                union(parent, x, y);
                count++;
            }

            i++;
        }

        return result;
    }

    private int find(int[] parent, int vertex) {
        if (parent[vertex] != vertex) {
            parent[vertex] = find(parent, parent[vertex]);
        }
        return parent[vertex];
    }

    private void union(int[] parent, int x, int y) {
        int xSet = find(parent, x);
        int ySet = find(parent, y);
        parent[xSet] = ySet;
    }

    public static void main(String[] args) {
        int vertices = 4;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));

        KruskalAlgorithm kruskal = new KruskalAlgorithm();
        List<Edge> result = kruskal.kruskalMST(edges, vertices);

        System.out.println("Edge   Weight");
        for (Edge edge : result) {
            System.out.println(edge.src + " - " + edge.dest + "    " + edge.weight);
        }
    }
}

Das Obige ist ein Beispielcode für die Verwendung von Java zur Implementierung des Prim-Algorithmus und des Kruskal-Algorithmus. Beides sind klassische Methoden zur Implementierung des Minimum-Spanning-Tree-Algorithmus von Graphen. Durch das Erlernen und Verstehen dieser Codes können Sie besser verstehen und beherrschen, wie Sie mit Java den Minimum-Spanning-Tree-Algorithmus von Diagrammen implementieren.

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