【算法基础实验】图论-最小生成树-Prim的即时实现

理论知识

Prim算法是一种用于计算加权无向图的最小生成树(MST, Minimum Spanning Tree)的贪心算法。最小生成树是一个连通的无向图的子图,它包含所有的顶点且总权重最小。Prim算法从一个起始顶点开始,不断将权重最小的边加入生成树,直到包含图中的所有顶点为止。

关键思想

  • 起点选择:从任意一个顶点开始,将其标记为已访问。
  • 贪心选择:从已访问的顶点集合中,选择一条连接到未访问顶点的权重最小的边,将该边加入MST。
  • 更新过程:重复选择和标记过程,直到所有顶点都包含在MST中。

时间复杂度

  • 使用简单的实现(如使用无序数组)时,Prim算法的时间复杂度为O(V^2)。
  • 使用优先队列(如最小堆)优化时,时间复杂度可以降低到O(E log V),其中E是边的数量,V是顶点的数量。

算法流程

要改进 LazyPrimMST,可以尝试从优先队列中删除失效的边,这样优先队列就只含有树顶点和非树顶点之间的横切边。关键在于,我们感兴趣的只是连接树顶点和非树顶点中权重最小的边。当我们将顶点 v 添加到树中时,对于每个非树顶点 w 产生的变化只可能使得 w 到最小生成树的距离更近了,如图所示。简而言之,我们不需要在优先队列中保存所有从 w 到树顶点的边——而只需要保存其中权重最小的那条,在将 v 添加到树中后检查是否需要更新这条权重最小的边(因为v-w 的权重可能更小)。我们只需遍历 v 的邻接链表就可以完成这个任务。换句话说,我们只会在优先队列中保存每个非树顶点 w 的一条边:将它与树中的顶点连接起来的权重最小的那条边。将 w 和树的顶点连接起来的其他权重较大的边迟早都会失效,所以没必要在优先队列中保存它们。

PrimMST 类使用了索引优先队列实现的 Prim 算法。它将 LazyPrimMST 中的 marked[] 和 mst[] 替换为两个顶点索引的数组edgeTo[] 和 distTo[],它们具有如下性质。

  • 如果顶点 v 不在树中但至少含有一条边和树相连,那么 edgeTo[v] 是将 v 和树连接的最短边,distTo[v] 为这条边的权重。
  • 所有这类顶点 v 都保存在一条索引优先队列中,索引 v 关联的值是 edgeTo[v]的边的权重。

这些性质的关键在于优先队列中的最小键即是权重最小的横切边的权重,而和它相关联的顶点 v 就是下一个将被添加到树中的顶点。marked[] 数组已经没有必要了,因为判断条件 !marked[w] 等价于 distTo[w] 是无穷的(且 edgeTo[w] 为 null)。要维护这些数据结构,PrimMST 会从优先队列中取出一个顶点 v 并检查它的邻接链表中的每条边 v-w。如果 w 已经被标记过,那么这条边就已经失效了;如果 w 不在优先队列中或者 v-w 的权重小于目前已知的最小值 edgeTo[w],代码会更新数组,将 v-w 作为将 w 和树连接的最佳选择。
在这里插入图片描述

以下流程是基于本实验数据描绘的处理轨迹图:

解释流程图有助于对代码的理解,理解核心原理
关注数据的组织方式

在节点中:

  • 白色圆形是树节点,灰色圆形是非树节点,

在边中:

  • 红线代表当前加入优先队列的边

  • 粗红线代表队列中权重最小的边

  • 粗黑线代表已经纳入MST中的边

  • 灰色线代表可以被其他线平替的线

💡 也就是说当我们遍历到一个非树节点时,需要判断当前遍历到的边和该非树节点已经被树遍历到的边相比,哪个最小,不是最小的都会被标记为灰色。如何记录树到非树节点的距离呢?是使用ditsTo[非树节点]这个数组来完成的

在Index列中:

  • 红色数字代表节点已经被遍历
  • 黑色数字代表该节点已经被纳入MST中了,marked置为True
  • 灰色数字表示节点尚未被遍历

💡 遍历动作一定是由一个新晋的树节点发起的
当树节点遍历到了另一个树节点则直接跳过,根据切分定理,我们要遍历的是非树节点

在edgeTo列中:

  • 黑色数字代表树节点
  • 灰色数字代表非树节点
  • 当边的两个节点都加入MST后,连接符号“-”由红色变为黑色

