【算法基础:搜索与图论】3.5 求最小生成树算法(PrimKruskal)
文章目录
- 最小生成树介绍
- 朴素Prim算法
- 算法思路⭐
- 例题:858. Prim算法求最小生成树
- Kruskal算法
- 算法思路⭐
- 例题:859. Kruskal算法求最小生成树
最小生成树介绍
最小生成树
有关树的定义
生成子图:生成子图是从原图中选取部分节点以及这些节点之间的边所组成的图。生成子图中的所有节点和边都必须在原图中存在。
生成树:一个连通无向图的生成子图,同时要求是树。也即在图的边集中选择 n - 1 条,将所有顶点连通。
我们定义无向连通图的 最小生成树(Minimum Spanning Tree,MST)为边权和最小的生成树。
注意:只有连通图才有生成树,而对于非连通图,只存在生成森林。

朴素Prim算法
算法思路⭐
算法流程和 Dijkstra 算法非常相似。
Dijkstra 算法是用 t 更新其它点到起点的距离,而 Prim 用 t 更新其它点到 集合 的距离。

初始时各个点到集合的距离设置为 INF
循环 n 次,每次循环找到当前没在集合(集合就是最小生成树中节点的集合)且距离集合最近的节点。
将当前最近的节点 t 加入最小生成树中,然后使用 t 更新其它所有点(1~n)到集合之间的距离。
时间复杂度是: O ( n 2 + m ) O(n^2 + m) O(n2+m)
例题:858. Prim算法求最小生成树
https://www.acwing.com/problem/content/description/860/

