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

算法笔记 图论和优先级队列的笔记

图论

DFS       stack     O(h)     不具有最短性

BFS       queue    O(2^h)   最短路

迪杰斯特拉算法

  • 初始化

    • 将起始节点 A 的距离设为 0
    • 将其他所有节点的距离设为无穷大。
    • 创建一个优先队列,并将起始节点 A 加入优先队列。
  • 处理队列

    • 从优先队列中取出距离最小的节点 u
    • 对于 u 的每个邻接节点 v,计算从 uv 的路径长度,如果该长度小于当前记录的 v 的最短路径,则更新 v 的最短路径并将 v 加入优先队列。

优先级队列

lambda函数中 >是最小堆, <是最大堆

greater是最小堆,less是最大堆

  • 最大堆:默认情况下,priority_queue 是最大堆,因为它使用 < 比较函数。这意味着较大的元素具有较高的优先级。
  • 最小堆:通过使用 greater<> 比较函数,priority_queue 变成了最小堆。greater<> 确保较小的元素具有较高的优先级。
  • 自定义比较函数:使用 lambda 表达式或其他自定义比较函数,可以灵活地定义优先级规则。

auto tupleCmp =[](const auto& e1,const auto& e2){ auto&& [x1,y1,d1]=e1; auto&& [x2,y2,d2]=e2; return d1>d2; };这个是最大堆还是最小堆

堆顶是优先级最高(值最大)的元素。

  1. 捕获参数
    • const auto& e1const auto& e2:这两个参数是要比较的元素,类型自动推断。
  2. 结构化绑定
    • auto&& [x1, y1, d1] = e1;auto&& [x2, y2, d2] = e2;:使用结构化绑定来解包元素。这些元素应该是类似于 tuplepair 的结构,其中 d1d2 是我们要比较的第三个元素(假设它们是优先级或距离)。
  3. 返回比较结果
    • return d1 > d2;:比较 d1d2。如果 d1 大于 d2,则返回 true

priority_queue 中,如果比较函数返回 true,表示 e1 应该排在 e2 之前。默认情况下,priority_queue 是最大堆,即较大的元素优先。然而,在这个自定义比较函数中:

  • d1 > d2 时,e1 被认为优先级更高,排在 e2 前面。
  • 因此,较小的 d 会被认为优先级较低。

结论:

这个比较函数实际上创建了一个 最小堆,因为 priority_queue 会根据 d 的值按升序排列,即优先处理 d 值较小的元素。

相关文章:

算法笔记 图论和优先级队列的笔记

图论 DFS stack O(h) 不具有最短性 BFS queue O(2^h) 最短路 迪杰斯特拉算法 初始化&#xff1a; 将起始节点 A 的距离设为 0。将其他所有节点的距离设为无穷大。创建一个优先队列&#xff0c;并将起始节点 A 加入优先队列。 处理队列&#xff1a; …...

6.每日LeetCode-数组类,找到所有数组中消失的数字

题目 448找到所有数组中消失的数字.go 给你一个含 n 个整数的数组 nums &#xff0c;其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字&#xff0c;并以数组的形式返回结果。 示例 1&#xff1a; 输入&#xff1a;nums [4,3,2,7,8,2,…...

【Three.js】知识梳理十:Three.js纹理贴图

1. 纹理贴图 在Three.js中&#xff0c;纹理贴图是一种将二维图像贴到三维物体表面的技术&#xff0c;以增强物体的视觉表现。纹理贴图可以使物体表面更加真实、细腻&#xff0c;为场景增色不少。 在Three.js中&#xff0c;纹理贴图的加载主要通过THREE.TextureLoader类实现。…...

mysql order by后跟case when

在SQL中&#xff0c;ORDER BY子句用于对查询结果进行排序。当在ORDER BY后面使用CASE语句时&#xff0c;它的原理是&#xff1a;根据CASE语句中定义的条件和结果&#xff0c;为查询结果集中的每一行生成一个临时的排序值。然后&#xff0c;根据这些排序值对结果集进行排序。 具…...

数字孪生赋能的智慧园区物联网云平台建设方案(97页PPT)

方案介绍&#xff1a; 本方案通过数字孪生技术赋能智慧园区物联网云平台&#xff0c;实现了园区的智能化管理、优化资源配置、提高运营效率等目标。同时提升园区的安全性、环保性和可持续性。最后&#xff0c;该方案还充分考虑了系统的可扩展性、安全性和可靠性&#xff0c;为…...

TikTok小店运营策略

TikTok&#xff0c;作为一款全球知名的短视频社交平台&#xff0c;其用户基数庞大且日活跃用户持续增长&#xff0c;为商家提供了巨大的商机。欧洲作为TikTok的重要市场之一&#xff0c;其小店功能为商家提供了一个展示和销售产品的新渠道。本文将探讨如何有效地运营TikTok小店…...

Docker面试整理-如何查看和管理Docker容器的日志?

管理和查看 Docker 容器的日志是 Docker 容器管理的重要部分,有助于监控应用的行为和诊断问题。Docker 提供了几种方法来查看和管理容器日志。 查看容器日志 要查看 Docker 容器的日志,你可以使用 docker logs 命令。这个命令会打印容器的 STDOUT 和 STDERR 输出,这是大多数…...

