【数据结构与算法 | 图篇】最小生成树之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 图解析 例二:逐步重构…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
Vue3中的computer和watch
computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...
Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...
