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

【数据结构与算法 | 图篇】最小生成树之Kruskal(克鲁斯卡尔)算法

1. 前言

克鲁斯卡尔算法(Kruskal's algorithm)是一种用于寻找加权图的最小生成树(Minimum Spanning Tree, MST)的经典算法。这种算法是由约瑟夫·克鲁斯卡尔(Joseph Kruskal)提出的,并且适用于所有类型的加权无向图,特别是那些边比较稀疏的图

Prim算法更偏重于图的顶点,而克鲁斯卡尔算法更偏重于图的边。

2. 基本步骤

  1. 排序:首先将图中的所有边按照权重(cost)从小到大进行排序。
  2. 初始化:创建一个空集合来保存最小生成树中的边。
  3. 遍历边:依次检查每一条边,检查顺序基于权重的大小。对于每一条边 `(u, v)`:如果加入这条边不会在已选择的边中形成环,则将这条边加入到最小生成树中。如果加入这条边会导致环的形成,则跳过这条边。
  4. 终止条件:重复上述过程,直到最小生成树包含了 `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. 前言 克鲁斯卡尔算法&#xff08;Kruskals algorithm&#xff09;是一种用于寻找加权图的最小生成树&#xff08;Minimum Spanning Tree, MST&#xff09;的经典算法。这种算法是由约瑟夫克鲁斯卡尔&#xff08;Joseph Kruskal&#xff09;提出的&#xff0c;并且适用于所有…...

了解常用的代码检查工具

在软件开发领域&#xff0c;代码检查工具是确保代码质量、提高开发效率、促进团队协作的重要工具。这些工具通过自动化分析代码&#xff0c;帮助开发者发现潜在的错误、漏洞、代码异味等问题&#xff0c;并提供修复建议或重构方案。以下是一些常用的代码检查工具&#xff0c;它…...

BUUCTF PWN wp--warmup_csaw_2016

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

dockerfile搭建部署LNMP

目录 实验 架构&#xff1a; 实验步骤&#xff1a; nginx部分 mysql部分 php部分 实验 实验&#xff1a;用dockerfile搭建LNMP论坛 架构&#xff1a; 一台docker虚拟机 docker部署nginx 1.22 指定ip地址172.111.0.10 docker部署mysql 8.0.30 指定ip地址…...

Rust : 数据分析利器polars用法

Polars虽牛刀小试&#xff0c;就显博大精深&#xff0c;在数据分析上&#xff0c;未来有重要一席。 下面主要列举一些常见用法。 一、toml 需要说明的是&#xff0c;在Rust中&#xff0c;不少的功能都需要对应features引入设置&#xff0c;这些需要特别注意&#xff0c;否则编译…...

Qt第一课

作者前言 &#x1f382; ✨✨✨✨✨✨&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f382; ​&#x1f382; 作者介绍&#xff1a; &#x1f382;&#x1f382; &#x1f382; &#x1f389;&#x1f389;&#x1f389…...

论“graphics.h”库,easyx

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

如何在寂静中用电脑找回失踪的手机?远程控制了解一下

经过一番努力&#xff0c;我终于成功地将孩子哄睡了。夜深人静&#xff0c;好不容易有了一点自己的时间&#xff0c;就想刷手机放松放松&#xff0c;顺便看看有没有重要信息。但刚才专心哄孩子去了&#xff0c;一时就忘记哄孩子之前&#xff0c;顺手把手机放哪里去了。 但找过手…...

Android 实现动态换行显示的 TextView 列表

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

Golang | Leetcode Golang题解之第352题将数据流变为多个不相交区间

题目&#xff1a; 题解&#xff1a; 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中操作 &#xff08;1&#xff09;在虚拟机中安装mysql &#xff08;2&#xff09;连接Windows数据库 &#xff08;3&#xff09;进入linux数据库。 &#xff08;4&#xff09;修改mysql配置文件 二.Windows命令窗口操作 需要软件虚拟机&#xff0c;Xsh…...

【数学建模】MATLAB快速入门

文章目录 1. MATLAB界面与基本操作1.1 MATLAB的基本操作 2. MATLAB字符串和文本2.1 string变量2.2 char变量 3. MATLAB的矩阵运算 1. MATLAB界面与基本操作 初始界面&#xff1a; 刚开始的界面只要一个命令行窗口&#xff0c;为了使编辑界面出现我们需要新建一个文件&#xff…...

【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 的数据备份与恢复

在生产环境中&#xff0c;数据的安全性和可靠性至关重要。对于基于 Elasticsearch 的系统而言&#xff0c;数据备份与恢复是确保数据完整性、应对灾难恢复的关键操作。本文将详细介绍 Elasticsearch 中如何进行数据备份与恢复&#xff0c;帮助管理员构建一个可靠的数据保护策略…...

Ps:首选项 - 暂存盘

Ps菜单&#xff1a;编辑/首选项 Edit/Preferences 快捷键&#xff1a;Ctrl K Photoshop 首选项中的“暂存盘” Scratch Disks选项卡通过合理配置和管理暂存盘&#xff0c;可以显著提高 Photoshop 的运行性能&#xff0c;特别是在处理复杂的设计项目或大型图像文件时。选择合适…...

力扣217题详解:存在重复元素的多种解法与复杂度分析

在本篇文章中&#xff0c;我们将详细解读力扣第217题“存在重复元素”。通过学习本篇文章&#xff0c;读者将掌握如何使用多种方法来解决这一问题&#xff0c;并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释&#xff0c;以便于理解。 问题描述 力扣第217…...

享元模式:轻量级对象共享,高效利用内存

享元模式&#xff08;Flyweight Pattern&#xff09;是一种结构型设计模式&#xff0c;用于减少对象数量、降低内存消耗和提高系统性能。它通过共享相似对象的内部状态&#xff0c;减少重复创建的对象。下面将具体介绍享元模式的各个方面&#xff1a; 组成 抽象享元&#xff0…...

人工智能-自然语言处理(NLP)

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

基于UE5和ROS2的激光雷达+深度RGBD相机小车的仿真指南(三)---创建自定义激光雷达Componet组件

前言 本系列教程旨在使用UE5配置一个具备激光雷达深度摄像机的仿真小车&#xff0c;并使用通过跨平台的方式进行ROS2和UE5仿真的通讯&#xff0c;达到小车自主导航的目的。本教程默认有ROS2导航及其gazebo仿真相关方面基础&#xff0c;Nav2相关的学习教程可以参考本人的其他博…...

C++ 设计模式——策略模式

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

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

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

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

Python 高效图像帧提取与视频编码:实战指南

Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...

ubuntu22.04有线网络无法连接,图标也没了

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

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

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

如何把工业通信协议转换成http websocket

1.现状 工业通信协议多数工作在边缘设备上&#xff0c;比如&#xff1a;PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发&#xff0c;当设备上用的是modbus从站时&#xff0c;采集设备数据需要开发modbus主站&#xff1b;当设备上用的是西门子PN协议时&#xf…...