Prim 算法 (Prim's Algorithm)

算法原理

Prim算法是一种用于寻找加权连通图的最小生成树（MST）的贪心算法。最小生成树是连接图中所有顶点的边的集合，且这些边的权重之和最小。Prim算法从一个顶点开始，逐步扩展生成树，每次选择连接已选顶点集和未选顶点集中权重最小的边，直到所有顶点都被包含在生成树中。

算法步骤

1. 初始化：选择任意一个顶点作为起始顶点，将其加入生成树中
2. 创建一个优先队列，用于存储连接生成树和非生成树顶点的边
3. 将起始顶点的所有边加入优先队列
4. 当生成树未包含所有顶点时，重复执行以下操作：
   • 从优先队列中取出权重最小的边
   • 如果该边连接的顶点不在生成树中，则将该边加入MST，并将新顶点加入生成树
   • 将新顶点的所有边加入优先队列
5. 重复步骤4直到生成树包含所有顶点

代码实现

import java.util.*;

public class PrimsAlgorithm {
    // 图的表示
    static class Graph {
        private int vertices;
        private List> adjList;
        
        static class Edge {
            int src;
            int dest;
            int weight;
            
            Edge(int src, int dest, int weight) {
                this.src = src;
                this.dest = dest;
                this.weight = weight;
            }
        }
        
        Graph(int vertices) {
            this.vertices = vertices;
            adjList = new ArrayList<>(vertices);
            for (int i = 0; i < vertices; i++) {
                adjList.add(new ArrayList<>());
            }
        }
        
        // 添加边
        void addEdge(int src, int dest, int weight) {
            adjList.get(src).add(new Edge(src, dest, weight));
            adjList.get(dest).add(new Edge(dest, src, weight)); // 无向图
        }
        
        // Prim算法实现
        void primMST() {
            // 用于存储MST的边
            List mst = new ArrayList<>();
            
            // 记录顶点是否已在MST中
            boolean[] inMST = new boolean[vertices];
            
            // 优先队列，按权重排序
            PriorityQueue pq = new PriorityQueue<>(vertices, 
                (a, b) -> a.weight - b.weight);
            
            // 从顶点0开始
            int startVertex = 0;
            inMST[startVertex] = true;
            
            // 将起始顶点的所有边加入优先队列
            for (Edge edge : adjList.get(startVertex)) {
                pq.add(edge);
            }
            
            // MST需要包含V-1条边
            while (mst.size() < vertices - 1 && !pq.isEmpty()) {
                // 取出权重最小的边
                Edge minEdge = pq.poll();
                
                int src = minEdge.src;
                int dest = minEdge.dest;
                int weight = minEdge.weight;
                
                // 检查这条边是否能扩展MST
                if (inMST[src] && !inMST[dest]) {
                    // 将边加入MST
                    mst.add(minEdge);
                    inMST[dest] = true;
                    
                    // 将新顶点的所有边加入优先队列
                    for (Edge edge : adjList.get(dest)) {
                        if (!inMST[edge.dest]) {
                            pq.add(edge);
                        }
                    }
                } else if (!inMST[src] && inMST[dest]) {
                    // 处理另一种情况
                    mst.add(minEdge);
                    inMST[src] = true;
                    
                    for (Edge edge : adjList.get(src)) {
                        if (!inMST[edge.dest]) {
                            pq.add(edge);
                        }
                    }
                }
            }
            
            // 输出MST
            System.out.println("最小生成树的边:");
            int totalWeight = 0;
            for (Edge edge : mst) {
                System.out.println(edge.src + " - " + edge.dest + " : " + edge.weight);
                totalWeight += edge.weight;
            }
            System.out.println("总权重: " + totalWeight);
        }
    }

    // 测试方法
    public static void main(String[] args) {
        // 创建图
        Graph graph = new Graph(6);
        
        // 添加边 (起点, 终点, 权重)
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 3);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 2);
        graph.addEdge(2, 3, 4);
        graph.addEdge(2, 4, 2);
        graph.addEdge(3, 4, 3);
        graph.addEdge(3, 5, 2);
        graph.addEdge(4, 5, 5);
        
        System.out.println("使用Prim算法寻找最小生成树:");
        graph.primMST();
    }
}

应用场景

• 网络设计：设计连接多个地点的最小成本网络
• 电路设计：在电路板上连接各个电子元件的最短线路
• 交通规划：建设连接多个城市的最低成本道路系统
• 聚类分析：在机器学习中用于数据聚类
• 图像分割：在计算机视觉中用于图像分割

优缺点