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

数据结构和算法-最小生成树（prim和krusakal）和最短路径问题（BFS和dijkastra和floyd）

news 文章来源：https://blog.csdn.net/llovewuzhengzi/article/details/135039877 2025/1/13 13:43:24

文章目录

  • 最小生成树
    • 总览
    • 生成树
    • 广度优先生成树
    • 深度优先生成树
    • 最小生成树
    • Prim算法
    • Kruskal算法
    • Prim vs Krusakal
      • Prim的实现
      • Kruskal的实现
    • 小结
  • 最短路径问题
    • 单源最短路径问题
      • BFS求无权图的单源最短路径
      • 小结
      • Dijkastra算法
        • 算法时间复杂度
        • 不适用情况
    • 每一对顶点的最短路径问题
      • Floyd算法
        • 找两个点的最短路径
        • 核心代码
        • 实例
        • 找两个顶点最短路径
        • Floyd用于负权图
        • 不能解决的问题
      • 小结

最小生成树

总览

在这里插入图片描述

生成树

在这里插入图片描述

广度优先生成树

在这里插入图片描述

深度优先生成树

在这里插入图片描述

最小生成树

针对的是带权连通图
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

Prim算法

同一个图的最小生成树可能不唯一

从p城出发
在这里插入图片描述
在这里插入图片描述

从农场出发也一样
在这里插入图片描述

Kruskal算法

在这里插入图片描述

Prim vs Krusakal

在这里插入图片描述

Prim的实现

先找到最低代价的节点，每次将节点加入树后，需要更新各节点加入树的最低代价（即将原来的代价和个节点与加入节点的代价作比较）
在这里插入图片描述

Kruskal的实现

查找并查集（如果用二叉树实现的）的根需要log2E
在这里插入图片描述

小结

在这里插入图片描述

最短路径问题

在这里插入图片描述

单源最短路径问题

BFS求无权图的单源最短路径

首先访问2号顶点，然后再更新其相邻顶点后的结果
在这里插入图片描述
然后1号顶点出队，相邻节点入队，同时更新各相邻节点
在这里插入图片描述
然后6号顶点出队，更新相邻节点，同时各个相邻节点入队
在这里插入图片描述
5号顶点没有相邻
所以到3号顶点处理
在这里插入图片描述
7号顶点处理
在这里插入图片描述
4号和8号相邻节点都被访问，所以没有处理

小结

在这里插入图片描述

Dijkastra算法

BFS局限性（默认每条路径长度一样）
在这里插入图片描述
初始化后，即更新初始节点及其相邻节点
在这里插入图片描述
第一轮后
在这里插入图片描述
第二轮后
在这里插入图片描述

第三轮后
在这里插入图片描述
第四轮后

在这里插入图片描述
查找两个顶点的最短路径
在这里插入图片描述

算法时间复杂度

在这里插入图片描述

在这里插入图片描述

不适用情况

在这里插入图片描述

每一对顶点的最短路径问题

在这里插入图片描述

Floyd算法

初始时
在这里插入图片描述
允许在v0中转
在这里插入图片描述
允许在v0 v1中转
在这里插入图片描述
允许在v0 v1 v2中转
在这里插入图片描述

找两个点的最短路径

在这里插入图片描述

核心代码

空间复杂度是有n*n个矩阵那么多
在这里插入图片描述

实例

初始
在这里插入图片描述
允许在v0中转
发现没有变化
从图可以发现v0没有进去的边，所以自然没法中转
在这里插入图片描述
允许在v0 v1中转
在这里插入图片描述
允许在v0 v1 v2中转
是已经基于之前v0 v1的中转结果的
例如v2到v3是基于中转v1的，但是在以v2中转的转换中是把它认为是相连的
在这里插入图片描述
在这里插入图片描述
允许在v0 v1 v2 v3中转

在这里插入图片描述
允许在v0 v1 v2 v3 v4中转
在这里插入图片描述

找两个顶点最短路径

