构建高效网络的基石（Java语言最小生成树贪心算法从零入门教程）

Prim 算法（点贪心）

Prim算法从任意一个顶点开始，逐步扩展已选顶点集合，每次选择连接已选集合和未选集合的最小权重边，直到包含所有顶点。

核心思想：维护一个“已加入MST的顶点集合”，每次找离这个集合最近的点加入。

Java 实现 Prim 算法

import java.util.*;public class PrimMST {    private static final int INF = Integer.MAX_VALUE;    public static void prim(int[][] graph, int n) {        int[] key = new int[n];     // 到MST的最小边权重        boolean[] inMST = new boolean[n]; // 是否已在MST中        int[] parent = new int[n];  // MST的父节点        // 初始化        Arrays.fill(key, INF);        Arrays.fill(parent, -1);        key[0] = 0; // 从顶点0开始        for (int count = 0; count < n; count++) {            // 找到key最小且不在MST中的顶点            int u = -1;            for (int v = 0; v < n; v++) {                if (!inMST[v] && (u == -1 || key[v] < key[u])) {                    u = v;                }            }            inMST[u] = true;            // 更新相邻顶点的key值            for (int v = 0; v < n; v++) {                if (graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v]) {                    parent[v] = u;                    key[v] = graph[u][v];                }            }        }        // 输出结果        System.out.println("边\t权重");        for (int i = 1; i < n; i++) {            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);        }    }    public static void main(String[] args) {        int n = 5;        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}        };        prim(graph, n);    }}

这段代码使用邻接矩阵表示图，时间复杂度为 O(V²)，适合稠密图。若使用优先队列（如PriorityQueue）优化，可降至 O(E log V)。

Kruskal 算法（边贪心）

Kruskal算法则从所有边中按权重从小到大排序，依次选取边，如果该边不会形成环，则加入MST，直到有 V-1 条边为止。

关键工具：并查集（Union-Find）用于高效检测环。

Java 实现 Kruskal 算法

import java.util.*;class Edge implements Comparable {    int src, dest, weight;    public Edge(int src, int dest, int weight) {        this.src = src;        this.dest = dest;        this.weight = weight;    }    @Override    public int compareTo(Edge other) {        return this.weight - other.weight;    }}public class KruskalMST {    static class UnionFind {        int[] parent;        int[] rank;        public UnionFind(int n) {            parent = new int[n];            rank = new int[n];            for (int i = 0; i < n; i++) {                parent[i] = i;            }        }        public int find(int x) {            if (parent[x] != x) {                parent[x] = find(parent[x]); // 路径压缩            }            return parent[x];        }        public void union(int x, int y) {            int rootX = find(x);            int rootY = find(y);            if (rootX != rootY) {                if (rank[rootX] < rank[rootY]) {                    parent[rootX] = rootY;                } else if (rank[rootX] > rank[rootY]) {                    parent[rootY] = rootX;                } else {                    parent[rootY] = rootX;                    rank[rootX]++;                }            }        }    }    public static void kruskal(Edge[] edges, int n) {        Arrays.sort(edges); // 按权重升序排序        UnionFind uf = new UnionFind(n);        List<Edge> result = new ArrayList<>();        for (Edge edge : edges) {            int x = uf.find(edge.src);            int y = uf.find(edge.dest);            if (x != y) { // 不成环                result.add(edge);                uf.union(x, y);            }            if (result.size() == n - 1) break;        }        System.out.println("边\t权重");        for (Edge e : result) {            System.out.println(e.src + " - " + e.dest + "\t" + e.weight);        }    }    public static void main(String[] args) {        int n = 4;        Edge[] edges = {            new Edge(0, 1, 10),            new Edge(0, 2, 6),            new Edge(0, 3, 5),            new Edge(1, 3, 15),            new Edge(2, 3, 4)        };        kruskal(edges, n);    }}

Prim vs Kruskal：如何选择？

• Prim算法适合稠密图（边多），使用邻接表+优先队列效率高。
• Kruskal算法适合稀疏图（边少），因为要排序所有边，但实现更直观。

总结

通过本教程，你已经掌握了用Java语言实现最小生成树的两种经典贪心算法：Prim 和 Kruskal。无论你是准备面试、做课程设计，还是研究算法原理，这些知识都是扎实的基础。

记住：贪心算法教程的核心在于理解“局部最优能否导向全局最优”。对于MST问题，答案是肯定的！

现在，动手运行上面的代码，修改图的结构，观察输出结果吧！实践是最好的学习方式。

关键词回顾：Java最小生成树、贪心算法教程、Prim算法Java实现、Kruskal算法详解。