最小生成树 — Prim算法

同Kruskal算法一样,Prim算法也是最小生成树的算法,但与Kruskal算法有较大的差别。
Prim算法整体是通过“解锁” + “选中”的方式,点 -> 边 -> 点 -> 边
因为是最小生成树,所以针对的也是无向图,所以可以随意选取一个点作为进入点,通过解锁这个点,可以获得从这个点出去的所有边,在通过这些边中权重最小的边解锁其他的点。如此反复。直到最小生成树的形成。
如图所示:
左侧为原始图,从a点出发(哪个点都可以,假设从a),解锁了a点(解锁的点画圈),并且解锁了从a点直接出发权重为1,2,9的三条边(边解锁为虚线),根据权重选择1的边(选择具体边改颜色)。并解锁了b点。
在这里插入图片描述
通过解锁的b点,可解锁权重1,3,4,9的边,此时bd边的权重最小为1,所以解锁了d的点。
在这里插入图片描述
解锁d后,d直接出来的边4也会进行解锁。再次选择权重较小的为2,但是此时d已经解锁过了,所以不考虑2,再次选择be为3的边解锁。
在这里插入图片描述
此时解锁后图形如上面所示,e点解锁后会解锁权重6、7的边。
在这里插入图片描述
此时所有的边都已经解锁,选择权重小的边,并且不会形成环的点,进行解锁。
最终去掉所有没被选择的边,剩余的就是最小生成树。
在这里插入图片描述
总结

  1. 最小生成树是要用最小距离接所有可达的点。
  2. 所以,随机的每一个点,在获取这个点所有的边中选取权重最小的 那一条边,组织起来就一定会是最小生成树组成的答案。

代码实现
基于上面图解是代码实现。点 > 边 -> 点 -> 边的解锁方式。
最外层的for循环可防“森林”。 a -> b c ->d e->f,a可以找到b,c可以找到d, e可以找到f。但是a c e之间互相没关系。