在这里插入图片描述

Floyd用于负权图

在这里插入图片描述

不能解决的问题

回路越多，路径越短

在这里插入图片描述

小结

BFS 采用邻接矩阵是V的平方 邻接矩阵是V+E
在这里插入图片描述

相关文章：

数据结构和算法-最小生成树（prim和krusakal）和最短路径问题（BFS和dijkastra和floyd）

文章目录 最小生成树总览生成树广度优先生成树深度优先生成树最小生成树Prim算法Kruskal算法Prim vs KrusakalPrim的实现Kruskal的实现 小结 最短路径问题单源最短路径问题BFS求无权图的单源最短路径小结Dijkastra算法算法时间复杂度不适用情况 每一对顶点的最短路径问题Floyd算…...

编程日记 2023/12/17 15:34:14

响应者链概述

响应者链 iOS事件的3大类型 Touch Events(触摸事件)Motion Events(运动事件，比如重力感应和摇一摇等)Remote Events(远程事件，比如用耳机上得按键来控制手机) 触摸事件 处理触摸事件的两个步骤 寻找事件的最佳响应者事件的响应在响应链中的传递 寻…...

编程日记 2023/12/17 15:33:12

ShenYu网关Http服务探活解析

文章目录 网关端服务探活admin端服务探活 Shenyu HTTP服务探活是一种用于检测HTTP服务是否正常运行的机制。它通过建立Socket连接来判断服务是否可用。当服务不可用时，将服务从可用列表中移除。 网关端服务探活 以divide插件为例，看下divide插件是如何获…...

编程日记 2023/12/17 15:31:11

基于dockerfile搭建LNMP

组件自定义IP所需组件nginx172.111.0.10nginxwordpressmysql172.111.0.20mysql-5.7.20php172.111.0.30php LNMP介绍 L：Linux平台，操作系统，另外桑组件的运行平台 N：nginx 提供前端页面 M：MySQL，开源关系的…...

编程日记 2023/12/17 15:30:10

基于VGG-16+Android+Python的智能车辆驾驶行为分析—深度学习算法应用(含全部工程源码)+数据集+模型（三）

目录 前言总体设计系统整体结构图系统流程图 运行环境模块实现1. 数据预处理2. 模型构建3. 模型训练及保存1）模型训练2）模型保存 4. 模型生成1）模型导入及调用2）相关代码（1）布局文件（2&#xff…...

编程日记 2023/12/17 15:29:09

springMVC-@RequestMapping

