Java函数实现最小生成树算法

最小生成树算法是图论中的重要算法之一，用来找到一个连通图的最小权重生成树。常见的最小生成树算法有普里姆算法和克鲁斯卡尔算法。以下是Java函数实现最小生成树算法的示例代码。

普里姆算法（Prim's Algorithm）：

import java.util.Arrays;

public class PrimAlgorithm {
    public static void primMST(int[][] graph) {
        int numVertices = graph.length;
        int[] parent = new int[numVertices]; // 存储最小生成树中的边
        int[] key = new int[numVertices]; // 存储从最小生成树中的顶点到未访问顶点集合中的顶点的最小权重

        boolean[] visited = new boolean[numVertices]; // 标记顶点是否被访问过

        Arrays.fill(key, Integer.MAX_VALUE); // 初始化key数组
        key[0] = 0; // 选取一个起始顶点
        parent[0] = -1; // 起始顶点没有父节点

        for (int i = 0; i < numVertices - 1; i++) {
            int minKeyIndex = findMinKeyIndex(key, visited); // 找到最小key值对应的顶点
            visited[minKeyIndex] = true; // 标记该顶点被访问

            for (int j = 0; j < numVertices; j++) {
                if (graph[minKeyIndex][j] != 0 && !visited[j] && graph[minKeyIndex][j] < key[j]) {
                    parent[j] = minKeyIndex;
                    key[j] = graph[minKeyIndex][j];
                }
            }
        }

        printMST(parent, graph);
    }

    private static int findMinKeyIndex(int[] key, boolean[] visited) {
        int minKey = Integer.MAX_VALUE;
        int minKeyIndex = -1;

        for (int i = 0; i < key.length; i++) {
            if (!visited[i] && key[i] < minKey) {
                minKey = key[i];
                minKeyIndex = i;
            }
        }

        return minKeyIndex;
    }

    private static void printMST(int[] parent, int[][] graph) {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < graph.length; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + 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's Algorithm）：

import java.util.Arrays;
import java.util.Comparator;

public class KruskalAlgorithm {
    class Edge {
        int src;
        int dest;
        int weight;

        Edge() {
            src = dest = weight = 0;
        }
    }

    class Graph {
        int numVertices;
        int numEdges;
        Edge[] edges;

        Graph(int numVertices, int numEdges) {
            this.numVertices = numVertices;
            this.numEdges = numEdges;
            edges = new Edge[numEdges];
            for (int i = 0; i < numEdges; i++) {
                edges[i] = new Edge();
            }
        }
    }

    class Subset {
        int parent;
        int rank;
    }

    int find(Subset[] subsets, int i) {
        if (subsets[i].parent != i) {
            subsets[i].parent = find(subsets, subsets[i].parent);
        }

        return subsets[i].parent;
    }

    void union(Subset[] subsets, int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);

        if (subsets[xroot].rank < subsets[yroot].rank) {
            subsets[xroot].parent = yroot;
        } else if (subsets[yroot].rank < subsets[xroot].rank) {
            subsets[yroot].parent = xroot;
        } else {
            subsets[xroot].parent = yroot;
            subsets[yroot].rank++;
        }
    }

    void kruskalMST(Graph graph) {
        int numVertices = graph.numVertices;
        Edge[] result = new Edge[numVertices];
        for (int i = 0; i < numVertices; i++) {
            result[i] = new Edge();
        }

        Arrays.sort(graph.edges, Comparator.comparingInt(o -> o.weight));
        Subset[] subsets = new Subset[numVertices];
        for (int i = 0; i < numVertices; i++) {
            subsets[i] = new Subset();
            subsets[i].parent = i;
            subsets[i].rank = 0;
        }

        int e = 0;
        int i = 0;
        while (e < numVertices - 1) {
            Edge nextEdge = graph.edges[i++];
            int x = find(subsets, nextEdge.src);
            int y = find(subsets, nextEdge.dest);

            if (x != y) {
                result[e++] = nextEdge;
                union(subsets, x, y);
            }
        }

        printMST(result);
    }

    private void printMST(Edge[] result) {
        System.out.println("Edge \tWeight");
        for (int i = 0; i < result.length - 1; i++) {
            System.out.println(result[i].src + " - " + result[i].dest + "\t" + result[i].weight);
        }
    }

    public static void main(String[] args) {
        int numVertices = 4;
        int numEdges = 5;
        Graph graph = new Graph(numVertices, numEdges);

        graph.edges[0].src = 0;
        graph.edges[0].dest = 1;
        graph.edges[0].weight = 10;

        graph.edges[1].src = 0;
        graph.edges[1].dest = 2;
        graph.edges[1].weight = 6;

        graph.edges[2].src = 0;
        graph.edges[2].dest = 3;
        graph.edges[2].weight = 5;

        graph.edges[3].src = 1;
        graph.edges[3].dest = 3;
        graph.edges[3].weight = 15;

        graph.edges[4].src = 2;
        graph.edges[4].dest = 3;
        graph.edges[4].weight = 4;

        KruskalAlgorithm kruskal = new KruskalAlgorithm();
        kruskal.kruskalMST(graph);
    }
}

以上代码分别实现了普里姆算法和克鲁斯卡尔算法的最小生成树求解过程。普里姆算法通过维护两个集合来实现：一个集合储存已选出的最小生成树的节点，另一个集合储存未访问过的节点。每次从未访问的节点中选择一个最小权重的边添加到当前最小生成树中，并将新加入的节点包括进已访问节点的集合，直到遍历过所有的节点。克鲁斯卡尔算法通过排序边按权重从小到大的顺序，逐一选择权重最小的边并检查两个顶点是否处于同一个连通分量中，如果不在同一个连通分量中，则将两个顶点合并，并将这条边加入最小生成树中。最后输出最小生成树的边的集合。