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

最小生成树笔记(Prim算法Kruskal算法)

1.最小生成树

最小生成树(Minimum Spanning Tree,简称MST)是指:在一个连通无向图中,找到一个包含所有顶点的树,且该树的所有边的权重之和最小。

换句话说,最小生成树是原图中的一个子图,它包含所有顶点,并且连接所有顶点的边的权重之和最小。


最小生成树的定义有以下特点:

  1. 最小生成树是无向图的一种树形结构,其中没有环(即没有闭合路径)。
  2. 最小生成树包含图中的所有顶点,但只包含足够数量的边来连接这些顶点,使得树成为一个连通的图。
  3. 最小生成树的总权重(边的权重之和)应该最小,即从所有可能的生成树中选择边权重之和最小的树。

最小生成树算法的目标是找到满足上述条件的最优解,常用的算法包括Prim算法和Kruskal算法。这些算法可以在连通无向图中找到最小生成树,并且在不同应用中具有重要的应用价值,如网络设计、电路布线、城市规划等。


2.Prim算法

Prim算法是一种用于求解最小生成树的贪心算法

它从图的某个顶点开始,逐步将距离当前生成树最近的顶点加入生成树,直到所有顶点都被包含在最小生成树中。

Prim算法的基本思想是通过不断地选择与当前生成树最近的顶点,并将该顶点与生成树中的一个顶点连接,来逐步构造最小生成树。

Prim算法的步骤如下:

  1. 选择一个起始顶点作为初始生成树,将该顶点加入生成树中。
  2. 初始化一个辅助数据结构(如优先队列或最小堆),用于存储与当前生成树相连的边,并按边的权重值排序。
  3. 在辅助数据结构中选择权重最小的边(即与当前生成树最近的边),将其相连的顶点加入生成树,并将该边从辅助数据结构中移除。
  4. 重复步骤3,直到所有顶点都被包含在生成树中。

Prim算法的过程可以保证生成的树是连通的,并且是最小生成树。它的时间复杂度取决于辅助数据结构的实现方式,一般情况下为O(ElogV),其中E是图的边数,V是图的顶点数。


3.Kruskal算法

Kruskal算法也是一种用于求解最小生成树的贪心算法。

它与Prim算法类似,但在选择边的方式上略有不同。Kruskal算法是基于边来构建最小生成树的,而不是基于顶点。

Kruskal算法的基本思想是从图的边集合中选择权重最小的边,并将其加入生成树中,直到生成树中包含了所有的顶点为止。

在选择边的过程中,需要保证生成树不形成环路,因此可以使用并查集来辅助判断两个顶点是否处于同一个连通分量。

Kruskal算法的步骤如下:

  1. 将图的所有边按照权重值从小到大排序。
  2. 初始化一个并查集,用于判断顶点之间的连通性。
  3. 依次遍历排序后的边集合,如果当前边的两个顶点不在同一个连通分量中,就将该边加入生成树,并合并两个顶点所在的连通分量。
  4. 重复步骤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分页

分页依赖&#xff1a; <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper-spring-boot-starter</artifactId> <version>1.0.0</version> </dependency> 配置&#xff1a; …...

Win7 专业版Windows time w32time服务电脑重启后老是已停止

环境&#xff1a; Win7 专业版 问题描述&#xff1a; Win7 专业版Windows time w32time服务电脑重启后老是已停止 解决方案&#xff1a; 1.检查启动Remote Procedure Call (RPC)、Remote Procedure Call (RPC) Locator&#xff0c;DCOM Server Process Launcher这三个服务是…...

全网最强,接口自动化测试-token登录关联实战总结(超详细)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 在PC端登录公司的…...

OLAP ModelKit Crack,ADO.NET和IList

OLAP ModelKit Crack,ADO.NET和IList OLAP ModelKit是一个多功能的.NET OLAP组件&#xff0c;用C#编写&#xff0c;只包含100%托管代码。它具有XP主题的外观&#xff0c;并能够使用任何.NET数据源(ADO.NET和IList)。借助任何第三方组件(尤其是图表组件)呈现数据的能力扩展了产品…...

4 三组例子,用OpenCV玩转图像-AI-python

读取&#xff0c;缩放&#xff0c;旋转&#xff0c;写入图像 首先导入包&#xff0c;为了显示导入matplotlib/为了在matplotlib显示 导入CV2/查看版本 导入图片/查看图片类型 图片数组 数组大小 对于opencv通道顺序蓝色B、绿色G、红色R matplotlib通道顺序为 红色R、绿色G、蓝…...

计算机网络-三种交换方式

计算机网络-三种交换方式 电路交换(Circuit Switching) 电话交换机接通电话线的方式称为电路交换从通信资源分配的角度来看&#xff0c;交换(Switching)就是按照某种方式动态的分配传输线路的资源 电话交换机 为了解决电话之间通信两两之间连线过多&#xff0c;所以产生了电话…...

03 制作Ubuntu启动盘

1 软碟通 我是用软碟通制作启动盘。安装软碟通时一定要把虚拟光驱给勾选上&#xff0c;其余两个可以看你心情。 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是在操作系统运行之前执行的一段小程序。通过这段小程序可以初始化硬件设备、建立内存空间的映射表&#xff0c;从而建立适当的系统软硬件环境&#xff0c;为最终调用操作系统内核做好准备。 对于嵌入式系统&#xff0c;Bootloader是基于特定硬件平台来实现的。因此…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...