【图论笔记】克鲁斯卡尔算法(Kruskal)求最小生成树

【图论笔记】克鲁斯卡尔算法(Kruskal)求最小生成树

适用于

克鲁斯卡尔适合用来求边比较稀疏的图的最小生成树

简记:

将边按照升序排序,选取n-1条边,连通n个顶点。
添加一条边的时候,如何判断能不能添加这条边?(添加进来之后,会不会构成回路)
看标记,
和原来的标记不一样,就可以加入,
加入之后将他们的标记修改为一样的。

图解

请添加图片描述
第一步:创建一个连通图,并且给每个顶点都标记上不同的颜色

第二步:选取边<A,C>,选完之后C的颜色要和A相同
请添加图片描述
第三步:加入边<D,F>,将F的颜色改为D的蓝色
请添加图片描述
第四步:加入边<B,E>,将E改为紫色
请添加图片描述
第五步:添加边<C,F>,将F相连的节点改为绿色(包括它自己)
请添加图片描述
第六步:<A,D>不能加入,因为A和D的颜色一样。加入边<B,C>,将原来和B相连的节点的颜色都改为绿色。完
请添加图片描述

代码正在研究

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/232239.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

python数据分析小案例:天猫订单数据综合分析

嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 本数据集共收集了发生在一个月内的28010条数据&#xff0c;包含以下&#xff1a; 7个字段说明 订单编号&#xff1a;订单编号 总金额&#xff1a;订单总金额 买…

if语句和switch语句来确定金额之下的优惠折扣

一、优惠规则 输入相应的金额&#xff0c;可以获得规则之下&#xff0c;金额相应的享受的折扣&#xff0c;需要先定义金额&#xff0c;然后就是使用if语句进行判断&#xff0c;使用switch语句选择判断规则之下对应的优惠折扣。 二、相关代码 public class DiscountPrice {p…

Dockerfile文件

什么是dockerfile? Dockerfile是一个包含用于组合映像的命令的文本文档。可以使用在命令行中调用任何命令。 Docker通过读取Dockerfile中的指令自动生成映像。 docker build命令用于从Dockerfile构建映像。可以在docker build命令中使用-f标志指向文件系统中任何位置的Docke…

ConvNeXt V2: Co-designing and Scaling ConvNets with Masked Autoencoders

1.关于稀疏卷积的解释&#xff1a;https://zhuanlan.zhihu.com/p/382365889 2. 答案&#xff1a; 在深度学习领域&#xff0c;尤其是计算机视觉任务中&#xff0c;遮蔽图像建模&#xff08;Masked Image Modeling, MIM&#xff09;是一种自监督学习策略&#xff0c;其基本思想…

rpc原理与应用

IPC和RPC&#xff1f; RPC 而RPC&#xff08;Remote Procedure Call&#xff09;&#xff0c;又叫做远程过程调用。它本身并不是一个具体的协议&#xff0c;而是一种调用方式。 gRPC 是 Google 最近公布的开源软件&#xff0c;基于最新的 HTTP2.0 协议&#xff0c;并支持常见…

【计算机网络】HTTPS协议原理

目录 一. HTTPS的基础概念 二. 概念准备 1. 密码学 2. 为什么要加密 三. 常见加密方式 1. 对称加密 2. 非对称加密 四. HTTPS原理探究 五. CA认证 1. 数据指纹&&数据摘要 2. 证书 3. 签名与验证 4. 琐碎知识点 5. 总结——完整流程 结束语 一. HTTPS的基…

开发猿的平平淡淡周末---2023/12/9

上周回顾 完成了遗留的开发任务&#xff0c;基本全部完成进一步了解了系统当时设计的原理熟悉了代码的重构 2023.12.9 天气晴 温度适宜 前言 小伙伴们大家好&#xff0c;时间很快&#xff0c;又来到了周末&#xff0c;也是一个平平淡淡的周末。上周只更了一篇博客...原…

交换机基本原理和配置

目录 一、数据链路层功能 二、交换机的工作原理 三、交换机的四大功能 一、数据链路层功能 位于网络层与物理层之间 数据链路的建立、维护与拆除帧包装、帧传输、帧同步帧的差错恢复流量控制 二、交换机的工作原理 交换机通过数据帧的源 MAC 地址&#xff0c;学习到交换机端…

讲座 | 颠覆传统摄像方式乃至计算机视觉的“脉冲视觉”

传统相机拍摄视频时其实是以一定帧率进行采样&#xff0c;视频其实还是一串图片的集合&#xff0c;因此低帧率时会觉得视频卡&#xff0c;拍摄高速运动物体时会有运动模糊等等问题。然而你能想象这一切都可以被“脉冲视觉”这一前沿技术改变吗&#xff1f; 今天下午听了北京大学…

