数据结构之生成树及最小生成树
数据结构之生成树及最小生成树
- 1、生成树概念
- 2、最小生成树
数据结构是程序设计的重要基础,它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发,分析和研究计算机加工的数据的特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法,为提高利用计算机解决问题的效率服务。
数据结构是指数据元素的集合及元素间的相互关系和构造方法。元素之间的相互关系是数据的 逻辑结构,数据元素及元素之间关系的存储称为 存储结构(或物理结构)。数据结构按照逻辑关系的不同分为 线性结构和 非线性结构两大类,其中,非线性结构又可分为树结构和图结构。
树结构是一种非常重要的非线性结构,该结构中的一个数据元素可以有两个或两个以上的直接后继元素,树可以用来描述客观世界中广泛存在的层次结构关系。
1、生成树概念
对于有n个顶点的连通图,至少有n-1条边,而生成树中恰好有n-1条边,所以连通图的生成树是该图的极小连通子图。若在图的生成树中任意加一条边,则必然形成回路。下图(a)所示的无向图的一个生成树如下图(b)所示,下图(c)不是生成树,因为存在回路。
图的生成树不是唯一的。从不同的顶点出发,选择不同的存储方式,用不同的求解方法,可以得到不同的生成树。对于非连通图而言,每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树,把它们称为非连通图的生成树森林。按深度和广度优先搜索进行遍历将得到不同的生成树,分别称为深度优先生成树和广度优先生成树。例如,下图所示的是上图(a)的一棵深度优先生成树和一棵广度优先生成树。
2、最小生成树
对于连通网来说,边是带权值的,生成树的各边也带权值,因此把生成树各边的权值总和称为生成树的权,把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。
常用的最小生成树求解算法有普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。
(1)普里姆(Prim)算法。
假设N=(V,E)是连通网,TE是N上最小生成树中边的集合。算法从顶点集合U={u0}(u0∈V)、边的集合TE={}开始,重复执行下述操作:在所有u∈U, v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0),把这条边并入集合TE,同时将v0并入集合U,直到U=V时为止。此时TE中必有n-1条边,T=(V,{TE})为N的最小生成树。
由此可知,普里姆算法构造最小生成树的过程是以一个顶点集合U={u0}作为初态,不断寻找与U中顶点相邻且代价最小的边的另一个顶点,扩充U集合直到U=V时为止。
用普里姆算法构造最小生成树的过程如下图所示。
普里姆算法的时间复杂度为0(n2),与图中的边数无关,因此该算法适合于求边稠密的网的最小生成树。
(2)克鲁斯卡尔(Kruskal)算法。
克鲁斯卡尔求最小生成树的算法思想为:假设连通网N(V,E),令最小生成树的初始状态为只有 n 个项点而无边的非连通图 T=(V,{}),图中每个顶点自成一个连通分量。在E选择代价最小的边,若该边依附的项点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。依此类推,直到T中所有顶点都在同一连通分量上为止。
用克鲁斯卡尔算法构造上图(a)所示网的最小生成树的过程如下图所示。
克售斯卡尔算法的时间复杂度为 O(e㏒e),与图中的顶点数无关,因此该算法适合于求边稀疏的网的最小生成树。
相关文章:

数据结构之生成树及最小生成树
数据结构之生成树及最小生成树 1、生成树概念2、最小生成树 数据结构是程序设计的重要基础,它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发,分析和研究计算机加工的数据的特性,以便为应用所…...

【java面试】常见问题(超详细)
目录 一、java常见问题JDK和JRE的区别是什么?Java中的String类是可变的还是不可变的?Java中的equals方法和hashCode方法有什么关系?Java中什么是重载【Overloading】?什么是覆盖【Overriding】?它们有什么区别…...

Labview for循环精讲
本文详细介绍Labview中For循环的使用方法,从所有细节让你透彻的看明白For循环是如何使用的,如果有帮助的话记得点赞加关注~ 1. For循环结构 从最简单的地方讲起,一个常用的for循环结构是由for循环结构框图、循环次数、循环计数(i)三部分组成…...

【STM32】STM32学习笔记-W25Q64简介(37)
00. 目录 文章目录 00. 目录01. SPI简介02. W25Q64简介03. 硬件电路04. W25Q64框图05. Flash操作注意事项06. 预留07. 附录 01. SPI简介 在大容量产品和互联型产品上,SPI接口可以配置为支持SPI协议或者支持I 2 S音频协议。SPI接口默认工作在SPI方式,可以…...
clickhouse数据库 使用http 方式交付查询sql
今天使用clickhouse 的HTTP 方式进行查询语句 clickhouse 服务 搭建在192.168.0.111 上面 那么我们如何快速的去查询呢 如下 我们可以使用curl 功能 或者直接在浏览器上输入对应的查询命令 如下: http://192.168.0.111:8123/userdefault&password123456&…...

