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

【最小生成树】(二) Kruskal 算法

题目: 寻宝

题目描述

在世界的某个区域,有一些分散的神秘岛屿,每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路,方便运输。

不同岛屿之间,路途距离不同,国王希望你可以规划建公路的方案,如何可以以最短的总公路距离将 所有岛屿联通起来(注意:这是一个无向图)。

给定一张地图,其中包括了所有的岛屿,以及它们之间的距离。以最小化公路建设长度,确保可以链接到所有岛屿;

提取关键: 存在一些点, 存在一些边, 每条边都有一定的代价, 求将所有点连通的最小代价;

Kruskal 算法

思路

将边按代价从小到大进行排序, 然后从代价最小的开始遍历, 尽量选择代价小的边加入结果集中, 最终使得整个图连通;

当我们遍历到一条边, 这条边所连的两个顶点本身就已经连通时, 那么这条边是多余的, 如果加入, 会产生环;

并查集

并查集的作用与代码在上一篇文章中有详细介绍, 可以到专栏中查看;

前文介绍了并查集的两大作用: 判断两点之间是否连通以及求集合大小; 这里, 介绍另一个用途: 判断无向图中是否存在环;

在无向图中, 如果一条边的两个端点本来就是连通的(处在同一集合中), 那么这个边的加入必然会使得图中产生 “环”
假设图中有 1, 2, 3 三个顶点, 有 [1, 2], [1, 3] 两条边, 现在考虑加入 [2, 3] 这条边, 原本结点 2 和 结点 3 就已经处于连通状态, 现在加入 [2, 3] 必定导致图中出现环状结构;

利用并查集, 就可以在将边纳入[边集]之前进行判断, 判断当前边的加入是否会导致出现环;

1  ____  2\      /\    /3

代码

import java.util.*;public class Main{public static void main(String[] args){kruskal();}// 求最小生成树代价; 对边代价排序, 由小到大连接即可, 连接过程中用 Union 判断环private static void kruskal(){Scanner sc = new Scanner(System.in);int vNum = sc.nextInt();int eNum = sc.nextInt();int[][] edges = new int[eNum][3];for(int i = 0; i < eNum; i++){for(int j = 0; j < 3; j++){edges[i][j] = sc.nextInt();}}Arrays.sort(edges, (e1, e2) -> Integer.compare(e1[2], e2[2]));Union union = new Union(vNum);int res = 0;for(int[] edge : edges){if(!union.isSame(edge[0], edge[1])){res += edge[2];union.join(edge[0], edge[1]);}}System.out.println(res);}
}class Union{private int[] father;public Union(int size){father = new int[size + 1];for(int i = 1; i <= size; i++){father[i] = i;}}public int root(int i){int temp = i;while(father[temp] != temp){temp = father[temp];}father[i] = temp;return temp;}public boolean isSame(int i1, int i2){return root(i1) == root(i2);}public void join(int i1, int i2){father[root(i2)] = root(i1);}
}

上一篇 【最小生成树】(一) 预备知识 并查集

相关文章:

【最小生成树】(二) Kruskal 算法

题目: 寻宝 题目描述 在世界的某个区域&#xff0c;有一些分散的神秘岛屿&#xff0c;每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路&#xff0c;方便运输。 不同岛屿之间&#xff0c;路途距离不同&#xff0c;国王希望你可以规划建公路的方案&#xf…...

haproxy最强攻略

1、负载均衡 负载均衡&#xff08;Load Balance&#xff0c;简称 LB&#xff09;是高并发、高可用系统必不可少的关键组件&#xff0c;目标是 尽力将网络流量平均分发到多个服务器上&#xff0c;以提高系统整体的响应速度和可用性。 负载均衡的主要作用如下&#xff1a; 高并发…...

XetHub 加入 Hugging Face!

我们非常激动地正式宣布&#xff0c;Hugging Face 已收购 XetHub &#x1f525; XetHub 是一家位于西雅图的公司&#xff0c;由 Yucheng Low、Ajit Banerjee 和 Rajat Arya 创立&#xff0c;他们之前在 Apple 工作&#xff0c;构建和扩展了 Apple 的内部机器学习基础设施。XetH…...

在编程学习的海洋中,如何打造高效的知识宝库

目录 在编程学习的海洋中&#xff0c;如何打造高效的知识宝库一、笔记记录的重要性&#xff1a;为知识设立灯塔二、快速记录的策略&#xff1a;抓住知识的核心三、系统化的整理&#xff1a;构建个人知识体系四、实用工具推荐&#xff1a;为知识管理添砖加瓦五、保持条理性的秘诀…...

string详解(1)

1.C语言中的字符串 C语言中&#xff0c;字符串是以\0结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c;C标准库中提供了一些str系列的库函数&#xff0c;但是这些库函数与字符串是分离开的&#xff0c;不太符合OOP的思想&#xff0c;而且底层空间需要用户自己管理&…...

Linux云计算 |【第二阶段】NETWORK-DAY4

主要内容&#xff1a; NAT 原理与配置&#xff08;私有IP地址、静态NAT转换、Easy IP&#xff09;、VRRP解析&#xff08;主路由器、备份路由器、虚拟路由器、优先级&#xff09; 一、NAT概述 NAT 网络地址转换&#xff08;Network Address Translation&#xff09;是一种网络…...

