当前位置: 首页 > news >正文

图论 之 最小生成树

文章目录

  • 题目
    • 1584.连接所有点的最小费用

  • 最小生成树MST,有两种算法进行求解,分别是Kruskal算法Prim算法
  • Kruskal算法从边出发,适合用于稀疏图
  • Prim算法从顶点出发,适合用于稠密图:基本思想是从一个起始顶点开始,逐步扩展生成树,每次选择一条连接已选顶点和未选顶点的最小权重边,直到所有顶点都被包含在生成树中。

Prim算法的基本步骤:

  • 初始化:选择一个起始顶点,将其加入生成树中。
  • 选择最小边:在所有连接生成树中顶点和未加入生成树的顶点的边中,选择权重最小的边。
  • 扩展生成树:将这条边及其连接的未加入顶点加入生成树。
  • 重复:重复步骤2和步骤3,直到所有顶点都加入生成树。

与求解最短路径的Dijkstra算法的求解思路是有异曲同工之妙的

  • Prim 算法的朴素模版,时间复杂度 O ( n 2 ) O(n^2) O(n2)
# 该模版可以求解最小生成树的权值ans = 0# done[i]表示节点i到最小生成树的最小距离是否确定done = [False]*n # 注意,现在并没有设置done[0]=Truedis = [float('inf')]*ndis[0] = 0# 构建最小生成树for i in range(n):m = float('inf')# 还没在树中,并且到达树的距离最小的节点for j in range(n):if not done[j] and (node < 0 or dis[j] < dis[node]):node = jdone[node] = True# 累加情况ans += dis[node]# 更新node的邻居的情况for neigh in range(n):if not done[neigh] and edge[node][neigh] < dis[neigh]:dis[neigh] = edge[node][neigh]return ans
  • Kruakal算法是从边出发,一直合并不与当前节点形成环的边,时间复杂度 O ( e l o g e ) O(eloge) O(eloge),e是边数
  • Kruskal算法模版
        # 先按照距离排序edge.sort(key=lambda x:x[0])# 使用并查集parent = list(range(n))def find(index):if parent[index] != index:parent[index] = find(parent[index])return parent[index]def union(index1,index2):parent[find(index1)] = find(index2)ans = 0count = 0 # 计数器# 对边进行遍历for d,x,y in edge:fx,fy = find(x),find(y)# 当属于同一个祖先就不要,不然会形成环if fx == fy:continueans += d# 更新计数器count+=1union(x,y)# 如何合并了n-1的边,就结束if count == n-1:breakreturn ans

题目

1584.连接所有点的最小费用

1584.连接所有点的最小费用

在这里插入图片描述

思路分析:最小生成树的模版题目

  • 使用Prim算法模版题
class Solution:def minCostConnectPoints(self, points: List[List[int]]) -> int:# 有两种实现方式,分别是Kruskal算法和Prim 算法# Kruskal算法从边出发,适合用于稀疏图,prim算法从点出发,适合用于稠密图n = len(points)# 先构建邻接表edge = [[float('inf')]*n for _ in range(n)]for i in range(n):x1,y1 = points[i]for j in range(i+1,n):x2,y2 = points[j]d = abs(x1-x2)+abs(y1-y2)edge[i][j] = d edge[j][i] = d # 该模版可以求解最小生成树的权值ans = 0# done[i]表示节点i到最小生成树的最小距离是否确定done = [False]*n # 注意,现在并没有设置done[0]=Truedis = [float('inf')]*ndis[0] = 0# 构建最小生成树for i in range(n):m = float('inf')# 还没在树中,并且到达树的距离最小的节点for j in range(n):if not done[j] and (node < 0 or dis[j] < dis[node]):node = jdone[node] = True# 累加情况ans += dis[node]# 更新node的邻居的情况for neigh in range(n):if not done[neigh] and edge[node][neigh] < dis[neigh]:dis[neigh] = edge[node][neigh]return ans
  • 使用Kruskal算法模版
