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

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...