【算法】Prim最小生成树算法

目录

一、思想

二、代码


在阅读本文前推荐优先食用:

【算法】Kruskal最小生成树算法-CSDN博客icon-default.png?t=O83Ahttps://blog.csdn.net/Eristic0618/article/details/143312482?spm=1001.2014.3001.5501

一、思想

Kruskal算法基于边的选择,因此更适用于稀疏图。而对于基于选择节点的Prim最小生成树算法,其更适用于边数量远大于节点数量的稠密图

Prim算法的思想如下:

  • 选择一个起始点作为连通块的一部分,更新其他节点距离连通块的最短距离
  • 每次选择离连通块距离最短的节点,将其加入连通块,并更新其他节点距离连通块的最短距离
  • 重复上一步,直到所有节点都包含在连通块内,构成一颗最小生成树

例如下面这个图:

我们以1号节点作为起始节点加入连通块,其他所有节点距离连通块的距离初始化为最大值

更新其他节点距离连通块的最短距离

从所有没有被加入连通块的节点中,找出离连通块距离最短的节点(此处为V3),加入连通块

更新其他节点距离连通块的最短距离,因为V3是新加入连通块的节点,所以实际上只需要判断其他未加入节点距离V3的距离是否小于自己原来的最短距离即可

继续找距离最短节点,此处V4和V6距离连通块的距离都为4,说明最小生成树不一定是唯一的。此处我们选择V4,将其加入连通块并更新距离

V6距离连通块最近,将V6加入连通块并更新距离

V2最近,将V2加入连通块并更新距离

最后是V5

所有节点都被加入连通块后,我们就得到了图中的最小生成树


二、代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define INF 0x3f3f3f3f
using namespace std;

#define N 510
#define M 1000010

int	n, m;
int dist[N]; //节点到连通块的最短距离 
int g[N][N]; //邻接矩阵
bool st[N];  //判断某节点是否在连通块中 

int Prim()
{
	memset(dist, 0x3f, sizeof dist); //初始化dist数组 
	dist[1] = 0;
	
	int res = 0; //最小生成树边权和 
	for(int i = 0; i < n; i++) //起始节点已加入连通块,遍历剩余n-1个节点
	{
		int t = -1; //标记当前遍历中与连通块距离最小的节点编号 
		for(int j = 1; j <= n; j++) //遍历所有节点 
		{
			if(!st[j] && (t == -1 || dist[t] > dist[j])) //节点j不在连通块中 且 当前未选择节点或节点j距离比节点t更短
				t = j; //更新t 
		}
		//经过循环,此时节点t就是 剩余所有不属于连通块中的节点 中 距离连通块最短的节点 
		if(dist[t] > INF / 2) return INF; // dist[t]仍为最大值,说明剩余节点不与连通块相连
		
		res += dist[t]; //将t距离连通块的距离加入边权和 
		
		for(int j = 1; j <= n; j++)
		{
			dist[j] = min(dist[j], g[t][j]); //更新剩余节点到连通块的最短距离 
		}
		
		st[t] = true; //将节点t加入连通块 
	}
	return res;
}

void solve()
{
	cin >> n >> m;
	
	memset(g, 0x3f, sizeof g); //所有权重全部初始化为最大值 
	for(int i = 0;i < m; i++)
	{
		int a, b, w;
		cin >> a >> b >> w;
		g[a][b] = g[b][a] = min(g[a][b], w); //无向图and可能存在重边 
	}
	
	int ret = Prim();
	
	if(ret == INF) cout << "impossible" << endl;
	else cout << ret << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
    return 0;
}

完.

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CPU用户时间百分比

在计算机系统中&#xff0c;"CPU用户时间百分比&#xff08;CPU User Time&#xff09;"是一个性能监控指标&#xff0c;它描述了CPU在用户模式下执行的累积时间与总的CPU时间的比例。这个指标可以帮助我们了解系统在执行用户态程序时的负载情况。下面是一些关于CPU用…

java-智能识别车牌号_基于spring ai和开源国产大模型_qwen vl

用大模型做车牌号识别&#xff0c;最简单高效 在Java场景中&#xff0c;java识别车牌号的需求非常普遍。过去&#xff0c;我们主要依赖OCR等传统方法来实现java识别车牌号&#xff0c;但这些方法的效果往往不稳定。随着技术的发展&#xff0c;现在有了更先进的解决方案——大模…

IoTDB时序数据库使用

简介 Apache IoTDB 是一款低成本、高性能的物联网原生时序数据库。它可以解决企业组建物联网大数据平台管理时序数据时所遇到的应用场景复杂、数据体量大、采样频率高、数据乱序多、数据处理耗时长、分析需求多样、存储与运维成本高等多种问题。 IoTDB官网 1. 连接数据库 官方…

Android camera2

一、序言 为了对阶段性的知识积累、方便以后调查问题&#xff0c;特做此文档&#xff01; 将以camera app 使用camera2 api进行分析。 (1)、打开相机 openCamera (2)、创建会话 createCaptureSession (3)、开始预览 setRepeatingRequest (4)、停止预览 stopRepeating (5)、关闭…

【设计模式系列】组合模式(十二)

目录 一、什么是组合模式 二、组合模式的角色 三、组合模式的典型应用 四、组合模式在Mybatis SqlNode中的应用 4.1 XML映射文件案例 4.2 Java代码使用案例 一、什么是组合模式 组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;其核…

【Linux 27】HTTP 协议中的 cookie 和 session