amazon linux使用密码登录或者root登陆

1. 首先要把创建root密码&#xff0c;如果原来的密码不记得了&#xff0c;可以直接用 sudo passwd -d root 删除原来的密码 然后创建root密码 sudo passwd root 2. 修改 sshd_config 文件 vim /etc/ssh/sshd_config 允许使用密码登录 PasswordAuthentication yes 允许root…...

集智书童 | CNN 与 Transformer 的强强联合:AResNet-ViT在图像分析中的优势 !

本文来源公众号“集智书童”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;CNN 与 Transformer 的强强联合&#xff1a;AResNet-ViT在图像分析中的优势 &#xff01; 作者针对残差CNN分支的注意力引导设计进行了消融实验。同时&a…...

Ubuntu基础使用指南

Ubuntu基础使用指南 Ubuntu作为一款流行的开源操作系统&#xff0c;以其稳定性、安全性和易用性著称。无论是作为服务器操作系统还是桌面操作系统&#xff0c;Ubuntu都能满足用户的各种需求。下面&#xff0c;我们将从Ubuntu的基础使用开始&#xff0c;带你深入了解这个强大的…...

怎样才算精通 Excel?

最强AI视频生成&#xff1a;小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频百万播放量https://aitools.jurilu.com/ 高赞回答很系统&#xff0c;但普通人这么学&#xff0c;没等精通先学废了&#xff01; 4年前&#xff0c;我为了学数据分析&#…...

怎么学算法并找到工作

1.基础 找一本基础的内容看一遍 时间复杂度、空间复杂度计算方式数组、队列、栈、树、图结构十大排序算法 2.《hello算法》 动画图解算法 https://www.hello-algo.com/chapter_hello_algo/ 3.《剑指Offer》 一些面试的高频有年度的题解 里么的题很有特色&#xff0c;而…...

【实时建图】MapTR(1)------ 论文详解

作者们提出了一种有效构建高清地图的方法(MapTR),该地图为自动驾驶系统的规划提供丰富且精确的环境信息。这是一种结构化端到端变换器,用于高效在线矢量化地图构建。作者提出了一种统一的置换等价建模方法,即将地图元素建模为一个具有一组等价置换的点集,这准确地描述了地…...

通用Builder工具类

假设有一个Java实体类定义&#xff1a; public class Request {private String type;private String op;private PageInfo pageInfo;public static class PageInfo {private Integer pageNum;private Integer pageSize;}// 省略getter和setter... }在代码中创建这个对象&#…...

开源免费的海报设计器vue-fabric-editor

vue-fabric-editor 是一个基于 Vue.js 和 Fabric.js 的创新前端富文本编辑器&#xff0c;它将传统的文本输入体验与图形设计元素相结合&#xff0c;为用户提供了全新的内容创作方式。 以下是关于 vue-fabric-editor 的详细介绍&#xff1a; 一、技术特点 框架结合&#xff1a;…...

【学习笔记】Day 4 - Day 5

一、进度概述 1、新机环境配置 2、《地震勘探原理》第一章 3、对 “DL-FWI 研究方向展望” 组会的一些想法 二、详情 1、新机环境配置 配置新机环境着实耗了较多时间&#xff0c;导致理论进度推进较慢。 2、《地震勘探原理》第一章学习笔记 相关笔记在另一篇…...

MySQL数据分析进阶(十四)保护数据库

※食用指南&#xff1a;文章内容为‘CodeWithMosh’SQL进阶教程系列学习笔记&#xff0c;笔记整理比较粗糙&#xff0c;主要目的自存为主&#xff0c;记录完整的学习过程。&#xff08;图片超级多&#xff0c;慎看&#xff01;&#xff09; 【中字】SQL进阶教程 | 史上最易懂S…...

排序算法之堆排序

title: 堆排序 date: 2024-7-23 15:48:25 0800 categories: 排序算法 tags:排序算法堆排序 description: 堆排序&#xff08;Heap Sort&#xff09;是一种基于堆的排序算法&#xff0c;具有较高的效率和稳定性。 math: true 堆排序 堆排序&#xff08;Heap Sort&#xff09;是…...

Python中的NLP宝库:探索顶级库与工具

标题&#xff1a;Python中的NLP宝库&#xff1a;探索顶级库与工具 Python&#xff0c;作为人工智能和机器学习任务中的关键编程语言&#xff0c;为自然语言处理&#xff08;NLP&#xff09;提供了丰富的库和工具。这些库不仅功能强大&#xff0c;而且大多数都是开源的&#xf…...

springboot + springcloud + Google pubsub+ firebase

1.pom依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-gcp-starter</artifactId><version>1.2.6.RELEASE</version></dependency><dependency><groupId>org.springframe…...

时序数据库TDengine和QuestDB对比

QuestDB和TDengine都是高性能的时序数据库&#xff08;Time Series Database, TSDB&#xff09;&#xff0c;但它们在设计、功能、适用场景以及性能表现上各有特色。 以下是对两者的详细对比&#xff1a; 一、设计与架构 QuestDB 是一个开源的高性能SQL时序数据库&#xff0…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...