## Prim算法 **最小生成树**：在无向图里找到一个连通图的所有顶点的无环子集，使得子集中的边的权重之和最小。 ### 算法描述 prim算法求图的最小生成树（加点法）： 1. 从图里一个顶点出发，找该点相邻的最小边edge加入到小根堆 2. 取出小根堆里的边edge,判断edge的to顶点是否已经经过，没有则找到最小边，有则跳过 3. 将edge.to顶点的相邻边加入到小根堆里，循环2，3步骤 ### 步骤图解析  ``` prim mst edge: edge: 1->3的weight=2 edge: 3->5的weight=1 edge: 1->2的weight=3 edge: 2->4的weight=5 ``` ### Java代码实现 ~~~ /** * prim算法求图的最小生成树（加点法） * 1. 从图里一个顶点出发，找该点相邻的最小边edge加入到小根堆 * 2. 取出小根堆里的边edge,判断edge的to顶点是否已经经过，没有则找到最小边，有则跳过 * 3. 将edge.to顶点的相邻边加入到小根堆里，循环2，3步骤 * @return 最小边集合 */ public Set<Edge> primMST(){ Set<Edge> result = new LinkedHashSet<>(); // 小根堆，使用边的权值排序 PriorityQueue<Edge> edgePQ = new PriorityQueue<>(((o1, o2) -> o1.weight - o2.weight)); Set<Vertex> pass = new HashSet<>(); // 加上循环是为了防止森林场景 for(Vertex vertex : vertexs.values()){ // 该顶点没有在pass里 if(!pass.contains(vertex)) { // 将顶点加入到pass里，表示经过该顶点 pass.add(vertex); // 将该顶点的相邻的边加入到堆里 for (Edge edge : vertex.edges) { edgePQ.offer(edge); } // 取出该节点最小边 while (!edgePQ.isEmpty()) { Edge edge = edgePQ.poll(); // 没有经过edge.to顶点 if (!pass.contains(edge.to)) { // 记录到边集合里 result.add(edge); // 将edge.to顶点加入到pass里 pass.add(edge.to); // 将edge.to顶点相邻的边加入到小根堆里 for (Edge next : edge.to.edges) { if (!edgePQ.contains(next)) { edgePQ.offer(next); } } } } } } return result; } ~~~