当前位置: 首页 > 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按钮 点击之后会弹出选择图片的方式 拍照或从相册选择图片后将会跳到图片裁剪 然后我们裁剪完之后点击确定在上传图片 这里是上传图片的接口 拿到本地图片 上传的话自己想以那种方式上传都可以...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...