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

数据结构之生成树及最小生成树

数据结构之生成树及最小生成树

  • 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】?它们有什么区别&#xf…...

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主要由“用以表现容器&#xff0c;迭代器和算法”的template构成&#xff0c;但也覆盖若干工具性templates&#xff0c;其中一个名为advance&#xff0c;用来将某个迭代器移动某个给定距离&#xff1a; tempalte<typename IterT,typename DistT>//将迭代器向…...

蓝桥杯省赛无忧 课件49 DFS-剪枝

01 数字王国之军训排队 02 特殊的三角形 03 特殊的多边形...

Linux中查看端口被哪个进程占用、进程调用的配置文件、目录等

1.查看被占用的端口的进程&#xff0c;netstat/ss -antulp | grep :端口号 2.通过上面的命令就可以列出&#xff0c;这个端口被哪些应用程序所占用&#xff0c;然后找到对应的进程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成功&#xff0c;并且通过了学生认证&#xff0c;但在activate pycharm时&#xff0c;却显示Authorization Failed You can close this page and return to the IDE如上图 二.原因&#xff1a; 可能是因为之前使用了破解版pycharm 三.解决方法&am…...

【时间序列篇】基于LSTM的序列分类-Pytorch实现 part2 自有数据集构建

系列文章目录 【时间序列篇】基于LSTM的序列分类-Pytorch实现 part1 案例复现 【时间序列篇】基于LSTM的序列分类-Pytorch实现 part2 自有数据集构建 【时间序列篇】基于LSTM的序列分类-Pytorch实现 part3 化为己用 在一个人体姿态估计的任务中&#xff0c;需要用深度学习模型…...

《设计模式的艺术》笔记 - 策略模式

介绍 策略模式定义一系列算法类&#xff0c;将每一个算法封装起来&#xff0c;并让它们可以相互替换。策略模式让算法独立于使用它的客户而变化&#xff0c;也称为政策模式。策略模式是一种对象行为模式。 实现 myclass.h // // Created by yuwp on 2024/1/12. //#ifndef DES…...

【Elasticsearch篇】详解使用RestClient操作索引库的相关操作

文章目录 &#x1f354;什么是Elasticsearch&#x1f33a;什么是RestClient&#x1f386;代码操作⭐初始化RestClient⭐使用RestClient操作索引库⭐使用RestClient删除索引库⭐使用RestClient判断索引库是否存在 &#x1f354;什么是Elasticsearch Elasticsearch是一个开源的分…...

ES数据处理方法

由于日志数据存在ES项目里&#xff0c;需要从ES中获取日志进行分析&#xff0c;使用SQL数据进行处理&#xff0c;如下&#xff1a; select traceid-- STRING COMMENT 流程id, ,appnum -- BIGINT COMMENT 迭代号, ,appversion --STRING COMMENT APP版本, ,appc…...

STM32实现软件IIC协议操作OLED显示屏(2)

时间记录&#xff1a;2024/1/27 一、OLED相关介绍 &#xff08;1&#xff09;显示分辨率128*64点阵 &#xff08;2&#xff09;IIC作为从机的地址0x78 &#xff08;3&#xff09;操作步骤&#xff1a;主机先发送IIC起始信号S&#xff0c;然后发送OLED的地址0x78&#xff0c;然…...

【linux】远程桌面连接到Debian

远程桌面连接到Debian系统&#xff0c;可以使用以下几种工具&#xff1a; 1. VNC (Virtual Network Computing) VNC&#xff08;Virtual Network Computing&#xff09;是一种流行的远程桌面解决方案&#xff0c;它使用RFB&#xff08;Remote Framebuffer Protocol&#xff0…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

《从零掌握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;导线&#…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...