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

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

news 2026/3/17 20:17:08

文章目录

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

Qwen3-Reranker-0.6B企业级应用：构建高效语义搜索系统完整方案

Qwen3-Reranker-0.6B企业级应用&#xff1a;构建高效语义搜索系统完整方案 1. 企业级语义搜索系统概述 1.1 语义搜索的核心价值 在信息爆炸时代&#xff0c;企业面临海量数据检索的挑战。传统关键词匹配技术&#xff08;如BM25&#xff09;虽然速度快&#xff0c;但无法理解…...

编程新知 2026/3/17 19:58:30

不用china.js！3种最新方法实现ECharts中国地图可视化（2024版）

2024年ECharts中国地图可视化三大替代方案实战指南 当官方不再提供china.js文件时&#xff0c;开发者如何快速实现中国地图可视化&#xff1f;本文将深入解析三种经过实战验证的替代方案&#xff0c;从数据获取到最终渲染&#xff0c;手把手带你绕过资源缺失的坑。 1. 为什么我…...

编程新知 2026/3/17 19:44:21

I2C速率模式全解析

I2C通信速率详解 一、I2C速率模式概述 I2C总线支持多种速率模式&#xff0c;每种模式都有其特定的应用场景和性能特点。以下是主要的速率模式对比&#xff1a; 速率模式传输速率应用场景特点标准模式100 kbps通用低速设备最早定义的速率&#xff0c;兼容性最好快速模式400 k…...

编程新知 2026/3/17 17:18:35

148.《mobx-react-lite + TypeScript 入门实战教程（完整版）》

一、教程前言 MobX 是一款轻量级响应式状态管理库&#xff0c;相比 Redux 更简洁、学习成本更低&#xff1b;mobx-react-lite 是 MobX 专为 React 函数组件设计的轻量级绑定库&#xff0c;结合 TypeScript 可实现类型安全的状态管理。 本教程通过「计数器 汽车列表」实战案例&…...

编程新知 2026/3/17 17:08:29

[特殊字符]现代机器人学课程：理论与实践的完美融合[特殊字符]

&#x1f916;现代机器人学课程&#xff1a;理论与实践的完美融合&#x1f680; 【免费下载链接】modern-robotics-course This repository is all the lessons for Modern Robotics Course. 项目地址: https://gitcode.com/gh_mirrors/mo/modern-robotics-course 在科…...

编程新知 2026/3/17 16:32:05

PowerPlatformConnectors安全最佳实践：保护你的集成工作流免受威胁

PowerPlatformConnectors安全最佳实践&#xff1a;保护你的集成工作流免受威胁 【免费下载链接】PowerPlatformConnectors This is a repository for Microsoft Power Automate, Power Apps, and Azure Logic Apps connectors 项目地址: https://gitcode.com/gh_mirrors/po/P…...

编程新知 2026/3/17 16:01:48

终极指南：如何修复Happy-LLM项目中的公式显示问题

终极指南&#xff1a;如何修复Happy-LLM项目中的公式显示问题 【免费下载链接】happy-llm &#x1f4da; 从零开始的大语言模型原理与实践教程 项目地址: https://gitcode.com/GitHub_Trending/ha/happy-llm Happy-LLM是一个从零开始的大语言模型原理与实践教程项目&…...

编程新知 2026/3/17 15:43:35

RexUniNLU中文NLP系统保姆级教程：Gradio输入输出格式与调试技巧

RexUniNLU中文NLP系统保姆级教程&#xff1a;Gradio输入输出格式与调试技巧 1. 开篇&#xff1a;为什么需要这个教程 如果你正在使用或者打算使用RexUniNLU中文NLP系统&#xff0c;可能会遇到这样的困惑&#xff1a;明明模型能力很强&#xff0c;为什么我的输入总是得不到想要…...

编程新知 2026/3/17 14:06:40

[特殊字符] mPLUG-Owl3-2B多模态工具实战：OCR增强型图文问答——识别图中文字并推理

mPLUG-Owl3-2B多模态工具实战&#xff1a;OCR增强型图文问答——识别图中文字并推理 1. 项目简介 mPLUG-Owl3-2B多模态交互工具是一个基于先进视觉语言模型的本地化解决方案&#xff0c;专门为图文理解和视觉问答场景设计。这个工具最大的特点是完全在本地运行&#xff0c;不…...

编程新知 2026/3/17 14:02:38

Youtu-Parsing入门必看：支持手写体、印章、LaTeX公式的全要素OCR解析

Youtu-Parsing入门必看&#xff1a;支持手写体、印章、LaTeX公式的全要素OCR解析 1. 引言&#xff1a;告别传统OCR的烦恼 如果你曾经尝试过从扫描的PDF、手写的笔记或者满是公式的学术论文里提取文字&#xff0c;你肯定知道传统OCR有多让人头疼。要么是表格识别得一塌糊涂&am…...

编程新知 2026/3/17 14:02:38