Java从放弃到继续放弃

并发编程 为什么需要多线程&#xff1f; 由于硬件的发展&#xff0c;CPU的核数增多&#xff0c;如果仍然使用单线程对CPU资源会造成浪费。同时&#xff0c;单线程也会出现阻塞的问题。所以&#xff0c;选择向多线程转变。 多线程的使用使得程序能够并行计算&#xff0c;提高计…...

上传文件生成聊天机器人,实现客服、办公自动化智能体 | Chatopera

从谈论聊天机器人&#xff0c;到谈论智能体&#xff0c;是目前人工智能最炙手可热的话题&#xff0c;这两年最大的变化是大语言模型的应用。聊天机器人曾经很难定制&#xff0c;往往局限于个别行业&#xff0c;同时也只有行业内的领导者、头部企业能定制。比如银行、金融证券、…...

SD3303A 大功率高亮度LED驱动芯片IC

一般描述 SD3303A是一款大功率高亮度LED驱动芯片,可以提供1A的电流驱动3W的LED。具有高效率&#xff0c;低功耗等特点&#xff0c;适用于电池供电的LED照明设备。 SD3303A具有开路保护和过温保护。 SD3303A需要使用两颗10uF(或者更大)的瓷片电容&#xff0c;来保…...

站易WordPress

站易WordPress是一家专业提供网站建设和运营服务的公司。他们提供的服务包括企业官方网站建设、网站运营维护、网站托管、网站优化、跨境独立站建站、外贸网站建设以及海外多语言网站建设等。 此外&#xff0c;站易还提供使用现成的WordPress模板&#xff0c;这样可以快速且低…...

windows下JDK1.8安装

windows下JDK1.8安装 本文假设你知道了解基本的windows系统操作。 在Windows系统下安装JDK 1.8&#xff08;Java Development Kit&#xff09;的步骤如下&#xff1a; 步骤1&#xff1a;下载JDK 1.8 打开浏览器并访问Oracle JDK下载页面。https://www.oracle.com/java/technol…...

怎么修改Visual Studio Code中现在github账号

git config --global user.name “你的用户名” git config --global user.email “你的邮箱” git config --global --list git push -u origin your_branch_name git remote add origin...

戴尔R720服务器(3)组RAID

今天收到7块硬盘&#xff0c;现在共有8块硬盘了&#xff0c;找了个视频学习了怎么使用阵列卡组RAID并记录。 ​​ ‍ 视频参考&#xff1a;【戴尔服务器添加RAID5热备盘hotspare】 ‍ 阵列卡组RAID5 开始 连接iDRAC控制台服务器开机按F2进入BIOS选择Device Settings​ ​​…...

eNSP学习——配置高级的访问控制列表

目录 主要命令 原理概述 实验目的 实验内容 实验拓扑 实验编址 实验步骤 1、基本配置 2、搭建OSPF网络 3、配置Telnet 4、配置高级ACL控制访问 需要eNSP各种配置命令的点击链接自取&#xff1a;华为&#xff45;NSP各种设备配置命令大全PDF版_ensp配置命令大全资源-…...

oracle的bitmap索引是什么

Oracle的Bitmap索引是一种特殊的索引类型&#xff0c;主要用于处理那些数值稀疏&#xff08;low-cardinality&#xff0c;低基数&#xff09;的字段&#xff0c;特别是那些值不经常改变的字段。以下是关于Bitmap索引的详细解释&#xff1a; 定义&#xff1a; Bitmap索引是一种…...

「前端+鸿蒙」鸿蒙应用开发-TS接口-特殊用途

在 TypeScript 中&#xff0c;接口除了定义对象的结构之外&#xff0c;还有一些特殊用途&#xff0c;这些用途使得接口成为一种灵活的工具&#xff0c;用于提高代码的可维护性和可扩展性。 TS快速入门-接口-特殊用途 1. 定义函数类型 接口可以用来定义函数的类型&#xff0c;…...

Centos7系统禁用Nouveau内核驱动程序【笔记】

在CentOS系统中&#xff0c;Nouveau是开源的NVIDIA显卡驱动程序&#xff0c;但它与NVIDIA的官方驱动程序NVIDIA Proprietary Driver存在兼容性问题。 如果你想要禁用Nouveau并使用NVIDIA官方驱动&#xff0c;可以按照以下步骤操作&#xff1a; 1、创建一个黑名单文件以禁用No…...

Vue 面试通杀秘籍

理论篇&#xff1a; 1. 说说对 Vue 渐进式框架的理解&#xff08;腾讯医典&#xff09; a) 渐进式的含义&#xff1a; 主张最少, 没有多做职责之外的事 b) Vue 有些方面是不如 React&#xff0c;不如 Angular.但它是渐进的&#xff0c;没有强主张&#xff0c; 你可以在原有…...

聚焦新版综合编程能力面试考查汇总

目录 一、业务性编程和广度能力考查 &#xff08;一&#xff09;基本定义 &#xff08;二&#xff09;必要性分析 二、高频考查样题&#xff08;编程扩展问法&#xff09; 考题1: 用java 代码实现一个死锁用例&#xff0c;说说怎么解决死锁问题&#xff1f;&#xff08;高…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...