建网站注册,三亚久爱传媒招聘信息,做服务的网站吗,长春有微信网站一起整的吗同Kruskal算法一样#xff0c;Prim算法也是最小生成树的算法#xff0c;但与Kruskal算法有较大的差别。 Prim算法整体是通过“解锁” “选中”的方式#xff0c;点 - 边 - 点 - 边。 因为是最小生成树#xff0c;所以针对的也是无向图#xff0c;所以可以随意…同Kruskal算法一样Prim算法也是最小生成树的算法但与Kruskal算法有较大的差别。 Prim算法整体是通过“解锁” “选中”的方式点 - 边 - 点 - 边。 因为是最小生成树所以针对的也是无向图所以可以随意选取一个点作为进入点通过解锁这个点可以获得从这个点出去的所有边在通过这些边中权重最小的边解锁其他的点。如此反复。直到最小生成树的形成。 如图所示 左侧为原始图从a点出发哪个点都可以假设从a解锁了a点解锁的点画圈并且解锁了从a点直接出发权重为129的三条边边解锁为虚线根据权重选择1的边选择具体边改颜色。并解锁了b点。 通过解锁的b点可解锁权重1349的边此时bd边的权重最小为1所以解锁了d的点。 解锁d后d直接出来的边4也会进行解锁。再次选择权重较小的为2但是此时d已经解锁过了所以不考虑2再次选择be为3的边解锁。 此时解锁后图形如上面所示e点解锁后会解锁权重6、7的边。 此时所有的边都已经解锁选择权重小的边并且不会形成环的点进行解锁。 最终去掉所有没被选择的边剩余的就是最小生成树。 总结
最小生成树是要用最小距离接所有可达的点。所以随机的每一个点在获取这个点所有的边中选取权重最小的 那一条边组织起来就一定会是最小生成树组成的答案。
代码实现 基于上面图解是代码实现。点 边 - 点 - 边的解锁方式。 最外层的for循环可防“森林”。 a - b c -d e-fa可以找到bc可以找到d e可以找到f。但是a c e之间互相没关系。
public static class EdgeComparator implements ComparatorEdge {Overridepublic int compare(Edge o1, Edge o2) {return o1.weight - o2.weight;}}public static SetEdge primMST(Graph graph) {//放入PriorityQueue中并根据边的权重进行排序PriorityQueueEdge priorityQueue new PriorityQueue(new EdgeComparator());//解锁的点SetNode setNodes new HashSet();//构成最小生成树的所有边SetEdge result new HashSet();//遍历图集中所有的点for (Node node : graph.nodes.values()) {//如果没解锁if (!setNodes.contains(node)) {setNodes.add(node);//将点的所有的边放到PriorityQueue中排序for (Edge edge : node.edges) {priorityQueue.add(edge);}while (!priorityQueue.isEmpty()) {Edge edge priorityQueue.poll();//获取到这个边连接的to点Node toNode edge.to;if (!setNodes.contains(edge.to)) {//解锁to点setNodes.add(toNode);result.add(edge);//并且将to点所有的边也都放到Queue中for (Edge nextEdge : toNode.edges) {priorityQueue.add(nextEdge);}}}}//如果防森林就不break break;}return result;}