💡 新加入的边一定包含树节点,另外一端肯定要指向某个非树节点,非树节点是灰色的数字,这里的灰色数字一定是跟index值保持一致的,所以我们可以根据非树节点的编号作为索引来管理PQ队列,我们的处理核心是与树直连的非树节点

在distTo列中:

  • 红色代表尚未确定边是否可以纳入MST
  • 黑色代表确定该边已经加入了MST,并且已经从PQ中删除
  • 红色箭头代表当前PQ中值最小的边

在这里插入图片描述

实验数据

8
16
4 5 0.35
4 7 0.37
5 7 0.28
0 7 0.16
1 5 0.32
0 4 0.38
2 3 0.17
1 7 0.19
0 2 0.26
1 2 0.36
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93

代码实现

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;public class myPrimMST {private myEdge[] edgeTo;private double[] distTo;private boolean[] marked;private myIndexMinPQ<Double> pq;private double totalWeight;public myPrimMST(myEdgeWeightedGraph G){edgeTo = new myEdge[G.V()];distTo = new double[G.V()];marked = new boolean[G.V()];pq = new myIndexMinPQ<>(G.V());for(int v=0;v<G.V();v++)distTo[v] = Double.POSITIVE_INFINITY;distTo[0] = 0.0;pq.insert(0,0.0);while(!pq.isEmpty())visit(G,pq.delMin());}private void visit(myEdgeWeightedGraph G, int v){marked[v] = true;for(myEdge e: G.adj(v)){int w = e.other(v);if(marked[w]) continue;if(e.weight()<distTo[w]){edgeTo[w] = e;distTo[w] = e.weight();if(pq.contains(w)) pq.change(w,distTo[w]);else pq.insert(w,distTo[w]);}}}public Iterable<myEdge> edges(){myBag<myEdge> mst = new myBag<myEdge>();for(int v=1;v< edgeTo.length;v++)mst.add(edgeTo[v]);return mst;}public double weight(){totalWeight = 0.00;for(myEdge e:edges()){totalWeight +=e.weight();StdOut.println(totalWeight);}return totalWeight;}public static void main(String[] args){In in = new In(args[0]);myEdgeWeightedGraph G = new myEdgeWeightedGraph(in);myPrimMST mst = new myPrimMST(G);for(myEdge e:mst.edges())StdOut.println(e);StdOut.printf("%.5f\n", mst.weight());}
}

代码详解

类定义和成员变量

