当前位置: 首页 > 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…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...