【数据结构与算法 | 图篇】最小生成树之Kruskal(克鲁斯卡尔)算法
1. 前言
克鲁斯卡尔算法(Kruskal's algorithm)是一种用于寻找加权图的最小生成树(Minimum Spanning Tree, MST)的经典算法。这种算法是由约瑟夫·克鲁斯卡尔(Joseph Kruskal)提出的,并且适用于所有类型的加权无向图,特别是那些边比较稀疏的图。
Prim算法更偏重于图的顶点,而克鲁斯卡尔算法更偏重于图的边。
2. 基本步骤
- 排序:首先将图中的所有边按照权重(cost)从小到大进行排序。
- 初始化:创建一个空集合来保存最小生成树中的边。
- 遍历边:依次检查每一条边,检查顺序基于权重的大小。对于每一条边 `(u, v)`:如果加入这条边不会在已选择的边中形成环,则将这条边加入到最小生成树中。如果加入这条边会导致环的形成,则跳过这条边。
- 终止条件:重复上述过程,直到最小生成树包含了 `n - 1` 条边(其中 `n` 是顶点的数量),或者没有更多的边可以添加为止。
3. 代码
public class Kruskal {// 静态内部类static class Edge implements Comparable<Edge>{// 顶点集合,构造器赋值,用于toString方法List<Vertex> vertices;// 下列两属性是定点集合的索引,比如索引0代表顶点v1int start;int end;int weight;public Edge(int start, int end, int weight) {this.start = start;this.end = end;this.weight = weight;}public Edge(List<Vertex> vertices, int start, int end, int weight) {this.vertices = vertices;this.start = start;this.end = end;this.weight = weight;}@Overridepublic int compareTo(Edge o) {return Integer.compare(this.weight, o.weight);}@Overridepublic String toString() {return "v" + vertices.get(start).name + "<=>" + "v"+vertices.get(end).name + " " + "(" + weight + ")";}}public static void main(String[] args) {List<Vertex> vertices = new ArrayList<>();Vertex v1 = new Vertex("0");Vertex v2 = new Vertex("1");Vertex v3 = new Vertex("2");Vertex v4 = new Vertex("3");Vertex v5 = new Vertex("4");Vertex v6 = new Vertex("5");Vertex v7 = new Vertex("6");vertices.add(v1);vertices.add(v2);vertices.add(v3);vertices.add(v4);vertices.add(v5);vertices.add(v6);vertices.add(v7);List<Edge> edges = new ArrayList<>();// 由于处理的是加权无向图,所以start:0, end:1与start:1, end:0无区别edges.add(new Edge(vertices, 0, 1, 2));edges.add(new Edge(vertices, 0, 2, 4));edges.add(new Edge(vertices, 0, 3, 1));edges.add(new Edge(vertices, 1, 3, 3));edges.add(new Edge(vertices, 1, 4, 10));edges.add(new Edge(vertices, 2, 3, 2));edges.add(new Edge(vertices, 2, 5, 5));edges.add(new Edge(vertices, 3, 4, 7));edges.add(new Edge(vertices, 3, 5, 8));edges.add(new Edge(vertices, 3, 6, 4));edges.add(new Edge(vertices, 4, 6, 6));edges.add(new Edge(vertices, 5, 6, 1));//将边的集合按照从小到大的顺序排列PriorityQueue<Edge> queue = new PriorityQueue<>(edges);kruskal(vertices.size(), queue);}public static void kruskal(int size, PriorityQueue<Edge> queue) {// 创建一个空集合来保存最小生成树中的边。List<Edge> list = new ArrayList<>();// 最小生成树的顶点数为size个,所以只需要找到size-1条边即可while (list.size() < size - 1){// 弹出边权重最小的边判断Edge poll = queue.poll();// 并查集:用来判断该边加入是否会相交,如果会,则跳过该边DisjointSet set = new DisjointSet(size);int i = set.find(poll.start);int j = set.find(poll.end);// 如果不相交if(i != j){list.add(poll);// 将两点相交set.union(i, j);}}for (Edge e : list){System.out.println(e);}}
}
输出:
v0<=>v3 (1)
v5<=>v6 (1)
v2<=>v3 (2)
v0<=>v1 (2)
v1<=>v3 (3)
v0<=>v2 (4)
4. 图注
初始时顶点图:
最小生成树的图:
由图:当(v3->v4)(v4->v7) (v7->v6)三顶点已经连通,判断(v3->v6)时,find(2) == find(5),即两个顶点已经连通,(如果加入该边会形成环)所以跳过该边。
相关文章:

【数据结构与算法 | 图篇】最小生成树之Kruskal(克鲁斯卡尔)算法
1. 前言 克鲁斯卡尔算法(Kruskals algorithm)是一种用于寻找加权图的最小生成树(Minimum Spanning Tree, MST)的经典算法。这种算法是由约瑟夫克鲁斯卡尔(Joseph Kruskal)提出的,并且适用于所有…...
了解常用的代码检查工具
在软件开发领域,代码检查工具是确保代码质量、提高开发效率、促进团队协作的重要工具。这些工具通过自动化分析代码,帮助开发者发现潜在的错误、漏洞、代码异味等问题,并提供修复建议或重构方案。以下是一些常用的代码检查工具,它…...

BUUCTF PWN wp--warmup_csaw_2016
第一步 先checksec一下(没有启用NX保护、PIE、完整的RELRO和栈保护,还有具有RWX权限的内存段。) 分析一下这个文件的保护机制: Arch: amd64-64-little 这表示该可执行文件是为64位的AMD64架构编译的,并且使用的是小…...

dockerfile搭建部署LNMP
目录 实验 架构: 实验步骤: nginx部分 mysql部分 php部分 实验 实验:用dockerfile搭建LNMP论坛 架构: 一台docker虚拟机 docker部署nginx 1.22 指定ip地址172.111.0.10 docker部署mysql 8.0.30 指定ip地址…...
Rust : 数据分析利器polars用法
Polars虽牛刀小试,就显博大精深,在数据分析上,未来有重要一席。 下面主要列举一些常见用法。 一、toml 需要说明的是,在Rust中,不少的功能都需要对应features引入设置,这些需要特别注意,否则编译…...

Qt第一课
作者前言 🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂 🎂 作者介绍: 🎂🎂 🎂 🎉🎉🎉…...
论“graphics.h”库,easyx
前言 别人十步我则百,别人百步我则千 你是否有这样的想法,把图片到入进c里,亦或者能实时根据你发出的信息而做出回应的程序,graphics.h这个库完美满足了你的需求,那今天作者就给大家介绍一下这个库,并做一些…...

如何在寂静中用电脑找回失踪的手机?远程控制了解一下
经过一番努力,我终于成功地将孩子哄睡了。夜深人静,好不容易有了一点自己的时间,就想刷手机放松放松,顺便看看有没有重要信息。但刚才专心哄孩子去了,一时就忘记哄孩子之前,顺手把手机放哪里去了。 但找过手…...

Android 实现动态换行显示的 TextView 列表
在开发 Android 应用程序时,我们经常需要在标题栏中显示多个 TextView,而这些 TextView 的内容长度可能不一致。如果一行内容过长,我们希望它们能自动换行;如果一行占不满屏幕宽度,则保持在一行内。本文将带我们一步步…...

Golang | Leetcode Golang题解之第352题将数据流变为多个不相交区间
题目: 题解: type SummaryRanges struct {*redblacktree.Tree }func Constructor() SummaryRanges {return SummaryRanges{redblacktree.NewWithIntComparator()} }func (ranges *SummaryRanges) AddNum(val int) {// 找到 l0 最大的且满足 l0 < val…...

Ubuntu安装mysql 以及远程连接mysql Windows—适合初学者的讲解(详细)
目录 准备工作 一.Xshell中操作 (1)在虚拟机中安装mysql (2)连接Windows数据库 (3)进入linux数据库。 (4)修改mysql配置文件 二.Windows命令窗口操作 需要软件虚拟机,Xsh…...

【数学建模】MATLAB快速入门
文章目录 1. MATLAB界面与基本操作1.1 MATLAB的基本操作 2. MATLAB字符串和文本2.1 string变量2.2 char变量 3. MATLAB的矩阵运算 1. MATLAB界面与基本操作 初始界面: 刚开始的界面只要一个命令行窗口,为了使编辑界面出现我们需要新建一个文件ÿ…...
【ubuntu24.04】k8s 部署5:配置calico 镜像拉取
kubeadm - 中国大陆版建议:初始化Kubeadm –apiserver-advertise-address 这个地址是本地用于和其他节点通信的IP地址 –pod-network-cidr pod network 地址空间 sudo kubeadm init --image-repository registry.aliyuncs.com/google_containers --apiserver-advertise-add…...
Elasticsearch 的数据备份与恢复
在生产环境中,数据的安全性和可靠性至关重要。对于基于 Elasticsearch 的系统而言,数据备份与恢复是确保数据完整性、应对灾难恢复的关键操作。本文将详细介绍 Elasticsearch 中如何进行数据备份与恢复,帮助管理员构建一个可靠的数据保护策略…...

Ps:首选项 - 暂存盘
Ps菜单:编辑/首选项 Edit/Preferences 快捷键:Ctrl K Photoshop 首选项中的“暂存盘” Scratch Disks选项卡通过合理配置和管理暂存盘,可以显著提高 Photoshop 的运行性能,特别是在处理复杂的设计项目或大型图像文件时。选择合适…...
力扣217题详解:存在重复元素的多种解法与复杂度分析
在本篇文章中,我们将详细解读力扣第217题“存在重复元素”。通过学习本篇文章,读者将掌握如何使用多种方法来解决这一问题,并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释,以便于理解。 问题描述 力扣第217…...
享元模式:轻量级对象共享,高效利用内存
享元模式(Flyweight Pattern)是一种结构型设计模式,用于减少对象数量、降低内存消耗和提高系统性能。它通过共享相似对象的内部状态,减少重复创建的对象。下面将具体介绍享元模式的各个方面: 组成 抽象享元࿰…...

人工智能-自然语言处理(NLP)
人工智能-自然语言处理(NLP) 1. NLP的基础理论1.1 语言模型(Language Models)1.1.1 N-gram模型1.1.2 词嵌入(Word Embeddings)1.1.2.1 词袋模型(Bag of Words, BoW)1.1.2.2 TF-IDF&a…...

基于UE5和ROS2的激光雷达+深度RGBD相机小车的仿真指南(三)---创建自定义激光雷达Componet组件
前言 本系列教程旨在使用UE5配置一个具备激光雷达深度摄像机的仿真小车,并使用通过跨平台的方式进行ROS2和UE5仿真的通讯,达到小车自主导航的目的。本教程默认有ROS2导航及其gazebo仿真相关方面基础,Nav2相关的学习教程可以参考本人的其他博…...

C++ 设计模式——策略模式
策略模式 策略模式主要组成部分例一:逐步重构并引入策略模式第一步:初始实现第二步:提取共性并实现策略接口第三步:实现具体策略类第四步:实现上下文类策略模式 UML 图策略模式的 UML 图解析 例二:逐步重构…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...

ubuntu22.04有线网络无法连接,图标也没了
今天突然无法有线网络无法连接任何设备,并且图标都没了 错误案例 往上一顿搜索,试了很多博客都不行,比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动,重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究
摘要:在消费市场竞争日益激烈的当下,传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序,探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式,分析沉浸式体验的优势与价值…...

如何把工业通信协议转换成http websocket
1.现状 工业通信协议多数工作在边缘设备上,比如:PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发,当设备上用的是modbus从站时,采集设备数据需要开发modbus主站;当设备上用的是西门子PN协议时…...