文章目录 &#x1f308;一、Cookie 的相关概念⭐ 1. Cookie 的概念⭐ 2. Cookie 的工作原理⭐ 3. Cookie 的分类⭐ 4. Cookie 的用途⭐ 5. Cookie 设置的基本格式⭐ 6. Cookie 设置时的注意事项⭐ 7. Cookie 的生命周期⭐ 8. Cookie 的安全性问题 &#x1f308; 二、Session 的…

flask小白注意了!当我们通过IP:5000的形式无法访问服务时,大概率问题出在这里!!!

我们在使用Flask开发应用时&#xff0c;通过127.0.0.1:5000 或者localhost:5000访问应用正常&#xff0c;但是当使用本机ip 访问时却出现了 无法访问此网站的错误&#xff0c;如下图&#xff1a; 按照图中的提示&#xff0c;检查了代理服务器和防火墙&#xff08;包括关闭了电脑…

Excel:vba实现批量插入图片

实现的效果&#xff1a; 实现的代码&#xff1a; Sub InsertImageNamesAndPictures()Dim PicPath As StringDim PicName As StringDim PicFullPath As StringDim RowNum As IntegerDim Pic As ObjectDim Name As String 防止表格里面有脏数据Cells.Clear 遍历工作表中的每个图…

余承东放话,华为最强旗舰马上就来,国产系统迎来关键一战

Mate 70系列要来了&#xff01; 10月&#xff0c;OPPO、小米、vivo、荣耀等一众手机厂商都抛出了年度旗舰手机&#xff0c;机圈大战闹得沸沸扬扬。那边厢&#xff0c;低调的华为也终于传来了激动人心的消息&#xff1a;Mate 70系列要来了&#xff01;余承东在微博发文称Mate 7…

Linux之实战命令65:hostnamectl应用实例(九十九)

简介&#xff1a; CSDN博客专家、《Android系统多媒体进阶实战》一书作者 新书发布&#xff1a;《Android系统多媒体进阶实战》&#x1f680; 优质专栏&#xff1a; Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a; 多媒体系统工程师系列【…

电力电子计算部分

1.瞬时功率 任何装置、设备的瞬时功率都是通过加在其上的电压及其流过的电流计算的&#xff0c;表达式为&#xff1a; 瞬时功率表达式适用于任何装置、设备或电路。瞬时功率是一个时变的量。 2.能量 能量或功&#xff0c;是对瞬时功率在时间上的积分。在时间t1到t2内所有吸收…

使用QtWebEngine的Mac应用如何发布App Store

前言 因为QtWebEngine时第三方包,苹果并不直接支持进行App Store上签名和发布,所以构建和发布一个基于使用QtWebEngine的应用程序并不容易,这里我们对Qt 5.8稍微做一些修改,以便让我们的基于QtWeb引擎的应用程序并让签名能够得到苹果的许可。 QtWebEngine提供了C++和Qml的…

《计算机网络》课后探研题书面报告_了解网络设备

引言 计算机网络自20世纪60年代首次提出以来&#xff0c;已经发展成为现代社会不可或缺的基础设施。最早的计算机网络仅用于连接少数设备&#xff0c;用于简单的数据传递与共享。随着互联网技术的迅速普及和计算机技术的飞跃发展&#xff0c;网络的规模和复杂性不断增加&#…

【用Java学习数据结构系列】泛型上界与通配符上界

看到这句话的时候证明&#xff1a;此刻你我都在努力 加油陌生人 个人主页&#xff1a;Gu Gu Study 专栏&#xff1a;用Java学习数据结构系列 喜欢的一句话&#xff1a; 常常会回顾努力的自己&#xff0c;所以要为自己的努力留下足迹 喜欢的话可以点个赞谢谢了。 作者&#xff…

ssm校园线上订餐系统的设计与实现+vue

系统包含&#xff1a;源码论文 所用技术&#xff1a;SpringBootVueSSMMybatisMysql 免费提供给大家参考或者学习&#xff0c;获取源码看文章最下面 需要定制看文章最下面 目 录 摘 要 I 目 录 III 第1章 绪论 1 1.1 研究背景 1 1.2目的和意义 1 1.3 论文研究内容 1 …

软设师知识点-计算机网络

计算机网络 在一台安装好TCP/IP协议的计算机上&#xff0c;当网络连接不可用时&#xff0c;为了测试编写好的网络程序&#xff0c;通常使用的目的主机IP地址127.0.0.1&#xff08;本地回送地址&#xff09; *网络设备 物理层的互传设备&#xff1a;中继器(用于扩展局域网网段…

【339】基于springboot的新能源充电系统

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;新能源充电系统的设计与实现 摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解…

Spring Boot2(Spring Boot 的Web开发 springMVC 请求处理 参数绑定 常用注解 数据传递 文件上传)

SpringBoot的web开发 静态资源映射规则 总结&#xff1a;只要静态资源放在类路径下&#xff1a; called /static (or /public or /resources or //METAINF/resources 一启动服务器就能访问到静态资源文件 springboot只需要将图片放在 static 下 就可以被访问到了 总结&…

#Jest进阶知识:整合 webpack 综合练习

这一小节&#xff0c;我们来做一个综合的练习&#xff0c;该练习会整合&#xff1a; typescriptwebpackjest 准备工作 首先创建项目目录&#xff0c;通过 npm init -y 进行初始化。 整个项目我们打算使用 typescript 进行开发&#xff0c;因此需要安装 typescript npm i t…

可以将题库文档做成答题考试的小程序

&#x1f4a5;轻松构建个人题库&#xff0c;开启高效在线答题体验&#xff01;&#x1f4af; &#x1f389;梦想拥有个性化题库&#xff0c;随时随地进行在线练习吗&#xff1f;“土著刷题”小程序正是为此而生&#xff0c;助你实现愿望&#xff01;✨ &#x1f31f;这款小程序…