class Solution:def minCostConnectPoints(self, points: List[List[int]]) -> int:# 有两种实现方式,分别是Kruskal算法和Prim 算法# Kruskal算法从边出发,适合用于稀疏图,prim算法从点出发,适合用于稠密图# 使用Kruskal,从边出发n = len(points)edge = []# 将全部的边都加入这个edgefor i in range(n):x1,y1 = points[i]for j in range(i+1,n):x2,y2 = points[j]d = abs(x1-x2)+abs(y1-y2)edge.append((d,i,j))# 先按照距离排序edge.sort(key=lambda x:x[0])# 使用并查集parent = list(range(n))def find(index):if parent[index] != index:parent[index] = find(parent[index])return parent[index]def union(index1,index2):parent[find(index1)] = find(index2)ans = 0count = 0 # 计数器for d,x,y in edge:fx,fy = find(x),find(y)if fx == fy:continueans += dcount+=1union(x,y)if count == n-1:breakreturn ans

相关文章:

图论 之 最小生成树

文章目录 题目1584.连接所有点的最小费用 最小生成树MST&#xff0c;有两种算法进行求解&#xff0c;分别是Kruskal算法和Prim算法Kruskal算法从边出发&#xff0c;适合用于稀疏图Prim算法从顶点出发&#xff0c;适合用于稠密图&#xff1a;基本思想是从一个起始顶点开始&#…...

STM32-有关内存堆栈、map文件

STM32堆栈空间大小设置_stm32堆栈分配大小-CSDN博客 STM32堆栈的大小及内存四&#xff08;五&#xff09;区的分析 - 天街小雨润地狠 - 博客园 .map文件的位置...

Linux系统中常见的词GNU是什么意思?

GNU 是 “GNU’s Not Unix” 的递归缩写&#xff0c;它是一个自由软件项目&#xff0c;旨在创建一个完全自由的操作系统。这个名字反映了GNU项目的核心理念&#xff1a;它试图创建一个类Unix的系统&#xff0c;但不是Unix本身。 GNU 项目由 理查德斯托曼&#xff08;Richard S…...

【个人开源】——从零开始在高通手机上部署sd(二)

代码&#xff1a;https://github.com/chenjun2hao/qualcomm.ai 推理耗时统计 单位/ms 硬件qnncpu_clipqnncpu_unetqnncpu_vaehtp_cliphtp_unethtp_vae骁龙8 gen124716.994133440.39723.215411.097696.327 1. 下载依赖 下载opencv_x64.tar,提取码: rrbp下载opencv_aarch64.t…...

【MCU驱动开发概述】

MCU驱动开发概述 目录 MCU驱动开发概述二、驱动开发的目的三、驱动开发的关键组成部分四、示例 - LED 控制驱动 一、引言 MCU&#xff08;Microcontroller Unit&#xff09;&#xff0c;即微控制器单元&#xff0c;是一种集成在单个芯片上的计算机系统&#xff0c;通常用于控制…...

PC端Linux之虚拟CAN

在调试QT程序时候需要用到虚拟CAN进行发送和接收的操作&#xff0c;以此记录方法。 在调试QT程序时候需要用到虚拟CAN进行发送和接收的操作&#xff0c;以此记录方法。 1、安装can-utils sudo apt install can-utils ifconig -a【查看是否安装成功&#xff0c;是否有can0网络…...

C++:std::thread、条件变量与信号量

介绍 在多线程编程的世界里&#xff0c;协调不同线程之间的工作是一项极具挑战性的任务。线程可能需要等待特定条件的满足&#xff0c;或者对共享资源的访问进行限制。C 标准库为我们提供了强大的工具&#xff0c;如 std::thread 用于创建和管理线程&#xff0c;条件变量用于线…...

POI pptx转图片

前言 ppt页面预览一直是个问题&#xff0c;office本身虽然有预览功能但是收费&#xff0c;一些开源的项目的预览又不太好用&#xff0c;例如开源的&#xff1a;kkfileview pptx转图片 1. 引入pom依赖 我这个项目比较老&#xff0c;使用版本较旧 <dependency><gro…...

Java File 类

File 类是 Java 中用于处理文件和目录的基本类之一&#xff0c;位于 java.io 包中。它提供了多种方法来创建、删除、检查、修改文件或目录的属性&#xff0c;以及列出文件夹中的内容。虽然 File 类本身不提供直接的读取或写入文件内容的方法&#xff08;这些操作通常由 FileInp…...

工业通信协议 EtherNet/IP 全面解析

