Java中的最小生成树算法

什么是最小生成树算法

最小生成树（Minimum Spanning Tree，简称MST）是一种用于在连通图中选取最小权值边组成的树结构的算法。最小生成树算法的目标是在一个加权连通图中找到一个生成树，使得树上所有边的权值之和最小。

最小生成树算法的应用

最小生成树算法常用于解决网络规划、城市规划、电力网络等问题。它可以帮助我们找到连接所有节点的最短路径，以保证资源的最优使用。

Java中的最小生成树算法实现

Java中有几种常用的最小生成树算法，包括Prim算法和Kruskal算法。

Prim算法

Prim算法是一种贪心算法，它通过逐步扩展生成树，始终选择当前最小权值的边来扩展。Prim算法的基本思想是从一个起始点开始，逐步向外扩展，每次选择与当前生成树相距最近的顶点并加入生成树。

以下是Java中Prim算法的实现示例：

import java.util.Arrays;

class PrimMST {
    int V; // 图的顶点数
    int[][] graph; // 存储图的邻接矩阵

    public PrimMST(int vertices, int[][] adjacencyMatrix) {
        V = vertices;
        graph = adjacencyMatrix;
    }

    // 找到与当前生成树相距最近的顶点
    int minKey(int[] key, boolean[] mstSet) {
        int min = Integer.MAX_VALUE, minIndex = -1;

        for (int v = 0; v < V; v++) {
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    // 打印最小生成树
    void printMST(int[] parent, int[][] graph) {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
        }
    }

    // 构建最小生成树
    void primMST() {
        int[] parent = new int[V];
        int[] key = new int[V];
        boolean[] mstSet = new boolean[V];

        Arrays.fill(key, Integer.MAX_VALUE);
        Arrays.fill(mstSet, false);

        key[0] = 0; // 从第一个顶点开始构建生成树
        parent[0] = -1;

        for (int count = 0; count < V - 1; count++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;

            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }

        printMST(parent, graph);
    }

    public static void main(String[] args) {
        int vertices = 5;
        int[][] adjacencyMatrix = new int[][] {
            { 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 prim = new PrimMST(vertices, adjacencyMatrix);
        prim.primMST();
    }
}

Kruskal算法

Kruskal算法也是一种贪心算法，它通过选择当前最小权值边来逐步生成树。与Prim算法不同的是，Kruskal算法首先将边按照权值从小到大进行排序，然后逐个加入生成树，直到生成树包含所有的顶点。

以下是Java中Kruskal算法的实现示例：

import java.util.Arrays;

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

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

    int V, E;
    Edge[] edges;

    public KruskalMST(int vertices, int edges) {
        V = vertices;
        E = edges;
        this.edges = new Edge[E];
        for (int i = 0; i < E; ++i) {
            this.edges[i] = new Edge();
        }
    }

    // 找到顶点的子集
    int find(int[] parent, int i) {
        if (parent[i] == -1)
            return i;
        return find(parent, parent[i]);
    }

    // 合并两个顶点的子集
    void union(int[] parent, int x, int y) {
        int xset = find(parent, x);
        int yset = find(parent, y);
        parent[xset] = yset;
    }

    // 构建最小生成树
    void kruskalMST() {
        Edge[] result = new Edge[V];
        int e = 0;
        int i = 0;
        for (i = 0; i < V; ++i) {
            result[i] = new Edge();
        }

        Arrays.sort(edges);

        int[] parent = new int[V];

        Arrays.fill(parent, -1);

        i = 0;

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

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

        System.out.println("Edge \tWeight");
        for (i = 0; i < e; ++i) {
            System.out.println(result[i].src + " - " + result[i].dest + "\t" + result[i].weight);
        }
    }

    public static void main(String[] args) {
        int vertices = 5;
        int edges = 7;

        KruskalMST kruskal = new KruskalMST(vertices, edges);

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

        // 其他边类似地进行初始化

        kruskal.kruskalMST();
    }
}

结语

最小生成树算法是解决连通图最优路径的重要算法之一，并广泛应用于各种领域。在Java中，我们可以使用Prim算法和Kruskal算法实现最小生成树的构建。希望通过本文，您对Java中的最小生成树算法有了更深入的了解。

本文来自极简博客，作者：人工智能梦工厂，转载请注明原文链接：Java中的最小生成树算法