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

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

news 2025/7/3 7:06:13

文章目录

  • 最小生成树
    • 总览
    • 生成树
    • 广度优先生成树
    • 深度优先生成树
    • 最小生成树
    • 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

Linux 文件类型，目录与路径，文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

编程新知 2025/6/30 8:13:12

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

编程新知 2025/6/21 9:09:27

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

编程新知 2025/6/29 18:40:59

盘古信息PCB行业解决方案：以全域场景重构，激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

编程新知 2025/6/27 7:21:30

三维GIS开发cesium智慧地铁教程（5）Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

编程新知 2025/6/21 4:17:55

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

编程新知 2025/6/26 5:47:42

【OSG学习笔记】Day 16: 骨骼动画与蒙皮（osgAnimation）

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

编程新知 2025/6/24 2:02:57

.Net Framework 4/C# 关键字（非常用，持续更新...）

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容，如果兼容将返回 true，如果不兼容则返回 false，在进行类型转换前，可以先使用 is 关键字判断对象是否与指定类型兼容，如果兼容才进行转换，这样的转换是安全的。 例如有：首先创建一个字符串对象，然后将字符串对象隐…...

编程新知 2025/6/25 1:12:20

08. C#入门系列【类的基本概念】：开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

编程新知 2025/6/15 18:05:20

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

编程新知 2025/6/26 22:06:15