How to implement the minimum spanning tree algorithm of graphs using java

How to use java to implement the minimum spanning tree algorithm of a graph

Concept introduction:
Minimum Spanning Tree (MST) refers to a weighted In a directed or undirected graph, find a tree that contains all the vertices in the graph and has the smallest sum of weights. There are many minimum spanning tree algorithms, the two most classic algorithms are Prim's algorithm and Kruskal's algorithm.

Prim algorithm:
Prim algorithm is a point-based greedy algorithm that starts from a vertex and then gradually expands until the entire minimum spanning tree is generated. The following is a sample code for implementing Prim's algorithm using 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);
    }
}

Kruskal algorithm:
Kruskal algorithm is a greedy algorithm based on edges. It selects edges in order from small to large in weight and only selects edges. No loop edges are generated until the entire minimum spanning tree is generated. The following is a sample code for using java to implement Kruskal's algorithm:

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

The above is a sample code for using java to implement Prim's algorithm and Kruskal's algorithm. They are both classic methods for implementing the minimum spanning tree algorithm of graphs. By learning and understanding these codes, you can better understand and master how to use Java to implement the minimum spanning tree algorithm of graphs.

The above is the detailed content of How to implement the minimum spanning tree algorithm of graphs using java. For more information, please follow other related articles on the PHP Chinese website!