【数据结构(邓俊辉)学习笔记】图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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算法的效率也可借助优先级队列进一步提高。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/345564.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【算法小记】深度学习——时间序列数据分析 Time series Data Analysis

在本篇博客中将简单介绍常见的几种循环神经网络和一维卷积神经网络,并使用一些简答的数据进行拟合分析。本文相对适合刚入门的同学,同时也作为自己过去一段时间学习的总结和记录,现在神经网络框架已经非常完善的支持了很多常见和有效的深度学…

Channels无法使用ASGI问题

Django Channels是一个基于Django的扩展, 用于处理WebSockets, 长轮询和触发器事件等实时应用程序. 它允许Django处理异步请求, 并提供了与其他WebSockets库集成的功能.当我们在Django Channels中使用ASGI_APPLICATION设置时, 我们可以指定一个新的ASGI应用程序来处理ASGI请求.…

Linux基础I/O

一&#xff0c;系统文件I/O 写文件: #include <stdio.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <unistd.h> #include <string.h> int main() {umask(0);int fd open("myfile", O_WRO…

Docker高级篇之Docker微服务实战

文章目录 1. 构建一个简单的微服务项目2. 编写Dockerfile发布微服务部署到docker容器 1. 构建一个简单的微服务项目 创建一个SpringBoot项目 创建一个Controller RestController public class OrderController {Value("${server.port")private String port;Reques…

C语言:双链表

一、什么是双链表&#xff1f; 双链表&#xff0c;顾名思义&#xff0c;是一种每个节点都包含两个链接的链表&#xff1a;一个指向下一个节点&#xff0c;另一个指向前一个节点。这种结构使得双链表在遍历、插入和删除操作上都表现出色。与单链表相比&#xff0c;双链表不仅可以…

Rust 实战丨SSE(Server-Sent Events)

&#x1f4cc; SSE&#xff08;Server-Sent Events&#xff09;是一种允许服务器向客户端浏览器推送信息的技术。它是 HTML5 的一部分&#xff0c;专门用于建立一个单向的从服务器到客户端的通信连接。SSE的使用场景非常广泛&#xff0c;包括实时消息推送、实时通知更新等。 S…

C++中的priority_queue和deque以及适配器

C中的priority_queue和deque 一丶 priority_queue1.1 priority_queue的介绍1.2 priority_queue的使用1.3 priority_queue的模拟实现 二丶 deque2.1 deque的简单介绍2.2 deque的缺陷2.3 为什么要选择deque作为stack和queue的迭代器 三丶 容器适配器3.1 什么是适配器3.2 STL标准库…

Effective Java 2 遇到多个构造器参数时要考虑使用构建器

第2个经验法则&#xff1a;用遇到多个构造器参数时要考虑使用构建器&#xff08;consider a builder when faced with many constructor parameters&#xff09; 上一条讨论了静态工厂相对于构造器来说有五大优势。但静态工厂和构造器有个共同的局限性:它 们都不能很好地扩展到…

开源网关Apache APISIX启用JWT身份验证

说明&#xff1a; 本文APISIX的配置参考我之前写的《Ubuntu部署Apache APISIX》 创建最小API 首先&#xff0c;确保你已经安装了.NET 6 SDK。创建文件夹“MinimalApiDemo”&#xff0c;VS Code打开文件夹&#xff0c;打开终端 dotnet new web -o MinimalApiDemo cd Minimal…

【JMeter接口测试工具】第二节.JMeter基本功能介绍(上)【入门篇】

文章目录 前言一、获取所有学院信息接口执行二、线程组的介绍 2.1 并发和顺序执行 2.2 优先和最后执行线程组 2.3 线程组的设置细节三、HTTP请求的介绍四、查看结果树的配置使用总结 前言 一、获取所有学院信息接口执行 我们先针对一条简单的接口进行执行&#…

代码随想录刷题笔记-哈希表篇

文章目录 242 有效的字母异位词(easy)力扣地址题目描述题目实例解题思路代码实现 383 赎金信(easy)力扣地址题目描述题目实例解题思路代码实现 49 字母异位词分组(mid)力扣地址题目描述题目实例解题思路代码实现 438 找到字符串中所有字母异位词(mid)力扣地址题目描述题目实例解…

3038. 相同分数的最大操作数目 I(Rust模拟击败100%Rust用户)

题目 给你一个整数数组 nums &#xff0c;如果 nums 至少 包含 2 个元素&#xff0c;你可以执行以下操作&#xff1a; 选择 nums 中的前两个元素并将它们删除。 一次操作的 分数 是被删除元素的和。 在确保 所有操作分数相同 的前提下&#xff0c;请你求出 最多 能进行多少次…

SpringBoot整合钉钉实现消息推送

前言 钉钉作为一款企业级通讯工具&#xff0c;具有广泛的应用场景&#xff0c;包括但不限于团队协作、任务提醒、工作汇报等。 通过Spring Boot应用程序整合钉钉实现消息推送&#xff0c;我们可以实现以下功能&#xff1a; 实时向指定用户或群组发送消息通知。自定义消息内容…

Python进阶-部署Flask项目(以TensorFlow图像识别项目WSGI方式启动为例)

本文详细介绍了如何通过WSGI方式部署一个基于TensorFlow图像识别的Flask项目。首先简要介绍了Flask框架的基本概念及其特点&#xff0c;其次详细阐述了Flask项目的部署流程&#xff0c;涵盖了服务器环境配置、Flask应用的创建与测试、WSGI服务器的安装与配置等内容。本文旨在帮…

【iOS】——Runtime学习

文章目录 一、Runtime介绍二、Runtime消息传递三、实例对象、类对象、元类对象四、isa_t结构体的具体实现五、cache_t的具体实现六、class_data_bits_t的具体实现七、Runtime消息转发动态方法解析备用接收者完整消息转发 一、Runtime介绍 iOS的Runtime&#xff0c;通常称为Obj…

使用汇编和proteus实现仿真数码管显示电路

proteus介绍&#xff1a; proteus是一个十分便捷的用于电路仿真的软件&#xff0c;可以用于实现电路的设计、仿真、调试等。并且可以在对应的代码编辑区域&#xff0c;使用代码实现电路功能的仿真。 汇编语言介绍&#xff1a; 百度百科介绍如下&#xff1a; 汇编语言是培养…

【通俗易懂的Python入门基础详细教程,可分享哦!!!】

Python&#xff0c;作为一种高级编程语言&#xff0c;自其诞生以来就以其独特的魅力吸引了无数开发者。以下是对学习Python的简要介绍&#xff1a; 一、Python的起源与发展 Python由荷兰计算机科学家吉多范罗苏姆于1990年代初设计&#xff0c;其设计初衷是作为ABC语言的替代品…

计算机网络复习题

期末题库复习1 一. 单选题&#xff08;共32题&#xff0c;100分&#xff09; 1. (单选题) 在脉冲起始时刻&#xff0c;有无跳变来表示“0”和“1”&#xff0c;且在脉冲中间时刻始终发生跳变的编码是&#xff08; &#xff09;。 A.非归零码 B.曼彻斯特编码 C.归零码 D.差…

Facebook革新:数字社交的下一个阶段

在数字化时代&#xff0c;社交网络已经成为人们生活中不可或缺的一部分。作为全球最大的社交网络平台之一&#xff0c;Facebook一直在不断创新&#xff0c;引领着数字社交的发展。然而&#xff0c;随着科技的不断进步和社交需求的变化&#xff0c;Facebook正在走向一个新的阶段…

k8s和deepflow部署与测试

Ubuntu-22-LTS部署k8s和deepflow 环境详情&#xff1a; Static hostname: k8smaster.example.net Icon name: computer-vm Chassis: vm Machine ID: 22349ac6f9ba406293d0541bcba7c05d Boot ID: 605a74a509724a88940bbbb69cde77f2 Virtualization: vmware Operating System: U…