Bagaimana untuk melaksanakan algoritma pepohon rentang minimum graf menggunakan java

Cara menggunakan java untuk melaksanakan algoritma pepohon rentang minimum bagi graf

Pengenalan konsep:
Pokok Rentang Minimum ) ) merujuk kepada mencari pokok dalam graf terarah berwajaran atau graf tidak terarah supaya ia mengandungi semua bucu dalam graf dan mempunyai jumlah pemberat terkecil. Terdapat banyak algoritma pokok rentang minimum, dua algoritma paling klasik ialah algoritma Prim dan algoritma Kruskal.

Algoritma Prim:
Algoritma Prim ialah algoritma tamak berasaskan titik yang bermula dari bucu dan kemudian secara beransur-ansur mengembang sehingga keseluruhan pokok rentang minimum dijana. Berikut ialah contoh kod untuk melaksanakan algoritma Prim menggunakan 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);
    }
}

Algoritma Kruskal:
Algoritma Kruskal ialah algoritma tamak berasaskan tepi, yang memilih tepi mengikut urutan berat dari kecil ke besar . Dan hanya pilih tepi yang tidak akan menghasilkan kitaran sehingga keseluruhan pokok rentang minimum dijana. Berikut ialah kod sampel untuk menggunakan java untuk melaksanakan algoritma Kruskal:

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

Di atas ialah kod sampel untuk menggunakan java untuk melaksanakan algoritma Prim dan algoritma Kruskal Kedua-duanya adalah kaedah klasik untuk melaksanakan rentang minimum algoritma pokok bagi graf. Dengan mempelajari dan memahami kod ini, anda boleh lebih memahami dan menguasai cara menggunakan Java untuk melaksanakan algoritma pepohon rentang minimum graf.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma pepohon rentang minimum graf menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!