基本介绍 RequestMapping注解可以指定控制器/处理器的某个方法的请求的url, 示例 （结合springMVC基本原理理解） Controller public class UserHandler {RequestMapping(value "/login")public String login() {System.out.println("登…...

编程日记 2023/12/17 15:28:08

智能优化算法应用：基于树种算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于树种算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用：基于树种算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.树种算法4.实验参数设定5.算法结果6.参考文献7.MA…...

编程日记 2023/12/17 15:27:07

web前端项目-影视网站开发

影视网站 本项目主要使用到了 HTML&#xff1b;CSS&#xff1b;JavaScript脚本技术&#xff1b;AJAX无刷新技术&#xff1b;jQuery等技术实现了动态影视网页 运行效果&#xff1a; 一&#xff1a;index.html <!DOCTYPE> <html lang"en"> <head>…...

编程日记 2023/12/17 15:26:06

QT:Unable to create a debugging engine.

debug跑不了&#xff1a; 报错&#xff1a;Unable to create a debugging engine. 参考&#xff1a; https://blog.csdn.net/u010906468/article/details/104716198 先检查是否安装了DEBUG插件 工具-》》选项 查看插件&#xff0c;如果没有的话&#xff0c;需要重新安装qt时…...

编程日记 2023/12/17 15:24:04

如何理解Rust语言中的“impl”关键字

在Rust编程语言中&#xff0c;impl是一个关键字&#xff0c;用于为类型实现方法和特性&#xff08;traits&#xff09;。impl关键字后面可以跟一个类型或者特性名称&#xff0c;然后在大括号中定义该类型或特性的具体实现。 当我们使用impl关键字为一个类型实现方法时&#xf…...

编程日记 2023/12/17 15:23:03

C++实现简单的猜数字小游戏

猜数字 小游戏介绍&#xff1a;猜数字游戏是令游戏机随机产生一个100以内的正整数&#xff0c;用户输入一个数对其进行猜测&#xff0c;需要你编写程序自动对其与随机产生的被猜数进行比较&#xff0c;并提示大了&#xff0c;还是小了&#xff0c;相等表示猜到了。如果猜到&…...

编程日记 2023/12/17 15:22:02

人工智能导论复习资料

题型 1、简答题&#xff08;5题&#xff09; 2、设计题 3、综合题 4、论述题&#xff08;10分&#xff09; 考点 第一章 1、人工智能的定义、发展&#xff1b; 2、人工智能的学派、认知观及其间的关系&#xff1b; 3、人工智能要素及系统分类&#xff1b; 4、人工智能的研究、…...

编程日记 2023/12/17 15:21:01

Sentinel使用详解

组件简介 Sentinel是阿里开源的一套用于服务容错的综合性解决方案。它以流量为切入点&#xff0c;从流量控制、熔断降级、系统负载保护等多个维度来保护服务的稳定性。Sentinel承接了阿里巴巴近10年的双十一大促流量的核心场景&#xff0c;例如秒杀、消息削峰填谷、集群流量控…...

编程日记 2023/12/17 15:17:59

Vue3源码梳理：响应式系统的前世今生

响应性数据的前世 js的程序性: 一套固定的&#xff0c;不会发生变化的执行流程 1 &#xff09;没有响应的数据 // 定义商品对象 const product {price: 10,quantity: 2 }// 总价格 let total product.price * product.quantity console.log(总价格&#xff1a;${total}) //…...

编程日记 2023/12/17 15:16:58

Jetpack Compose开发一个Android WiFi导航应用

在以前的一篇文章构建一个WIFI室内定位系统_wifi定位系统-CSDN博客中&#xff0c;我介绍了如何用Android来测量WiFi信号&#xff0c;上传到服务器进行分析后&#xff0c;生成室内不同地方的WiFi指纹&#xff0c;从而帮助进行室内导航。当时我是用的HTML5的技术来快速开发一个An…...

编程日记 2023/12/17 15:15:58

【Mode Management】ComM详细介绍

目录 1. Introduction and functional overview 2.Dependencies to other modules 3.Functional specification 3.1 Partial Network Cluster Management 3.2 ComM channel state machine 3.2.1 Behaviour in state COMM_NO_COMMUNICATION 3.2.1.1 COMM_NO_COM_NO_PENDI…...

编程日记 2023/12/17 15:11:54

【C++多线程编程】（二）之详解锁（lock）和解锁（unlock）

在C多线程编程中&#xff0c;锁&#xff08;lock&#xff09;和解锁&#xff08;unlock&#xff09;通常用于管理共享资源的访问&#xff0c;以防止多个线程同时对资源进行修改&#xff0c;从而避免竞态条件&#xff08;Race Condition&#xff09;和数据不一致性问题。C标准库…...

编程日记 2023/12/17 15:10:53

【Mypy】超级实用的python高级库！

今天&#xff0c;我很兴奋地向大家介绍一个神奇的Python库&#xff1a;Mypy。这个库是Python世界中的一颗璀璨明星&#xff0c;提供了静态类型检查的强大功能&#xff0c;极大地增强了Python这门动态类型语言的健壮性和可维护性。我们将深入探索Mypy的多个方面&#xff0c;并通…...

编程日记 2023/12/17 15:09:51

【Python基础】循环语句

文章目录 [toc]什么是循环Python中的循环方式while循环格式示例 什么是循环 程序中需要重复执行的代码&#xff0c;可以通过循环实现比如和女朋友道歉&#xff0c;或一万遍“宝宝&#xff0c;我错了”&#xff0c;在没有学习循环之前&#xff0c;我们只能通过如下方式实现 pr…...

编程日记 2023/12/17 15:01:45

【面试】广告优化

a1&#xff1a;点击率公式是什么&#xff1f;点击率低的原因是什么&#xff1f; 点击率点击/曝光&#xff0c;点击率低的原因主要有两点&#xff1a;一是创意不吸引人&#xff1b;二是目标受众不准确/定向过宽不精确&#xff0c;广告曝光给了对产品不感兴趣用户 a2&#xff1a;…...

编程日记 2023/12/17 15:00:44

RabbitMQ插件详解：rabbitmq_message_timestamp【Rabbitmq 五】

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 RabbitMQ时空之旅&#xff1a;rabbitmq_message_timestamp的奇妙世界 前言什么是rabbitmq_message_timestamprabbitmq_message_timestamp 的定义与作用&#xff1a;如何在 RabbitMQ 中启用消息时间戳&…...

编程日记 2023/12/17 14:59:42

AD9361 Evaluation Software配置脚本转换工具

最近在玩一个开源的AD9361项目&#xff0c;AD9361采用纯逻辑配置&#xff0c;不需要ARM或者MicroBlaze。其中&#xff0c;先是用AD9361 Evaluation Software生成配置脚本&#xff0c;再转换成ad9361_lut.v。 在网上查了一圈&#xff0c;有个转换工具叫bit_converter&#xff0…...

编程日记 2023/12/17 14:57:41

Centos7 配置Git

随笔记录 目录 1&#xff0c; 新建用户 2. 给用户设置密码相关操作 3. 为新用户添加sudo 权限 4. 配置Git 4.1 配置Git 4.2 查看id_ras.pub 5, 登录Git 配置SSH 秘钥 6. Centos7 登录Git 7. clone 指定branch到本地 8. 将新代码复制到指定路径 9. 上传指定代码 …...

编程日记 2023/12/17 14:56:40

python工具方法 44 数据仿真生成（粘贴目标切片到背景图像上，数据标签校验）

在深度学习训练中数据是一个很重要的因素，在数据不够时需要我们基于现有的数据进行增强生成新的数据。此外，在某特殊情况，如对某些目标切片数据（例如：石块分割切片）预测效果较差，需要增强其在训练数据中的频率。故此，我们可以将先有数据标注中的目标裁剪出来，作为样本…...

编程日记 2023/12/17 14:53:37

Llama 架构分析

从代码角度进行Llama 架构分析 Llama 架构分析前言Llama 架构分析分词网络主干DecoderLayerAttentionMLP 下游任务因果推理文本分类 Llama 架构分析 前言 Meta 开发并公开发布了 Llama系列大型语言模型 (LLM)&#xff0c;这是一组经过预训练和微调的生成文本模型&#xff0c;参…...

编程日记 2023/12/17 14:52:37

vue3前端 md5工具类

工具类 /*** Namespace for hashing and other cryptographic functions* Copyright (c) Andrew Valums* Licensed under the MIT license, http://valums.com/mit-license/*/var V V || {}; V.Security V.Security || {};(function () {// for faster accessvar S V.Secur…...

编程日记 2023/12/17 14:51:36

Unity触摸 射线穿透UI解决

unity API 之EventSystem.current.IsPointerOverGameObject() 命名空间 &#xff1a;UnityEngine.EventSystems 官方描述&#xff1a; public bool IsPointerOverGameObject(); public bool IsPointerOverGameObject(int pointerId); //触摸屏时需要的参数&#xff…...

编程日记 2023/12/17 14:50:35

基于QTreeWidget实现带Checkbox的多级组织结构选择树

基于QTreeWidget实现带Checkbox的多级组织结构选择树 采用基于QWidgetMingw实现的原生的组织结构树 通过QTreeWidget控件实现的带Checkbox多级组织结构树。 Qt相关系列文章&#xff1a; 一、Qt实现的聊天画面消息气泡 二、基于QTreeWidget实现多级组织结构 三、基于QTreeWidget…...

编程日记 2023/12/17 14:46:31

探索 Vim：一个强大的文本编辑器

引言&#xff1a; Vim&#xff08;Vi IMproved&#xff09;是一款备受推崇的文本编辑器&#xff0c;拥有强大的功能和高度可定制性&#xff0c;提供丰富的编辑和编程体验。本文将探讨 Vim 的基本概念、使用技巧以及为用户带来的独特优势。 简介和发展 1. Vim 的简介和历史 V…...

编程日记 2023/12/17 14:45:30

K8S（十）—容器探针

这里写目录标题 容器探针&#xff08;probe&#xff09;检查机制探测结果探测类型何时该使用存活态探针?何时该使用就绪态探针?何时该使用启动探针&#xff1f; 使用exechttptcpgrpc使用命名端口 使用启动探针保护慢启动容器定义就绪探针配置探针HTTP 探测TCP 探测探针层面的…...

编程日记 2023/12/17 14:44:29

什么程序做网站安全/合肥网络关键词排名

dhcp 端口 UDP67和UDP68为正常的DHCP服务端口 rpm -qa | grep dhcp 查询是否安装了dhcp 服务 安装dhcp 服务 yum install dhcp -y 打开/etc/dhcp/dhcpd.conf subnet 192.168.105.0 netmask 255.255.255.0 { 下发网段 range 192.168.105.20 192.168.105.200 ; …...

编程日记 2025/1/13 12:03:24

word里面网站超链接怎么做/百度推广哪家做的最好

不少人买平板电脑的目的就是用来玩吃鸡的&#xff0c;然而有的人发现买回来后玩吃鸡会有一点点卡&#xff0c;这是什么原因呢?主要与配置和设置有关系&#xff0c;因为吃鸡对配置要求还是比较高的&#xff0c;如果选择一些配置较差的低端品牌自然会卡顿&#xff0c;那么它对于…...

编程日记 2025/1/13 11:48:02

姜堰哪里有网站建设的/企业邮箱怎么注册

本文将会按照以下四个部分来讲述如何从业务数据中分析数据,建立模型,希望对大家有所帮助!数据从哪来如何分析数据机器学习算法简介预测效果评估Part1: 数据从哪来你眼中的大数据分析和实际的大数据分析实际上是非常不一样的你眼中的大数据分析和实际的大数据分析一般来说,实际业…...

编程日记 2025/1/13 9:53:58

订阅号做微网站需要认证吗/营销策划师

1、测试人员提交新的Bug入库&#xff0c;错误状态为New。 2、高级测试人员验证错误&#xff0c;如果确认是错误&#xff0c;分配给相应的开发人员&#xff0c;设置状态为Open。如果不是错误&#xff0c;则拒绝&#xff0c;设置为Declined(拒绝)状态。 3、开发人员查询状态为O…...

编程日记 2025/1/13 3:21:15

自己做网站制作需要多少钱/网络优化seo是什么工作

前言 今天给大家介绍利用Python爬取并简单分析猫眼电影影评。让我们愉快地开始吧~ 开发工具 Python版本&#xff1a;3.6.4 相关模块&#xff1a; requests模块&#xff1b; pyecharts模块&#xff1b; jieba模块&#xff1b; scipy模块&#xff1b; wordcloud模块&…...

编程日记 2025/1/12 22:42:00

自动生成图片的网站/谷歌是如何运营的

遇到这个 Java Serializable 序列化这个接口&#xff0c;我们可能会有如下的问题a&#xff0c;什么叫序列化和反序列化b&#xff0c;作用。为啥要实现这个 Serializable 接口&#xff0c;也就是为啥要序列化c&#xff0c;serialVersionUID 这个的值到底是在怎么设置的&#xff…...

编程日记 2025/1/12 22:41:00