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

【数据结构(邓俊辉)学习笔记】图06——最小支撑树

文章目录

  • 0. 概述
  • 1. 支撑树
  • 2. 最小支撑树
  • 3. 歧义性
  • 4. 蛮力算法
  • 5. Prim算法
    • 5.1 割与极短跨越边
    • 5.2 贪心迭代
    • 5.3 实例
    • 5.4 实现
    • 5.5 复杂度

0. 概述

学习下最小支撑树和prim算法。

1. 支撑树

在这里插入图片描述
最小的连通图是树。

连通图G的某一无环连通子图T若覆盖G中所有的顶点,则称作G的一棵支撑树或生成树(spanning tree)。

就保留原图中边的数目而言,支撑树既是“禁止环路”前提下的极大子图,也是“保持连通”前提下的最小子图。

确切地,尽管同一幅图可能有多棵支撑树,但由于其中的顶点总数均为n,故其采用的边数也均为n - 1。

2. 最小支撑树

在这里插入图片描述

若图G为一带权网络,则每一棵支撑树的成本(cost)即为其所采用各边权重的总和。在G的所有支撑树中,成本最低者称作最小支撑树(minimum spanning tree, MST)。

3. 歧义性

尽管同一带权网络通常都有多棵支撑树,但总数毕竟有限,故必有最低的总体成本。然而,总体成本最低的支撑树却未必唯一。
在这里插入图片描述
最小支撑树允许有负数,因为它算的是total cast。

若有重边,通过强制附加某种次序即可消除这种歧义性。

4. 蛮力算法

在这里插入图片描述
由最小支撑树的定义,可直接导出蛮力算法大致如下:逐一考查G的所有支撑树并统计其成本,从而挑选出其中的最低者。然而根据Cayley公式,由n个互异顶点组成的完全图共有 n n − 2 n^{n-2} nn2棵支撑树,即便忽略掉构造所有支撑树所需的成本,仅为更新最低成本的记录就需要O( n n − 2 n^{n-2} nn2)时间。

事实上基于PFS搜索框架,并采用适当的顶点优先级更新策略,即可得出如下高效的最小支撑树构造算法。

5. Prim算法

5.1 割与极短跨越边

在这里插入图片描述
图G = (V; E)中,顶点集V的任一非平凡子集U及其补集V\U都构成G的一个割(cut),记作(U : V\U)。若边uv满足u∈U且v∈V\U,则称作该割的一条跨越边(crossing edge)。因此类边联接于V及其补集之间,故亦形象地称作该割的一座桥(bridge)。

Prim算法的正确性基于以下事实:最小支撑树总是会采用联接每一割的最短跨越边

5.2 贪心迭代

在这里插入图片描述

5.3 实例

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

5.4 实现

这个实现无非就是一个PFS。

在这里插入图片描述
这棵子树上的点认为都访问过了,没有访问的点(补集上的点)手上都拥有一个优先级数,这个数就是代表它到子树的距离,这个距离在任何时刻各自都会实现于某个特定的点,每次要做的事就是在树中找到最小的把它拓展进来,接下来再update。

在这里插入图片描述
接下来就是为prim算法写一个优先级更新器,实现更新算法。实现流程:

在当前图g中,如果有一个点uk刚刚被扩展进来,加入到这棵树中,对于它的每个尚未被发现的邻居v,按照prim策略做松弛。首先判断下当前的提供的优先级数是否更好,如果当前的优先级数更好便会欣然接受这个。再更新下v的父亲。

5.5 复杂度

目前只是把算法将明白了,数据结构还差的很远,每次查找优先级数还比较慢,以上Prim算法的时间复杂度为O( n 2 n^2 n2)。作为PFS搜索的特例,Prim算法的效率也可借助优先级队列进一步提高。

相关文章:

【数据结构(邓俊辉)学习笔记】图06——最小支撑树

文章目录 0. 概述1. 支撑树2. 最小支撑树3. 歧义性4. 蛮力算法5. Prim算法5.1 割与极短跨越边5.2 贪心迭代5.3 实例5.4 实现5.5 复杂度 0. 概述 学习下最小支撑树和prim算法。 1. 支撑树 最小的连通图是树。 连通图G的某一无环连通子图T若覆盖G中所有的顶点,则称…...

海豚调度清理:使用 API 轻松清理历史工作流实例以及日志文件

💡 本系列文章是 DolphinScheduler 由浅入深的教程,涵盖搭建、二开迭代、核心原理解读、运维和管理等一系列内容。适用于想对 DolphinScheduler了解或想要加深理解的读者。 祝开卷有益。 大数据学习指南 大家好,我是小陶,DolphinS…...

python怎么显示行号

我们如果想让Python IDLE显示行号,我们可以通过扩展IDLE功能来做到。 1.我们需要下载一个LineNumber.py扩展。 2.我们打开Python安装目录,找到安装目录下的Lib\idlelib目录,复制LineNumber到这个目录。 3.然后启动扩展。 4.配置扩展的方式…...

pytorch中,load_state_dict和torch.load的区别?

在 PyTorch 中,load_state_dict 和 torch.load 是两个不同的函数,用于不同的目的。 torch.load: 用途: 从磁盘加载一个保存的对象。这个对象可以是一个模型的整个状态字典(包含模型参数)、优化器状态字典、甚至是任意其他 Python …...

ObjectARX打印当前图纸为PDF,无延迟(亲测有效)