java复制代码
public class myPrimMST {private myEdge[] edgeTo;  // 记录最小生成树的边private double[] distTo;  // 记录从树到该顶点的最小权重边private boolean[] marked; // 记录顶点是否在树中private myIndexMinPQ<Double> pq; // 索引优先队列,帮助找到最小权重的边private double totalWeight; // 最小生成树的总权重
  • edgeTo:存储每个顶点的连接边,形成MST。
  • distTo:存储到每个顶点的最小边权重。
  • marked:标记哪些顶点已经被包括在MST中。
  • pq:索引优先队列,用于动态查找最小边。

构造函数

java复制代码
public myPrimMST(myEdgeWeightedGraph G) {edgeTo = new myEdge[G.V()];distTo = new double[G.V()];marked = new boolean[G.V()];pq = new myIndexMinPQ<>(G.V());for(int v=0; v<G.V(); v++)distTo[v] = Double.POSITIVE_INFINITY;distTo[0] = 0.0;pq.insert(0, 0.0);while(!pq.isEmpty())visit(G, pq.delMin());
}
  • 初始化:edgeTodistTomarkedpq
  • 设置初始顶点的距离为 0 并将其插入优先队列。
  • while 循环:每次从优先队列中删除权重最小的顶点,并调用 visit 方法处理该顶点。

visit方法

java复制代码
private void visit(myEdgeWeightedGraph G, int v) {marked[v] = true;for(myEdge e: G.adj(v)) {int w = e.other(v);if(marked[w]) continue;if(e.weight() < distTo[w]) {edgeTo[w] = e;distTo[w] = e.weight();if(pq.contains(w)) pq.change(w, distTo[w]);else pq.insert(w, distTo[w]);}}
}
  • visit 方法标记顶点 v 为已访问。
  • 遍历所有与 v 连接的边,并检查另一端顶点 w 是否已在MST中。
  • 如果找到更小的连接权重边,则更新 edgeTodistTo,并在优先队列中更新或插入 w

edges方法和weight方法

java复制代码
public Iterable<myEdge> edges() {myBag<myEdge> mst = new myBag<>();for(int v=1; v<edgeTo.length; v++)mst.add(edgeTo[v]);return mst;
}public double weight() {totalWeight = 0.00;for(myEdge e : edges())totalWeight += e.weight();return totalWeight;
}
  • edges() 方法返回MST中的所有边。
  • weight() 方法计算并返回MST的总权重。

main方法

java复制代码
public static void main(String[] args) {In in = new In(args[0]);myEdgeWeightedGraph G = new myEdgeWeightedGraph(in);myPrimMST mst = new myPrimMST(G);for(myEdge e : mst.edges())StdOut.println(e);StdOut.printf("%.5f\n", mst.weight());
}
  • 从文件中读取图数据并构建 myEdgeWeightedGraph 对象 G
  • 使用 myPrimMST 类计算最小生成树 mst
  • 打印最小生成树的所有边和总权重。

总结

Prim算法通过逐步构建最小生成树,并利用优先队列来高效地选择最小权重的边。在这段代码中,myPrimMST 类实现了Prim算法,通过维护一个最小优先队列来管理尚未包括在MST中的顶点,从而动态调整生成树并计算其总权重。

实验步骤

C:\Users\xyz\IdeaProjects\algrithoms\src>javac myPrimMST.java 
C:\Users\xyz\IdeaProjects\algrithoms\src>java myPrimMST data\tinyEWD.txt     
2-7 0.34
6-2 0.40
7-5 0.28
5-4 0.35
1-3 0.29
0-2 0.26
5-1 0.32
2.24000

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

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

相关文章

Excel表格添加趋势线_数据拟合

一个曲线通过补偿算法拟合为另一个曲线&#xff0c;通常可以通过多种数学和计算技术实现。这里也可以通过Excel表格添加趋势线&#xff0c;然后对趋势线进行拟合&#xff0c;得到趋势预测公式来达到数据补偿。 通过把你需要的数据导入到Excel表格中。 通过 “ 插入 ” --> “…

谷歌云AI新作:CROME,跨模态适配器高效多模态大语言模型

CROME: Cross-Modal Adapters for Efficient Multimodal LLM https://arxiv.org/pdf/2408.06610 Abstract 研究对象&#xff1a;Multimodal Large Language Models (MLLMs) demonstrate remarkable imagelanguage capabilities, but their widespread use faces challenges in…

论坛 推荐

畅议论坛&#xff1a;http://udbbs.top/http://udbbs.top/

查看U盘的具体信息,分区表格式、实际容量和分区状态

查看U盘的具体信息&#xff0c;分区表格式、实际容量和分区状态 前言&#xff1a; 利用windows自带的命令行窗口就可以 1、使用命令提示符查看MBR和GPT分区类型 &#xff08;1&#xff09;按“Windows R”键&#xff0c;在弹出的运行对话框中输入“diskpart”&#xff0c;并按…

游戏开发设计模式之工厂模式

目录 简单工厂模式&#xff08;Simple Factory Pattern&#xff09; 应用场景&#xff1a; 优缺点&#xff1a; 工厂方法模式&#xff08;Factory Method Pattern&#xff09; 应用场景&#xff1a; 优缺点&#xff1a; 抽象工厂模式&#xff08;Abstract Factory Patte…

碰撞检测 | 基于ROS Rviz插件的多边形碰撞检测仿真平台

目录 0 专栏介绍1 基于多边形的碰撞检测2 碰撞检测仿真平台搭建2.1 多边形实例2.2 外部服务接口2.3 Rviz插件化 3 案例演示3.1 功能介绍3.2 绘制多边形 0 专栏介绍 &#x1f525;课设、毕设、创新竞赛必备&#xff01;&#x1f525;本专栏涉及更高阶的运动规划算法轨迹优化实战…

Debian12安装tomcat8

jdk安装 安装Tomcat前需要先安装JDK&#xff0c;JDK安装参见&#xff1a; https://zhengshaoshaolin.blog.csdn.net/article/details/141407600 tomcat安装 1、下载安装 Apache Tomcat 访问官方 Apache Tomcat 下载页面&#xff0c;获取最新的二进制文件 或者使用如下的 wg…

Spring DI 数据类型—— set 方法注入

首先新建项目&#xff0c;可参考 初识IDEA、模拟三层--控制层、业务层和数据访问层 一、spring 环境搭建 &#xff08;一&#xff09;pom.xml 导相关坐标 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.or…

【Win开发环境搭建】Redis与可视化工具详细安装与配置过程

&#x1f3af;导读&#xff1a;本文档提供了Redis的简介、安装指南、配置教程及常见操作方法。包括了安装包的选择与配置环境变量的过程&#xff0c;详细说明了如何通过修改配置文件来设置密码和端口等内容。同时&#xff0c;文档还介绍了如何使用命令行工具连接Redis&#xff…

ArcGIS如何将投影坐标系转回为地理坐标系

有时候两个数据&#xff0c;一个为投影坐标系&#xff0c;另一个为地理坐标系时&#xff0c;在GIS软件中位置无法叠加到一起&#xff0c;这需要将两个或多个数据的坐标系统一&#xff0c;可以直接将地理坐标系的数据进行投影&#xff0c;或将投影坐标系转为地理坐标系。下面介绍…

在使用Simulink进行FOC(Field-Oriented Control,场向量控制)仿真时,如果遇到波形丢失精度的问题,该这么解决

&#x1f3c6;本文收录于《CSDN问答解惑-专业版》专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收…

【Qt】输入类控件QLineEdit

目录 输入类控件QLineEdit 例子&#xff1a;录入个人信息 例子&#xff1a;使用正则表达式验证输入框的数据 例子&#xff1a;验证俩次输入密码一致 例子&#xff1a;切换显示代码 输入类控件QLineEdit QLineEdit 用来表示单行输入框&#xff0c;可以输入一段文本&#xf…

网络安全入门教程(非常详细)从零基础入门到精通_网路安全 教程

前言 1.入行网络安全这是一条坚持的道路&#xff0c;三分钟的热情可以放弃往下看了。2.多练多想&#xff0c;不要离开了教程什么都不会了&#xff0c;最好看完教程自己独立完成技术方面的开发。3.有时多百度&#xff0c;我们往往都遇不到好心的大神&#xff0c;谁会无聊天天给…

QT-五子棋游戏

QT-五子棋游戏 一、演示效果二、核心代码三、下载链接 一、演示效果 二、核心代码 #include "GameModel.h" #include <time.h> #include <stdlib.h>GameModel::GameModel(){}void GameModel::startGame(GameType type){gameType type;//初始化棋盤game…

如何备份电脑数据到U盘?防止数据丢失从备份开始

在数字化时代&#xff0c;数据备份已经成为我们日常生活中不可或缺的一部分。电脑中的数据&#xff0c;无论是工作文件、学习资料&#xff0c;还是珍贵的照片和视频&#xff0c;都是我们生活中重要的资产。为了防止数据丢失&#xff0c;将数据备份到U盘是一个简单且实用的方法。…

【IEEE独立出版】第三届人工智能、物联网和云计算技术国际会议(AIoTC 2024,9月13-15)

第三届人工智能、物联网与云计算技术国际会议(AIoTC 2024)将于2024年9月13日-15日在中国武汉举行。 本次会议由华中师范大学伍伦贡联合研究院与南京大学联合主办、江苏省大数据区块链与智能信息专委会承办、江苏省概率统计学会、江苏省应用统计学会、Sir Forum、南京理工大学、…

《重温JavaScript五子棋小游戏》

目录 全部运行代码&#xff1a;五子棋游戏的基本步骤&#xff1a;代码剖析&#xff1a;1. 初始化游戏界面2. 管理游戏状态3. 玩家交互4. 电脑AI5. 胜负判定6. 游戏控制 本文通过实现一个基本的五子棋游戏&#xff0c;展示了如何使用HTML、CSS和JavaScript来构建一个简单的交互式…

GIS应用水平考试一级真题和答案分享~

2012年-2018年完整真题和答案 GIS应用水平考试资料分享https://docs.qq.com/doc/DRmxxaVhpbGJXSGho?u5295a88d71d8480d971da4e3334ee913

ES高级查询Query DSL查询详解、term术语级别查询、全文检索、highlight高亮

文章目录 ES高级查询Query DSLmatch_all返回源数据_source返回指定条数size分页查询from&size指定字段排序sort 术语级别查询term query术语查询terms query多术语查询range query范围查询exists queryids queryprefix query前缀查询wildcard query通配符查询fuzzy query模…

可视化大屏-实现自动滚动

一、背景&#xff1a;可视化大屏通常需要用到自动滚动的效果&#xff0c;本文主要采用的是vue-seamless-scroll组件来实现&#xff08;可参考官方文档&#xff09; 二、实现效果&#xff1a; 自动滚动 三、代码实现&#xff1a; 解题思路&#xff1a; 1.先安装依赖包 npm inst…