当前位置: 首页 > 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;逐步重构…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

Qt的学习(一)

1.什么是Qt Qt特指用来进行桌面应用开发&#xff08;电脑上写的程序&#xff09;涉及到的一套技术Qt无法开发网页前端&#xff0c;也不能开发移动应用。 客户端开发的重要任务&#xff1a;编写和用户交互的界面。一般来说和用户交互的界面&#xff0c;有两种典型风格&…...