深度学习-循环神经网络-RNN实现股价预测-LSTM自动生成文本
序列模型(Sequence Model) 基于文本内容及其前后信息进行预测 基于目标不同时刻状态进行预测 基于数据历史信息进行预测 序列模型:输入或者输出中包含有序列数据的模型 突出数据的前后序列关系 两大特点: 输入(输出)元素之间是具有顺序关系。不同的顺序,得到的结果应…...

案例分享 | 助力数字化转型:嘉为科技项目管理平台上线
嘉为科技项目管理平台(一期)基于易趋(EasyTrack)进行实施,通过近一年的开发及试运行,现已成功交付上线、推广使用,取得了良好的应用效果。 1.关于广州嘉为科技有限公司(以下简称嘉为…...
深入理解 MySQL 中的 HAVING 关键字和聚合函数
深入理解 MySQL 中的 HAVING 关键字和聚合函数 在处理数据库查询时,尤其是涉及到大量数据分析和报表生成的场合,了解如何有效使用 SQL 语句中的 HAVING 关键字和聚合函数变得尤为重要。 什么是 HAVING 关键字? HAVING 关键字在 SQL 语句中…...
GPT4.5人工智能即将来临,ChatGPT的正面影响和负面影响(好处和坏处),利弊分析
ChatGPT来了,对我们影响大不大? 近年来,人工智能技术的飞速进步催生了ChatGPT——一种强大的人工智能语言模型。其杰出的生成能力使其能够与人类进行自然、流畅的交流,从而在教育、医疗和娱乐等多个领域展现出巨大的应用潜力。然…...
条款47:请使用traits classes表现类型信息
1.前言 STL主要由“用以表现容器,迭代器和算法”的template构成,但也覆盖若干工具性templates,其中一个名为advance,用来将某个迭代器移动某个给定距离: tempalte<typename IterT,typename DistT>//将迭代器向…...

蓝桥杯省赛无忧 课件49 DFS-剪枝
01 数字王国之军训排队 02 特殊的三角形 03 特殊的多边形...

Linux中查看端口被哪个进程占用、进程调用的配置文件、目录等
1.查看被占用的端口的进程,netstat/ss -antulp | grep :端口号 2.通过上面的命令就可以列出,这个端口被哪些应用程序所占用,然后找到对应的进程PID https://img-blog.csdnimg.cn/c375eb2bed754426b373907acaa7346e.png 3.根据PID查询进程。…...
大模型面试题总结
文章目录 一、大模型(LLMs)基础面二、大模型(LLMs)进阶面三、大模型(LLMs)微调面四、大模型(LLMs)langchain面1. 基于LLM+向量库的文档对话 基础面2. 基于LLM+向量库的文档对话 优化面3. LangChain的概念面试问题4.LangChain的一些模块提问5.LangChain的业务提问6.Lang…...

Authorization Failed You can close this page and return to the IDE
一.问题描述 注册JetBrains成功,并且通过了学生认证,但在activate pycharm时,却显示Authorization Failed You can close this page and return to the IDE如上图 二.原因: 可能是因为之前使用了破解版pycharm 三.解决方法&am…...

【时间序列篇】基于LSTM的序列分类-Pytorch实现 part2 自有数据集构建
系列文章目录 【时间序列篇】基于LSTM的序列分类-Pytorch实现 part1 案例复现 【时间序列篇】基于LSTM的序列分类-Pytorch实现 part2 自有数据集构建 【时间序列篇】基于LSTM的序列分类-Pytorch实现 part3 化为己用 在一个人体姿态估计的任务中,需要用深度学习模型…...
《设计模式的艺术》笔记 - 策略模式
介绍 策略模式定义一系列算法类,将每一个算法封装起来,并让它们可以相互替换。策略模式让算法独立于使用它的客户而变化,也称为政策模式。策略模式是一种对象行为模式。 实现 myclass.h // // Created by yuwp on 2024/1/12. //#ifndef DES…...

【Elasticsearch篇】详解使用RestClient操作索引库的相关操作
文章目录 🍔什么是Elasticsearch🌺什么是RestClient🎆代码操作⭐初始化RestClient⭐使用RestClient操作索引库⭐使用RestClient删除索引库⭐使用RestClient判断索引库是否存在 🍔什么是Elasticsearch Elasticsearch是一个开源的分…...
ES数据处理方法
由于日志数据存在ES项目里,需要从ES中获取日志进行分析,使用SQL数据进行处理,如下: select traceid-- STRING COMMENT 流程id, ,appnum -- BIGINT COMMENT 迭代号, ,appversion --STRING COMMENT APP版本, ,appc…...

STM32实现软件IIC协议操作OLED显示屏(2)
时间记录:2024/1/27 一、OLED相关介绍 (1)显示分辨率128*64点阵 (2)IIC作为从机的地址0x78 (3)操作步骤:主机先发送IIC起始信号S,然后发送OLED的地址0x78,然…...

【linux】远程桌面连接到Debian
远程桌面连接到Debian系统,可以使用以下几种工具: 1. VNC (Virtual Network Computing) VNC(Virtual Network Computing)是一种流行的远程桌面解决方案,它使用RFB(Remote Framebuffer Protocol࿰…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...

【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...