注意:图中可能存在重边和自环。
重边是指连接同一对顶点的多条边。在处理重边的时候,我们应当只保留权重最小的那条边,其他的边应当被忽略。
自环是指从一个顶点指向自身的边。在最小生成树中,自环是没有意义的,因为我们可以直接忽略这样的边。实际上,对于 Prim 算法,我们应当在初始化阶段,忽略这些自环,即将其赋予无穷大的权重。
另外注意图是无向图,因此在建图时应当同时更新 g [ u ] [ v ] = g [ v ] [ u ] = M a t h . m i n ( g [ u ] [ v ] , w ) ; g[u][v] = g[v][u] = Math.min(g[u][v], w); g[u][v]=g[v][u]=Math.min(g[u][v],w);
import java.util.*;public class Main {static final int INF = 0x3f3f3f3f;public static void main(String[] args){Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(), m = scanner.nextInt();// 边数很多,所以使用邻接矩阵来存储int[][] g = new int[n + 1][n + 1];for (int i = 1; i <= n; ++i) {Arrays.fill(g[i], INF); // 对于自环也应该把距离设置成INF}for (int i = 0; i < m; ++i) {int u = scanner.nextInt(), v = scanner.nextInt(), w = scanner.nextInt();g[u][v] = g[v][u] = Math.min(g[u][v], w); // 是无向图,所以g[u][v] = g[v][u]都要更新}// 求最小生成树的树边权重之和int sum = prim(g);System.out.println(sum > INF / 2? "impossible": sum);}static int prim(int[][] g) {int n = g.length - 1, res = 0;boolean[] st = new boolean[n + 1]; // 存储每个点是否已经在生成树中了int[] dis = new int[n + 1]; // 存储其它点到当前最小生成树的距离Arrays.fill(dis, 0x3f3f3f3f); // 初始时距离都是 INFfor (int i = 0; i < n; ++i) {// 找到当前和集合最近且不在集合中的节点tint t = -1;for (int j = 1; j <= n; ++j) {if (!st[j] && (t == -1 || dis[t] > dis[j])) t = j;}if (i != 0 && dis[t] == INF) return INF; // 如果第一个节点没有把任何节点到最小生成树的距离变小// 将 t 加入最小生成树中去if (i != 0) res += dis[t]; // 注意判断树中的第一个节点是不会贡献边权和的st[t] = true;// 使用 t 到各个节点的距离 更新 各个节点到当前最小生成树的距离for (int j = 1; j <= n; ++j) {dis[j] = Math.min(dis[j], g[t][j]);}}return res;}
}
Kruskal算法
算法思路⭐
- 先将所有边按权重从小到大排序
- 枚举每条边 a ,b , w。如果 a, b 不连通就把这条边加入集合,即加入最小生成树。

如果使用 O ( m log m ) O(m\log m) O(mlogm) 的排序算法,并且使用 O ( m α ( m , n ) ) O(m\alpha(m, n)) O(mα(m,n)) 或 O ( m log n ) O(m\log n) O(mlogn) 的并查集,就可以得到时间复杂度为 O ( m log m ) O(m\log m) O(mlogm) 的 Kruskal 算法。
例题:859. Kruskal算法求最小生成树
https://www.acwing.com/activity/content/problem/content/925/

import java.util.*;public class Main {static final int INF = 0x3f3f3f3f, N = 100005;static int[] p = new int[N];static int n;public static void main(String[] args){Scanner scanner = new Scanner(System.in);n = scanner.nextInt();int m = scanner.nextInt();// 记录所有的 m 个边int[][] edges = new int[m][3];for (int i = 0; i < m; ++i) {edges[i][0] = scanner.nextInt();edges[i][1] = scanner.nextInt();edges[i][2] = scanner.nextInt();}int res = kruskal(edges);System.out.println(res == INF? "impossible": res);}static int find(int x) {if (x != p[x]) p[x] = find(p[x]);return p[x];}static int kruskal(int[][] edges) {// 按照权重升序排序Arrays.sort(edges, (a, b) -> a[2] - b[2]);Arrays.setAll(p, e -> e); // 初始化并查集int res = 0, cnt = 0;for (int[] edge: edges) {int x = edge[0], y = edge[1];if (find(x) != find(y)) {p[find(x)] = find(y);res += edge[2];cnt++;}}if (cnt < n - 1) return INF;return res;}
}
相关文章:
【算法基础:搜索与图论】3.5 求最小生成树算法(PrimKruskal)
文章目录 最小生成树介绍朴素Prim算法算法思路⭐例题:858. Prim算法求最小生成树 Kruskal算法算法思路⭐例题:859. Kruskal算法求最小生成树 最小生成树介绍 最小生成树 有关树的定义 生成子图:生成子图是从原图中选取部分节点以及这些节点…...
扩展Ceph集群实现高可用
...
代码随想录 DAY45
class Solution { public: int climbStairs(int n) { vector<int>dp(n1,0); dp[0]1; for(int j0;j<n;j){ for(int i1;i<2;i){ if(j>i) dp[j]dp[j-i]; } } return dp[n]; } }; 这个题还是说想清楚 这个因为有1和2 阶的情况 所以i就是从1开始遍历 然后小于等于…...
Centos报错:[Errno 12] Cannot allocate memory
执行一个脚本刚开始正常,后面就报[Errno 12] Cannot allocate memory 如果内存不足,可能需要增加交换内存。或者可能根本没有启用交换。可以通过以下方式检查您的交换: sudo swapon -s如果它为空,则表示您没有启用任何交换。添加 1GB 交换…...
手把手教你怎么写顺序表
目录 一、顺序表有什么功能? 二、实现顺序表的各个功能 1.前置准备 2.初始化顺序表 3.顺序表扩容 4.打印顺序表 5.增加顺序表成员 5.1尾增 5.2头增 6.删除顺序表中成员的内容 6.1尾删 6.2头删 7.查找成员 8.修改(替换) 9.插入(在目标位置插入成员) 10.定…...
FPGA中RAM的结构理解
FPGA中RAM的结构理解 看代码的过程中对RAM的结构不是很理解,搞脑子一片浆糊,反复推算,好不容易理清了思路,记录下来,防止忘记。开辟的RAM总容量为128bytes,数据的位宽为32位(即一个单元有32bit…...
家庭用的无线洗地机到底好不好用?2023洗地机品牌排行榜前十名
无线洗地机在清洁使用的时候非常便捷,多功能于一体能够轻轻松松就拖扫完全家,不需要多余的先扫再拖,浪费时间还非常的劳累。那么有什么靠谱并且质量也有保障的无线洗地机推荐吗?为了给想要选购洗地机的小伙伴提供一些参考…...
[React]常见Hook实现之useUpdateEffect
useUpdateEffect是一个自定义的React Hook,用于在组件更新时执行副作用。它的实现原理如下: useEffect和useLayoutEffect:useUpdateEffect内部使用useEffect或useLayoutEffect来注册副作用函数。这两个Hook函数都接受一个回调函数和依赖项数…...
为什么视频画质会变差,如何提升视频画质清晰度。
在数字时代,视频已经成为我们生活中不可或缺的一部分。然而,随着视频的传输和处理过程中的多次压缩,画质损失逐渐凸显,影响了我们对影像的真实感受。为了让视频画质更加清晰、逼真,我们需要采取一些措施来保护和修复视…...
【uni-app2.0】实现登录页记住密码功能
使用uni-app的uni.setStorageSync()和uni.getStorageSync()方法来存储和读取密码 在登录页中添加一个记住密码的u-checkbox选项,并在data里面添加一个rememberPwd的布尔值,在每次点击记住密码change的时候来记录用户的选择 <u-checkbox-group place…...
IDEA live templates
surround 在SQL的xml里 可以修改变量 官方文档 CDATA not null <if test"$SELECTION$ ! null and $SELECTION$ ! "> and $VAR1$ #{$SELECTION$} </if>not null like mysql <if test"$SELECTION$ ! null and $SELECTION$ ! "> and…...
电子鼻毕业论文
面向压埋探测的人体代谢气体识别方法的研究与应用 实现对非目标气体的检测 数据预处理 (1a)标准化 将采集到的数据先进行变换,统一数量级。其中,xij为第j个传感器的第i个采样值;xj为第 j 个气体传感器的所有采样值&…...
8 | 爬虫解析利器 PyQuery 的使用
文章目录 爬虫解析利器 PyQuery 的使用简介安装基本用法初始化查找元素遍历元素修改元素练习题练习题 1练习题 2答案练习题 1练习题 2总结爬虫解析利器 PyQuery 的使用 简介 PyQuery 是一个 Python 的库,它是 jQuery 的 Python 实现。PyQuery 可以让开发者使用类似于 jQuery…...
2023年 React 最佳学习路线
CSS CSS JavaScript JavaScript TypeScript 目前没有找到比其他文档好很多的文档地址 可以先看官网 React 新版 React 官方文档无敌 React React-router-dom V5 V6 Webpack webpack Antd antd...
使用 ChatGPT 进行研究的先进技术
在这篇文章中,您将探索改进您研究的先进技术。尤其, 分析和解释研究数据进行文献综述并找出研究差距废话不多说直接开始吧!!! 分析和解释研究数据 一家小企业主希望分析客户满意度数据以改善客户服务。他们使用包含 10…...
Java-API简析_java.net.Proxy类(基于 Latest JDK)(浅析源码)
【版权声明】未经博主同意,谢绝转载!(请尊重原创,博主保留追究权) https://blog.csdn.net/m0_69908381/article/details/131881661 出自【进步*于辰的博客】 因为我发现目前,我对Java-API的学习意识比较薄弱…...
磁盘问题和解决: fsck,gdisk,fdisk等
错误: Resize inode not valid 对于gpt分区的硬盘一般fsck只能检查分区, 不能用于检查整个硬盘, 但是如果对硬盘设备运行时遇到这样的错误 $ sudo fsck -n /dev/sdc fsck from util-linux 2.37.2 e2fsck 1.46.5 (30-Dec-2021) GW1.5T was not cleanly unmounted, check force…...
基于深度学习的高精度六类海船检测识别系统(PyTorch+Pyside6+YOLOv5模型)
摘要:基于深度学习的高精度六类海船检测识别系统可用于日常生活中检测与定位海船目标(散装货船(bulk cargo carrier)、集装箱船(container ship)、渔船(fishing boat)、普通货船&…...
【React Native】学习记录(一)——环境搭建
Expo是一套工具,库和服务,可让您通过编写JavaScript来构建原生iOS和Android应用程序。 一开始学习的时候直接使用的是expo。 npx create-expo-app my-appcd my-appnpm run start接下来需要搭建安卓和IOS端(为此特意换成了苹果电脑)…...
Java 设计模式 - 简单工厂模式 - 创建对象的简便之道
简单工厂模式是一种创建型设计模式,它提供了一种简单的方式来创建对象,而无需暴露对象创建的逻辑。在本篇博客中,我们将深入了解简单工厂模式的概念、实现方式以及如何在Java中使用它来创建对象。 为什么使用简单工厂模式? 在软…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
链式法则中 复合函数的推导路径 多变量“信息传递路径”
非常好,我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题,统一使用 二重复合函数: z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y)) 来全面说明。我们会展示其全微分形式(偏导…...
2025-05-08-deepseek本地化部署
title: 2025-05-08-deepseek 本地化部署 tags: 深度学习 程序开发 2025-05-08-deepseek 本地化部署 参考博客 本地部署 DeepSeek:小白也能轻松搞定! 如何给本地部署的 DeepSeek 投喂数据,让他更懂你 [实验目的]:理解系统架构与原…...
02-性能方案设计
需求分析与测试设计 根据具体的性能测试需求,确定测试类型,以及压测的模块(web/mysql/redis/系统整体)前期要与相关人员充分沟通,初步确定压测方案及具体的性能指标QA完成性能测试设计后,需产出测试方案文档发送邮件到项目组&…...
