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; }}