最小生成树算法——Prim

简介: 最小生成树算法——Prim


P算法流程

一开始图中所有的边都默认被锁住了,只有边被解锁了,才能考虑要不要这条边。一开始图中所有的点也都默认全部被锁住了,只有选中了某个点,这个点才被解锁,并且这个点的直接边(从这个点出发的边)也全部被解锁。解锁的点放入一个集合。

所以,一开始从图中任意一点出发,在这个点的所有直接边里选一条权值最小的边,如果这条边的的两侧有新结点,就解锁这个结点;如果没有新结点,就不要这条边。然后新解锁的结点的直接边又全部被解锁了,再在这些边里面选权值最小的边…周而复始。

总的来说,P算法流程就是,先从某个点出发,解锁一批边,选条最小的边解锁一个新结点,再解锁一批边…

P算法不需要用到并查集,因为总是一个点解锁一批边,在这一批边里选一个点放入集合里。每次都是一个一个点进入集合,根本不存在两大片集合要合并的问题。所以表示解锁的点只需要一个集合就可以。当然边的选择还是要用到小根堆。

大家可以按照上面的思路和下面图片来理一下思路:

image.png

package com.harrison.class11;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
import com.harrison.class11.Code01_NodeEdgeGraph.*;
public class Code06_Prim {
  public static class EdgeComparator implements Comparator<Edge>{
    public int compare(Edge e1,Edge e2) {
      return e1.weight-e2.weight;
    }
  }
  public static Set<Edge> primMST(Graph graph){
    // 按边的权值组织的小根堆
    PriorityQueue<Edge> pq=new PriorityQueue<>(new EdgeComparator());
    // 解锁的点放入这个集合里
    HashSet<Node> nodeSet=new HashSet<>();
    // 保证放入小根堆里的边不会重复
    HashSet<Edge> edgeSet=new HashSet<>();
    // 选好的边就依次放入这个集合
    Set<Edge> ans=new HashSet<>();
    // for循环只是为了防止森林的出现,也可以去掉此for循环
    // 因为面试题中不会出现森林,不管有向无向
    for(Node node:graph.nodes.values()) {
      if(!nodeSet.contains(node)) {
        nodeSet.add(node);
        for(Edge edge:node.edges) {// 接下来由这个点解锁一批边
          if(!edgeSet.contains(edge)) {
            pq.add(edge);
            edgeSet.add(edge);
          }
        }
        while(!pq.isEmpty()) {
          Edge edge=pq.poll();// 弹出权值最小的边
          Node toNode=edge.to;
          if(!nodeSet.contains(toNode)) {
            nodeSet.add(toNode);
            ans.add(edge);
            for(Edge nextEdge:node.edges) {
              if(!edgeSet.contains(nextEdge)) {
                pq.add(nextEdge);
                edgeSet.add(nextEdge);
              }
            }
          }
        }
      }
      break;
    }
    return ans;
  }
}

最后再总结一下:

1)随便选一个结点解锁,相邻的边也全部解锁,然后选一条权值最小的边

2)新解锁的边两侧有新结点,则把新节点给解锁,并把新解锁的边考虑在最小生成树里面;新解锁的边两侧没有新结点,则不将新解锁的边考虑在最小生成树里面

3)新解锁的结点所有相邻的边被解锁,已经被考虑在最小生成树里的边不重复解锁,然后在所有相邻的边里选择一条权值最小的边,重复步骤 2)周而复始,一直到把所有的点都解锁完


相关文章
|
20天前
|
算法 决策智能
基于prim算法求出网络最小生成树实现网络社团划分和规划
该程序使用MATLAB 2022a版实现路线规划,通过排序节点权值并运用Prim算法生成最小生成树完成网络规划。程序基于TSP问题,采用遗传算法与粒子群优化算法进行路径优化。遗传算法通过编码、选择、交叉及变异操作迭代寻优;粒子群优化算法则通过模拟鸟群觅食行为,更新粒子速度和位置以寻找最优解。
|
3月前
|
机器学习/深度学习 算法 Java
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法,包括它们的伪代码描述、Java源代码实现、时间效率分析,并展示了算法的测试用例结果,使读者对贪婪技术及其应用有了更深入的理解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
|
4月前
|
存储 传感器 算法
|
4月前
|
机器学习/深度学习 人工智能 算法
|
5月前
|
算法 Java
Java数据结构与算法:贪心算法之最小生成树
Java数据结构与算法:贪心算法之最小生成树
|
5月前
|
算法 C语言
数据结构与算法——最小生成树问题(什么是最小生成树、Prim算法、Kruskal算法)
数据结构与算法——最小生成树问题(什么是最小生成树、Prim算法、Kruskal算法)
30 0
|
6月前
|
人工智能 算法
一些算法的复习(最短路径、最小生成树、dp)
一些算法的复习(最短路径、最小生成树、dp)
|
6月前
|
算法
最小生成树算法
最小生成树算法
|
7天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
4天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。