最小生成树笔记(Prim算法Kruskal算法)
1.最小生成树
最小生成树(Minimum Spanning Tree,简称MST)是指:在一个连通无向图中,找到一个包含所有顶点的树,且该树的所有边的权重之和最小。
换句话说,最小生成树是原图中的一个子图,它包含所有顶点,并且连接所有顶点的边的权重之和最小。
最小生成树的定义有以下特点:
- 最小生成树是无向图的一种树形结构,其中没有环(即没有闭合路径)。
- 最小生成树包含图中的所有顶点,但只包含足够数量的边来连接这些顶点,使得树成为一个连通的图。
- 最小生成树的总权重(边的权重之和)应该最小,即从所有可能的生成树中选择边权重之和最小的树。
最小生成树算法的目标是找到满足上述条件的最优解,常用的算法包括Prim算法和Kruskal算法。这些算法可以在连通无向图中找到最小生成树,并且在不同应用中具有重要的应用价值,如网络设计、电路布线、城市规划等。
2.Prim算法
Prim算法是一种用于求解最小生成树的贪心算法。
它从图的某个顶点开始,逐步将距离当前生成树最近的顶点加入生成树,直到所有顶点都被包含在最小生成树中。
Prim算法的基本思想是通过不断地选择与当前生成树最近的顶点,并将该顶点与生成树中的一个顶点连接,来逐步构造最小生成树。
Prim算法的步骤如下:
- 选择一个起始顶点作为初始生成树,将该顶点加入生成树中。
- 初始化一个辅助数据结构(如优先队列或最小堆),用于存储与当前生成树相连的边,并按边的权重值排序。
- 在辅助数据结构中选择权重最小的边(即与当前生成树最近的边),将其相连的顶点加入生成树,并将该边从辅助数据结构中移除。
- 重复步骤3,直到所有顶点都被包含在生成树中。
Prim算法的过程可以保证生成的树是连通的,并且是最小生成树。它的时间复杂度取决于辅助数据结构的实现方式,一般情况下为O(ElogV),其中E是图的边数,V是图的顶点数。
3.Kruskal算法
Kruskal算法也是一种用于求解最小生成树的贪心算法。
它与Prim算法类似,但在选择边的方式上略有不同。Kruskal算法是基于边来构建最小生成树的,而不是基于顶点。
Kruskal算法的基本思想是从图的边集合中选择权重最小的边,并将其加入生成树中,直到生成树中包含了所有的顶点为止。
在选择边的过程中,需要保证生成树不形成环路,因此可以使用并查集来辅助判断两个顶点是否处于同一个连通分量。
Kruskal算法的步骤如下:
- 将图的所有边按照权重值从小到大排序。
- 初始化一个并查集,用于判断顶点之间的连通性。
- 依次遍历排序后的边集合,如果当前边的两个顶点不在同一个连通分量中,就将该边加入生成树,并合并两个顶点所在的连通分量。
- 重复步骤3,直到生成树包含了所有顶点。
Kruskal算法的过程可以保证生成的树是连通的,并且是最小生成树。它的时间复杂度取决于边排序和并查集操作的复杂度,一般情况下为O(ElogE + ElogV),其中E是图的边数,V是图的顶点数。
相关文章:
最小生成树笔记(Prim算法Kruskal算法)
1.最小生成树 最小生成树(Minimum Spanning Tree,简称MST)是指:在一个连通无向图中,找到一个包含所有顶点的树,且该树的所有边的权重之和最小。 换句话说,最小生成树是原图中的一个子图&#…...
4、数据清洗
4、数据清洗 前面我们处理的数据实际上都是已经被处理好的规整数据,但是在大数据整个生产过程中,需要先对数据进行数据清洗,将杂乱无章的数据整理为符合后面处理要求的规整数据。 数据去重 1.删除重复数据groupby().count():可以…...
Python-OpenCV 图像的基础操作
图像的基础操作 获取图像的像素值并修改获取图像的属性信息图像的ROI区域图像通道的拆分及合并图像扩边填充图像上的算术运算图像的加法图像的混合图像的位运算 获取图像的像素值并修改 首先读入一副图像: import numpy as np import cv2# 1.获取并修改像素值 # 读…...
test111
step3:多线程task 首先,实现两个UserService和AsyncUserService两个服务接口: package com.example.demospringboot.service;public interface UserService {void checkUserStatus(); }package com.example.demospringboot.service.impl;im…...
17. Spring 事务
目录 1. 事务定义 2. MySQL 中的事务使用 3. 没有事务时的插入 4. Spring 编程式事务 5. Spring 声明式事务 5.1 Transactional 作用范围 5.2 Transactional 参数说明 5.3 Transactional 工作原理 1. 事务定义 将⼀组操作封装成一个执行单元(封装到一起…...
【C# 基础精讲】运算符和表达式
在C#编程中,运算符和表达式是构建复杂逻辑的关键元素。运算符用于执行各种数学、逻辑和其他操作,而表达式则由运算符、变量、常量和函数组成,用于生成计算结果。本文将详细介绍C#中常见的运算符和表达式的概念,以及它们在程序中的…...
【搜索】DFS连通性模型
算法提高课笔记 目录 迷宫题意思路代码 红与黑题意思路代码 DFS 的搜索分为两大部分: 内部搜索:一个图中从一个点搜到另一个点外部搜索:从一张图(状态)搜到另一张图(状态) 在第一个部分里是图…...
项目优化后续 ,手撸一个精简版VUE项目框架!
之前说过项目之前用的vben框架,在优化完性能后打包效果由原来的纯代码96M变成了56M,后续来啦,通过更换框架,代码压缩到了36M撒花~ 现在就来详细说说是怎么手撸一个框架的! 方案: 搭建一套 vite vue3 a…...
【深度学习笔记】TensorFlow 基础
在 TensorFlow 2.0 及之后的版本中,默认采用 Eager Execution 的方式,不再使用 1.0 版本的 Session 创建会话。Eager Execution 使用更自然地方式组织代码,无需构建计算图,可以立即进行数学计算,简化了代码调试的过程。…...
面试题-springcloud中的负载均衡是如何实现的?
一句话导读 Springcloud中的负载均衡是通过Ribbon实现的,自带有很多负载均衡策略,如:包括轮询(Round Robin)、随机(Random)、加权轮询(Weighted Round Robin)、加权随机&…...
flink的ProcessWindowFunction函数的三种状态
背景 在处理窗口函数时,ProcessWindowFunction处理函数可以定义三个状态: 富函数getRuntimeContext.getState, 每个key每个窗口的状态context.windowState(),每个key的状态context.globalState,那么这几个状态之间有什么关系呢? …...
day50-springboot+ajax分页
分页依赖: <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper-spring-boot-starter</artifactId> <version>1.0.0</version> </dependency> 配置: …...
Win7 专业版Windows time w32time服务电脑重启后老是已停止
环境: Win7 专业版 问题描述: Win7 专业版Windows time w32time服务电脑重启后老是已停止 解决方案: 1.检查启动Remote Procedure Call (RPC)、Remote Procedure Call (RPC) Locator,DCOM Server Process Launcher这三个服务是…...
全网最强,接口自动化测试-token登录关联实战总结(超详细)
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 在PC端登录公司的…...
OLAP ModelKit Crack,ADO.NET和IList
OLAP ModelKit Crack,ADO.NET和IList OLAP ModelKit是一个多功能的.NET OLAP组件,用C#编写,只包含100%托管代码。它具有XP主题的外观,并能够使用任何.NET数据源(ADO.NET和IList)。借助任何第三方组件(尤其是图表组件)呈现数据的能力扩展了产品…...
4 三组例子,用OpenCV玩转图像-AI-python
读取,缩放,旋转,写入图像 首先导入包,为了显示导入matplotlib/为了在matplotlib显示 导入CV2/查看版本 导入图片/查看图片类型 图片数组 数组大小 对于opencv通道顺序蓝色B、绿色G、红色R matplotlib通道顺序为 红色R、绿色G、蓝…...
计算机网络-三种交换方式
计算机网络-三种交换方式 电路交换(Circuit Switching) 电话交换机接通电话线的方式称为电路交换从通信资源分配的角度来看,交换(Switching)就是按照某种方式动态的分配传输线路的资源 电话交换机 为了解决电话之间通信两两之间连线过多,所以产生了电话…...
03 制作Ubuntu启动盘
1 软碟通 我是用软碟通制作启动盘。安装软碟通时一定要把虚拟光驱给勾选上,其余两个可以看你心情。 2 镜像文件 我使用清华镜像网站找到的Ubuntu镜像文件。 Index of /ubuntu-releases/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 请自己选择镜像…...
【JavaSE】String类中常用的字符串方法(超全)
目录 1.求字符串的长度 2.判断字符串是否为空 3.String对象的比较 3.1 判断字符串是否相同 3.2 比较字符串大小 3.3 忽略大小写比较 4.字符串查找 5.转化 5.1 数值和字符串转化 5.1.1 数字转字符串 valueof 5.1.2 valueOf的其他用法 5.1.3 字符串转数字 5.2 大小写转…...
Bootload U-Boot分析
Bootloader是在操作系统运行之前执行的一段小程序。通过这段小程序可以初始化硬件设备、建立内存空间的映射表,从而建立适当的系统软硬件环境,为最终调用操作系统内核做好准备。 对于嵌入式系统,Bootloader是基于特定硬件平台来实现的。因此…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
在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…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
