> 文档中心 > prim算法 (普利姆算法) (图 / 最小生产树)

prim算法 (普利姆算法) (图 / 最小生产树)

prim算法(普利姆算法):对图G(V,E)设置集合S,存放已访问的顶点,然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点(记为u),访问并加入集合S。之后,令顶点u为中介点,优化所有从u能到达的顶点v与集合S之间的最短距离。执行n次(n为顶点个数),直到集合S已包含所有顶点。

思路

在这里插入图片描述
在这里插入图片描述

代码实现

package graph;import java.util.Comparator;import java.util.HashSet;import java.util.PriorityQueue;import java.util.Set;public class Code05_Prim {    public class MyCompartor implements Comparator<Edge> { @Override public int compare(Edge o1, Edge o2) {     return o1.weight - o2.weight; }    }    public Set<Edge> primMST(Graph graph) { // 创建小根堆,边的权重越小越靠前 PriorityQueue<Edge> queue = new PriorityQueue<>(); // 创建点集,防止重复加入 Set<Node> nodeSet = new HashSet<>(); // 结果边集 Set<Edge> result = new HashSet<>(); // 遍历点 for (Node node : graph.nodes.values()) {     if (!nodeSet.contains(node)) {  nodeSet.add(node); // 加入点集  for (Edge edge : node.edges) {      queue.offer(edge);  // 点所连的边加入边集  }     }     while (!queue.isEmpty()) {  Edge cur = queue.poll();  Node toNode = cur.to;  // 如果toNode不在点集中,说明可以加入,将toNode加入点集,toNode所连边加入队列  if (!nodeSet.contains(toNode)) {      nodeSet.add(toNode);      result.add(cur);  // 将可以加入的边加入结果集中      for (Edge edge : toNode.edges) {   queue.offer(edge);      }  }     } } return result;    }}

小故事网