Prim算法详解（Java语言实现最小生成树的完整教程）

Prim算法的基本步骤

1. 选择任意一个顶点作为起始点，加入MST集合。
2. 找出连接MST集合与非MST集合的所有边中权重最小的一条。
3. 将该边及其另一端的顶点加入MST集合。
4. 重复步骤2-3，直到所有顶点都被包含进MST中。

Java实现Prim算法

下面我们使用邻接矩阵来表示图，并用优先队列（PriorityQueue）优化边的选择过程。

import java.util.*;public class PrimAlgorithm {    private static final int INF = Integer.MAX_VALUE;    // 图的顶点数    private int V;    // 邻接矩阵表示图    private int[][] graph;    public PrimAlgorithm(int vertices) {        V = vertices;        graph = new int[V][V];        // 初始化图，无边用INF表示        for (int i = 0; i < V; i++) {            Arrays.fill(graph[i], INF);        }    }    // 添加边    public void addEdge(int u, int v, int weight) {        graph[u][v] = weight;        graph[v][u] = weight; // 无向图    }    // Prim算法主函数    public void primMST() {        // key[i] 表示顶点i到MST的最小边权重        int[] key = new int[V];        // inMST[i] 表示顶点i是否已在MST中        boolean[] inMST = new boolean[V];        // parent[i] 用于记录MST的结构        int[] parent = new int[V];        // 初始化key数组为无穷大        Arrays.fill(key, INF);        Arrays.fill(parent, -1);        // 从顶点0开始        key[0] = 0;        for (int count = 0; count < V - 1; count++) {            // 找到key最小且不在MST中的顶点            int u = minKey(key, inMST);            inMST[u] = true;            // 更新相邻顶点的key值            for (int v = 0; v < V; v++) {                if (graph[u][v] != INF && !inMST[v] && graph[u][v] < key[v]) {                    parent[v] = u;                    key[v] = graph[u][v];                }            }        }        // 打印最小生成树        printMST(parent);    }    private int minKey(int[] key, boolean[] inMST) {        int min = INF, minIndex = -1;        for (int v = 0; v < V; v++) {            if (!inMST[v] && key[v] < min) {                min = key[v];                minIndex = v;            }        }        return minIndex;    }    private void printMST(int[] parent) {        System.out.println("边 \t 权重");        for (int i = 1; i < V; i++) {            System.out.println(parent[i] + " - " + i + " \t " + graph[i][parent[i]]);        }    }    public static void main(String[] args) {        PrimAlgorithm g = new PrimAlgorithm(5);        g.addEdge(0, 1, 2);        g.addEdge(0, 3, 6);        g.addEdge(1, 2, 3);        g.addEdge(1, 3, 8);        g.addEdge(1, 4, 5);        g.addEdge(2, 4, 7);        g.addEdge(3, 4, 9);        g.primMST();    }}

代码说明

上述代码实现了基于邻接矩阵的Prim算法：

• key[] 数组保存每个顶点到当前MST的最小边权重。
• inMST[] 标记顶点是否已加入MST。
• parent[] 记录MST的父子关系，用于输出结果。
• 每次循环选择一个未加入MST且key值最小的顶点，然后更新其邻居的key值。

Prim算法的时间复杂度

使用邻接矩阵的Prim算法时间复杂度为 O(V²)，其中 V 是顶点数。若使用优先队列（堆）优化，可将复杂度降至 O(E log V)，其中 E 是边数。对于稠密图，O(V²) 的实现已经足够高效。

总结

通过本教程，你已经掌握了Prim算法的基本原理、实现步骤以及完整的Java实现Prim代码。Prim算法是图论算法中的重要组成部分，广泛应用于网络设计、电路布线等领域。希望你能动手实践，加深理解！

关键词回顾：Prim算法、最小生成树、Java实现Prim、图论算法