数据库数据恢复—Mysql数据库误删表数据的数据恢复案例

mysql数据库数据恢复环境&#xff1a; 本地服务器&#xff0c;windows server操作系统 &#xff0c;部署有mysql单实例&#xff0c;数据库引擎类型为innodb&#xff0c;独立表空间&#xff0c;无数据库备份&#xff0c;未开启binlog。 mysql数据库故障&#xff1a; 工作人员使…

前端vue3——实现二次元人物拼图校验

文章目录 ⭐前言⭐vue3拖拽实现拼图&#x1f496; 思路分解&#x1f496; 布局结构&#x1f496; 拖拽函数&#x1f496; 校验函数&#x1f496; inscode整体代码 ⭐运行效果&#x1f496; 随机顺序&#x1f496; 拖拽中&#x1f496; 校验失败&#x1f496; 校验通过 ⭐总结⭐…

2.2 网络多线程(私聊、群发、发送文件、推送新闻、离线留言)

文章目录 一、私聊1.1 分析1.2 客户端1.2.1 MessageClientService 私聊类1.2.2 ClientConnectServerThread 线程类 1.3 服务端1.3.1 ServerConnectClientThread 线程类 1.4功能演示 二、群发消息2.1 分析2.2 客户端2.2.1 MessageClientService类2.2.2 ClientConnectServerThrea…

使用Microsoft Dynamics AX 2012 - 6. 运营规划

运营规划的主要职责是确保项目在需要的时候可用&#xff0c;同时达到高经济效益的目标。运营规划必须解决高供应准备度和低库存这两个相互冲突的优先事项。 运营规划中的业务流程 在Dynamics AX中&#xff0c;长期预测和短期总体规划由运营规划模块&#xff08;“总体规划”&…

面试计算机网络八股文五问五答第一期

面试计算机网络八股文五问五答第一期 作者&#xff1a;程序员小白条&#xff0c;个人博客 相信看了本文后&#xff0c;对你的面试是有一定帮助的&#xff01; ⭐点赞⭐收藏⭐不迷路&#xff01;⭐ 1.TCP和UDP的区别 TCP和UDP是两种网络传输协议&#xff0c;它们的主要区别在…

Android audio环形缓冲队列

1、背景 在学习audio的过程中&#xff0c;看到了大神zyuanyun的博客&#xff0c;在博客的结尾&#xff0c;大神留下了这些问题&#xff1a; 但是大神没有出后续的博文来说明audio环形缓冲队列的具体实现&#xff0c;这勾起了我强烈的好奇心。经过一段时间的走读代码&#xff…

Docker Network(网络)——8

目录&#xff1a; Docker 为什么需要网络管理Docker 网络架构简介 CNMLibnetwork驱动常见网络类型 bridge 网络host 网络container 网络none 网络overlay 网络docker 网络管理命令 docker network createdocker network inspectdocker network connectdocker network disconne…

22、文件上传漏洞——文件上传检测与绕过

文章目录 一、文件上传漏洞原理二、客户端检测及绕过&#xff08;JS检测与绕过&#xff09;三、服务端检测3.1 后缀名检测与绕过3.2 MIME类型检测与绕过3.3 文件内容检测与绕过3.4 00截断检测与绕过3.5 条件竞争检测与绕过 一、文件上传漏洞原理 上传文件时&#xff0c;如果服务…

虾皮什么商品好卖

在虾皮&#xff08;Shopee&#xff09;平台上&#xff0c;有许多商品类别都表现出了较好的销售情况。然而&#xff0c;随着时间和地区的变化&#xff0c;热销商品也会有所不同。本文将介绍一些在虾皮平台上表现较好的商品类别&#xff0c;并提供一些建议&#xff0c;帮助您在虾…

SystemUI下拉通知菜单栏定时自动隐藏

前言 在系统应用开发过程中&#xff0c;常常遇到一些特殊的需求&#xff0c;Android原生的应用并无此适配&#xff0c;此时需要对系统应用进行定制化开发。 目前遇到的这样一个需求&#xff1a;下拉通知菜单栏时&#xff0c;定时8秒后自动关闭通知菜单栏。通知菜单栏为Sytstem…

docke网络之bridge、host、none

一、bridge网络 1.创建一个测试容器 [rootlocalhost ~]# docker run -d -it --name busybox_1 busybox /bin/sh -c "while true;do sleep 3600;done" 03b308c847edd23f21ba69afb825d92f7aaeb05b1ff4431dd47ccee439a0361a 2.查看当前机器docker有哪些网络 [rootlocal…