工业通信协议 EtherNet/IP 全面解析 EtherNet/IP&#xff08;以太网工业协议&#xff09;是一种基于标准以太网的工业自动化通信协议&#xff0c;由 ODVA&#xff08;开放设备网供应商协会&#xff09; 管理。它融合了 CIP&#xff08;通用工业协议&#xff09; 和以太网技术&…...

使用docker配置PostgreSQL

配置docker阿里云镜像仓库 国内使用docker hub拉取镜像比较慢&#xff0c;所以首先配置个人的镜像仓库。 阿里云的个人镜像仓库是免费的&#xff0c;对个人来说足够用。 具体操作参考阿里云官方链接 。 关于个人镜像仓库的使用参考链接。 配置完个人镜像仓库后将公网配置到doc…...

UITextView删除原有字符串时,光标会上移并且光标会变高

代码运行效果如图&#xff1a; import Foundationclass TestVC: UIViewController {override func viewDidLoad() {super.viewDidLoad()let testV MyCustomTextView(frame: CGRect(x: 0, y: 130, width: SCREEN_WIDTH - 50, height: 170))self.view.addSubview(testV)testV.ba…...

python入门 介绍及变量的使用

1.python介绍 python 是一门计算机语言 常见的计算机语言&#xff1a;python、java、C语言。。。 什么是计算机语言&#xff1a;就是让计算机知道你想干什么&#xff0c;把你的需求使用它能听懂的语言说出来 中国也有一门计算机语言&#xff1a;易语言 能认为是语言的本质上…...

51单片机-按键

1、独立按键 1.1、按键介绍 轻触开关是一种电子开关&#xff0c;使用时&#xff0c;轻轻按开关按钮就可使开关接通&#xff0c;当松开手时&#xff0c;开关断开。 1.2、独立按键原理 按键在闭合和断开时&#xff0c;触点会存在抖动现象。P2\P3\P1都是准双向IO口&#xff0c;…...

Java 8 至 Java 23 版本特性对比表

Java现在发布的版本很快&#xff0c;每年两个&#xff0c;但是真正会被大规模使用的是三年一个的TLS版本。 版本年份LTS关键特性影响力等级Java 82014✅Lambda 表达式、Stream API、方法引用、接口默认方法、Optional 类⭐⭐⭐⭐⭐Java 92017❌模块化系统&#xff08;JPMS&…...

在wsl环境中配置和开发verilog(一种比较新颖的verilog开发指南)

WSL是windows中自带的linux子系统&#xff0c;笔者在若干月前首次接触其便爱不释手&#xff0c;verilog作为一种硬件解释语言&#xff0c;可否像c语言那样被游刃有余的编译和运行呢&#xff0c;笔者这次大胆的尝试在WSL环境VSCODEIverilog开发verilog。 首先默认按照了WSL和VS…...

AI学习指南HuggingFace篇-Hugging Face 的核心工具

一、引言 Hugging Face作为AI领域的重要参与者,提供了许多强大的工具,极大地简化了自然语言处理(NLP)任务的开发流程。其中,Transformers、Datasets 和 Tokenizers 是Hugging Face的三大核心工具。本文将深入介绍这些工具的作用、功能以及它们如何相互配合,帮助读者更好…...

DeepSeek 助力 Vue 开发:打造丝滑的二维码生成(QR Code)

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享一篇文章&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 目录 Deep…...

QT 引入Quazip和Zlib源码工程到项目中,无需编译成库,跨平台,压缩进度

前言 最近在做项目时遇到一个需求&#xff0c;需要将升级的文件压缩成zip&#xff0c;再进行传输&#xff1b; 通过网络调研&#xff0c;有许多方式可以实现&#xff0c;例如QT私有模块的ZipReader、QZipWriter&#xff1b;或者第三方库zlib或者libzip或者quazip等&#xff1…...

深入解析桥接模式:软件设计中的解耦利器

桥接模式&#xff1a;软件设计中的解耦利器 在软件开发的复杂世界中&#xff0c;设计模式是开发者解决常见问题的有力工具。桥接模式作为一种重要的结构型设计模式&#xff0c;在处理抽象与实现的关系时展现出独特的优势&#xff0c;它能够巧妙地将抽象部分与实现部分分离&…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...