public static class EdgeComparator implements Comparator<Edge> {@Overridepublic int compare(Edge o1, Edge o2) {return o1.weight - o2.weight;}}public static Set<Edge> primMST(Graph graph) {//放入PriorityQueue中,并根据边的权重进行排序PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());//解锁的点Set<Node> setNodes = new HashSet<>();//构成最小生成树的所有边Set<Edge> 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;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/92283.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MySql011——检索数据:过滤数据(使用正则表达式)

前提&#xff1a;使用《MySql006——检索数据&#xff1a;基础select语句》中创建的products表 一、正则表达式介绍 关于正则表达式的介绍大家可以看我的这一篇博客《Java038——正则表达式》&#xff0c;这里就不再累赘。 二、使用MySQL正则表达式 2.1、基本字符匹配 检索…

Java版企业电子招投标采购系统源码之首页设计 tbms

​ 功能描述 1、门户管理&#xff1a;所有用户可在门户页面查看所有的公告信息及相关的通知信息。主要板块包含&#xff1a;招标公告、非招标公告、系统通知、政策法规。 2、立项管理&#xff1a;企业用户可对需要采购的项目进行立项申请&#xff0c;并提交审批&#xff0c;查…

照耀国产的星火,再度上新!

国产之光&#xff0c;星火闪耀 ⭐ 新时代的星火⭐ 多模态能力⭐ 图像生成与虚拟人视频生成⭐ 音频生成与OCR笔记收藏⭐ 助手模式更新⭐ 插件能力⭐ 代码能力⭐ 写在最后 ⭐ 新时代的星火 在这个快速变革的时代&#xff0c;人工智能正迅猛地催生着前所未有的革命。从医疗到金融…

CEC2013(MATLAB):遗传算法(Genetic Algorithm,GA)求解CEC2013的28个函数

一、遗传算法GA 遗传算法&#xff08;Genetic Algorithm&#xff0c;GA&#xff09;起源于对生物系统所进行的计算机模拟研究&#xff0c;是一种随机全局搜索优化方法&#xff0c;它模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象&#xff0c;从任…

easyx图形库基础4:贪吃蛇

贪吃蛇 一实现贪吃蛇&#xff1a;1.绘制网格&#xff1a;1.绘制蛇&#xff1a;3.控制蛇的默认移动向右&#xff1a;4.控制蛇的移动方向&#xff1a;5.生成食物6.判断蛇吃到食物并且长大。7.判断游戏结束&#xff1a;8.重置函数&#xff1a; 二整体代码&#xff1a; 一实现贪吃蛇…

【0基础学爬虫】爬虫基础之网络请求库的使用

大数据时代&#xff0c;各行各业对数据采集的需求日益增多&#xff0c;网络爬虫的运用也更为广泛&#xff0c;越来越多的人开始学习网络爬虫这项技术&#xff0c;K哥爬虫此前已经推出不少爬虫进阶、逆向相关文章&#xff0c;为实现从易到难全方位覆盖&#xff0c;特设【0基础学…

安卓13解决链接问题

作为Android用户&#xff0c;你可能已经注意到了一个问题——Android 13不再支持PPTP协议。但请别担心&#xff0c;作为一家专业的代理供应商&#xff0c;我们将与你分享解决方案&#xff0c;让你轻松解决L2TP问题&#xff0c;享受到高水平的连接体验。本文将为你提供实用的操作…

什么是浮动(float)?如何清除浮动?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 浮动&#xff08;Float&#xff09;和清除浮动⭐ 浮动的使用⭐ 清除浮动1. 空元素法&#xff08;Empty Element Method&#xff09;2. 使用 Clearfix Hack3. 使用 Overflow ⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发…

微服务与Nacos概述-5

引入OpenFeign 添加依赖&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId> </dependency> <dependency><groupId>com.alibaba.cloud</groupId>…

山东布谷科技直播软件开发WebRTC技术:建立实时通信优质平台

在数字化的时代&#xff0c;实时通信成为了人们远程交流的主要方式&#xff0c;目前市场上也出现了很多带有实时通信交流的软件&#xff0c;实时通信符合人们现在的需求&#xff0c;所以在直播软件开发过程中&#xff0c;开发者也运用了实时通信技术为直播软件加入了实时通信的…

【芯片前端】auto_testbench的大版本升级——加入简单预期与自动比对

前言 前文提要&#xff1a; 【芯片前端】一键生成简易版本定向RTL验证环境的脚本——auto_verification_rtl脚本_尼德兰的喵的博客-CSDN博客 【芯片前端】可能是定向验证的巅峰之作——auto_testbench_autotestbench_尼德兰的喵的博客-CSDN博客 工具路径&#xff1a; auto…

Vue.js2+Cesium1.103.0 九、淹没分析效果

Vue.js2Cesium1.103.0 九、淹没分析效果 Demo <template><divid"cesium-container"style"width: 100%; height: 100%;"><spanid"button"style"position: absolute; right: 50px; top: 50px; z-index: 999; font-size: 24px…

Gitlab-第四天-CD到k8s集群的坑

一、.gitlab-ci.yml #CD到k8s集群的 stages: - deploy-test build-image-deploy-test: stage: deploy-test image: bitnami/kubectl:latest # 使用一个包含 kubectl 工具的镜像 tags: - k8s script: - ls -al - kubectl apply -f deployment.yaml # 根据实际情况替换…

SpringBoot请求响应

简单参数 1. 原始方式获取请求参数 Controller方法形参中声明httpServletRequest对象 调用对象的getParameter参数名 RestController public class RequestController {RequestMapping("/simpleParam")public String simpleParam(HttpServletRequest request){Strin…

理解 Go 中的切片:append 操作的深入分析(篇2)

理解 Go 语言中 slice 的性质对于编程非常有益。下面&#xff0c;我将通过代码示例来解释切片在不同函数之间传递并执行 append 操作时的具体表现。 本篇为第 2 篇&#xff0c;当切片的容量 cap 不够时 func main() {// slice1 当前长度为 3&#xff0c;容量大小也为 3slice1 :…

学习笔记整理-面向对象-05-内置对象

一、内置对象 1. 什么是包装类 Number()、String()和Boolean()分别是数字、字符串、布尔值的"包装类"。包装类的目的就是为了让基本类型值可以从它们的构造函数的prototype上获得方法。Number()、String()和Boolean()的实例都是object类型&#xff0c;它们的Primit…

Python是什么?它有什么用途?

Python是什么&#xff1f; Python是一门具有优雅和简洁语法的高级编程语言。它由荷兰程序员Guido van Rossum创造并于上世纪90年代初发布。Python的设计理念强调可读性和清晰性&#xff0c;使得代码编写变得轻松且容易理解。这门语言以其独特的缩进方式来标记代码块&#xff0…

7.利用matlab完成 符号方阵的特征值分解和 符号矩阵的奇异值分解 (matlab程序)

1.简述 &#xff08;1&#xff09;特征值分解&#xff1a;函数eig 格式&#xff1a;[V,D] eig(A) %计算A的特征值对角阵D和特征向量V&#xff0c;使AVVD成立。 注意&#xff1a;特征值分解时&#xff0c;使用eig&#xff0c;矩阵A必须是方阵。 A [0 1;1 1]; [V,D] ei…

【javaweb】学习日记Day1 - HTML CSS入门

目录 一、图片标签 ① 绝对路径 1.绝对磁盘路径 2.绝对网络路径 ② 相对路径 &#xff08;推荐&#xff09; 二、标题标签 三、水平线标签 四、标题样式 1、CSS引入样式 ① 行内样式 ② 内嵌样式 ③ 外嵌样式 2、CSS选择器 ① 元素选择器 ② id选择器 ③…

06 - 文件的差异和恢复

查看所有文章链接&#xff1a;&#xff08;更新中&#xff09;GIT常用场景- 目录 文章目录 1. 文件的差异2. 文件的恢复 工作区&#xff1a;本地进行修改的code 暂存区&#xff1a;执行了 git add <filename> 命令之后 版本库&#xff1a;执行了 git commit <...>…