CAD二次开发定制ObjectARX安装配置AutoCAD插件ZWCAD插件C++ //----------------------------------------------------------------------------- //----- acrxEntryPoint.cpp //----------------------------------------------------------------------------- #include &quo…...

torch.squeeze() dim=1 dim=-1 dim=2

对数据的维度进行压缩 使用方式:torch.squeeze(input, dimNone, outNone) 将输入张量形状中的1 去除并返回。 如果输入是形如(A1B1C1D),那么输出形状就为: (ABCD) import torch x torch.rand(2, 1, 1, 3, 1, 4) print(x) print(x.shape) …...

智慧环保一体化平台简介

据悉,环保问题日益受到人们的关注,智慧环保一体化平台作为解决环保问题的有力工具,正逐渐走进人们的视野。朗观视觉智慧环保一体化平台通过整合各类环保资源,实现环境数据的实时监测、分析与管理,为环境保护提供智能化…...

idea在空工程中添加新模块并测试的步骤

ServicesTest是空的工程,没有pom文件。现在需要在ServicesTest目录下添加新模块作为新的工程,目的是写一下别的技术功能。 原先目录结构,ServicesTest是空的工程,没有pom文件。下面的几个模块是新的工程,相互独立。 1.…...

HCIE-QOS基本原理

QOS基本原理 QOS概述什么是QOSQoS服务模型区分服务模型QoS常用技术 (DiffServ模型)QoS数据处理流程 (DiffServ模型) QoS流分类和流标记QoS数据处理流程为什么需要流分类和流标记 简单流分类外部优先级 - VLAN报文外部优先级 - MPLS报文外部优先级 - IP报文各外部优先级间的对应…...

pycharm基本使用(常用快捷键)

0.下载 pycharm官网下载 选择合适的版本,本文以2024.1为例 1.简单应用 常用快捷键 ctrlD 复制当前行 ctrlY 删除当前行 ctrlX 剪切当前行(可用作删除,更顺手) shift↑ 选中多行ctrlshiftF10 运行 shiftF9 调试ctrl/ 注释当前…...

机器学习--回归模型和分类模型常用损失函数总结(详细)

文章目录 引言 回归模型常用损失函数均方误差(Mean Squared Error, MSE)均方根误差(Root Mean Squared Error, RMSE)平均绝对误差(Mean Absolute Error, MAE)Huber损失(Huber Loss) …...

企业选择数字工厂管理系统供应商的标准是什么

随着信息技术的飞速发展,数字化转型已成为企业提升竞争力、实现可持续发展的必由之路。在制造业领域,数字工厂管理系统实现生产流程自动化、智能化的关键工具,其选择的重要性不言而喻。本文将从多个维度探讨企业选择数字工厂管理系统供应商的…...

京准电钟|基于纳秒级的GPS北斗卫星授时服务器

京准电钟|基于纳秒级的GPS北斗卫星授时服务器 京准电钟|基于纳秒级的GPS北斗卫星授时服务器 你有没有思考过这样一个问题:火车站内,熙熙攘攘,旅客排队进站、列车停靠发车,一切井然有序。一旦有个别时间出现…...

Flutter知识点

Dart语言基础知识 Dart特性: Dart 是少数同时支持 JIT(Just In Time,即时编译)和 AOT(Ahead of Time,运行前编译)的语言之一。语言在运行之前通常都需要编译,JIT 和 AOT 则是最常见…...

2024-06-12 问AI: 在大语言模型中,什么是Jailbreak漏洞?

文心一言 在大语言模型中,Jailbreak漏洞(也称为越狱攻击或指令注入攻击)是一种特定的安全漏洞,它允许用户或攻击者通过精心设计的输入或指令,绕过模型的安全限制,诱导模型产生原本被设定为禁止或限制的输出…...

Vue22-v-model收集表单数据

一、效果图 二、代码 2-1、HTML代码 2-2、vue代码 1、v-model单选框的收集信息 v-model:默认收集的就是元素中的value值。 单选框添加默认值: 2、v-model多选框的收集信息 ①、多个选择的多选 注意: 此处的hobby要是数组!&…...

【深度学习】深入解码:提升NLP生成文本的策略与参数详解

文章目录 解码策略解码参数公式解释代码例子区别 更详细的束搜索的解释更详细的例子解释第一步第二步第三步 解码策略和解码参数在自然语言处理(NLP)模型的生成过程中起着不同的作用,但它们共同决定了生成文本的质量和特性。 解码策略 解码…...

Petalinux由于网络原因产生的编译错误(2)--Fetcher failure:Unable to find file

1 Fetcher failure:Unable to find file 错误 如果编译工程遇到如下图所示的“Fetcher failure for URL”或相似错误 出现这种错误的原因是 Petalinux 在配置和编译的时候,需要联网下载一些文件,由于网 络原因这些文件不能正常下载,导致编译…...

随手记:商品信息过多,展开收起功能

UI原型图&#xff1a; 页面思路&#xff1a; 在商品信息最小item外面有一个包裹所有item的标签&#xff0c;控制这个标签的高度来实现展开收起功能 <!-- 药品信息 --><view class"drugs" v-if"inquiryInfoSubmitBtn"><view class"…...

uniapp上传头像并裁剪图片

第一步写上uniapp自带的选择图片button按钮 点击之后会弹出选择图片的方式 拍照或从相册选择图片后将会跳到图片裁剪 然后我们裁剪完之后点击确定在上传图片 这里是上传图片的接口 拿到本地图片 上传的话自己想以那种方式上传都可以...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...