如何使用java实现图的最小生成树算法

如何使用java实现图的最小生成树算法

概念介绍：
最小生成树（Minimum Spanning Tree, MST）是指在一个带权有向图或无向图中，找到一棵树，使得其包含图中的所有顶点且权值之和最小。最小生成树算法有多种，其中最经典的两种算法分别是Prim算法和Kruskal算法。

Prim算法：
Prim算法是一种基于点的贪婪算法，它从一个顶点开始，然后逐渐扩展，直到生成整棵最小生成树。下面是使用java实现Prim算法的示例代码：

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算法：
Kruskal算法是一种基于边的贪婪算法，它按照权值从小到大的顺序选择边，并且只选择不会产生环的边，直到生成整棵最小生成树。下面是使用java实现Kruskal算法的示例代码：

import java.util.*;

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

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

class KruskalAlgorithm {
    public List kruskalMST(List edges, int vertices) {
        List 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 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 result = kruskal.kruskalMST(edges, vertices);

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

以上是使用java实现Prim算法和Kruskal算法的示例代码，它们都是实现图的最小生成树算法的经典方法。通过学习和理解这些代码，可以更好地理解和掌握如何使用java实现图的最小生成树算法。