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

BFS入门

news 来源：原创 2025/7/5 12:21:40

定义

BFS 通常是指广度优先搜索（Breadth - First Search），它是一种图形数据结构的遍历算法。从给定的起始顶点开始，首先访问起始顶点的所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点，以此类推，一层一层地向外扩展搜索，就好像是水波纹一样，从中心向四周扩散。在这个过程中，先被访问到的顶点的邻接顶点会先被探索。

二叉树层次遍历

在这里插入图片描述

ccbl(int root)queue<int> Q; //创建一个队列Q.push(root); //将根节点入队列while(!empty(Q) //队列不为空){cur = Q.gethead;  //获得队首元素Q.pop();  //将队首元素出队printf("%d",cur);  //输出当前节点的值if(!Q.leftchild)Q.push(Q.leftchild);  //如果该节点的左儿子不为空，将左儿子加入到队列中if(!Q.rightchild)Q.push(Q.rightchild);  //如果该节点的右儿子不为空，将右儿子加入到队列中}

电梯问题

有一个奇怪的电梯，他可以停在任何不层，并且在每个楼层有一个Ki （0<= Ki <=N）。电梯只有两个按钮：上、下。当你在第i层，如果你按下“UP”按钮，你将上升Ki层，也就是说，你将会到达第i+Ki层，如果你按下 “DOWN” 按钮，你会下降Ki层，即您将前往第i-Ki层。当然，电梯不能高于N，也不能低于1。
例如，有6层的建筑物，并且k1=3，k2=3，k3=2，k4=2，k5=2，k6=3。从1楼开始，你河以按下“UP”按钮，你会到4楼，但如果你按下“DOWN”按钮，电梯不做处理，因为它不能下到-2楼。
问：当你在A楼而想去B楼时，至少须按下“UP”或“DOWN”按钮多少次？其中，1<=N,A, B ＜= 200
样例输入：
6 1 3
3 3 2 2 2 З
样例输出：
3

在这里插入图片描述

#include<bits/stdc++. h> using namespace std;
int N,Start, End; int a[202]; int vis[202];
struct pos
{
int level; 
int steps;
}；
void bfs();int main
{while (scanf ("%d", &N) ==1){if (N = 0) break;scanf ("%d%d", &Start, &End) ;for (int i = 1; i < N; i++){scanf ("%d", &a[i]);vis[i] = 0;}bfs ();}return 0;
}void bfs ()
{pos cur, nex;cur. level = Start;cur. steps = 0;queue<pos>qu;qu. push (cur) ;vis[Start] = 1;while (!qu. empty ()){ cur = qu. front ();qu. pop () ;if (cur. level = End){ printf ("%d\n", cur. steps);return;}nex. level=cur. level + a[cur. level];nex. steps = cur. steps + 1;if(nex. level <= N){if (vis[nex. level] == 0){vis [nex. level] = 1;qu. push (nex);}}nex.level = cur.level - a[ cur.level ];nex. steps = cur. steps + 1;if(nex. level >= 1){ if (vis[nex. level] == 0){vis [nex. level] = 1;qu. push (nex);}}}printf ("-1\n") ;return;
}

倒可乐

题目描述：
每当刘一丁买了可乐，刘二丁就要求和他一起分享，而且一定要喝的和刘一丁一样多。但刘一丁的手中只有两个杯子，它们的容量分别是N和M毫升，可乐的体积为S（S<101）毫升（正好装满一瓶），它们三个之间可以相互倒可乐（都是没有刻度的，且 S=N+M,101>S>0，N>0,M>0）。
如果能平分，请输出倒可乐的最少次数，如果不能，请输出"NO"。
Input
7 4 3
413
000
Output
NO
3

在这里插入图片描述

状态转移规则（倒水规则）：

如果i水杯内水的容量大于j水杯内倒满所需的容量X，则i水杯倒水后的容量为：i-x，j水杯倒水后容量为：j+x
如果i水杯内水的容量小于j水杯内倒满所需的容量x，则i水杯倒水后的容量为：0，j水杯倒水后容量为：j+x
每操作一次，最少倒水次数+1

BFS基本思想

从初始状态S开始，利用规则，生成所有可能的状态，构成树的下一层节点。
检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别依次利用规则，生成再下一层的所有状态节点。
对新一层的所有状态节点继续检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开，直到出现目标状态为止。

算法

Node bfs(node source, node target)
{memset(visit, 0 , sizeof(visit)) ;queue < node> Q;Q.push(source) ;visit[source] = 1 ;while(!Q.empty){Node a = Q.front();Q.pop() ;if(a==target) { return a; }for（对于a所有的后继节点 b）if(visit[b]){ continue ; }Q.push(b) ;visit[b]= 1；//剪枝，保证节点只进队列一次}return NULL;
}

四方访问

定义一个二维数组（全局变量）；

int dir[4][2] = { {0,-1},{0,1},{1,0},{-1,0} };
//设当前坐标（X.Y）,下步坐标（XX,YY）
for（int i=0; i<4; i++)
{XX = XX + dir[i][0];YY = YY + dir[i][1];......
}

BFS入门

目录定义二叉树层次遍历电梯问题倒可乐BFS基本思想算法四方访问定义 BFS 通常是指广度优先搜索（Breadth - First Search），它是一种图形数据结构的遍历算法。从给定的起始顶点开始，首先访问起始顶点的所有邻接顶点，然…...

编程日记 2025/7/5 12:21:40

ElementUI：el-tabs 切换之前判断是否满足条件

<div class"table-card"><div class"card-steps-class"><el-tabsv-model"activeTabsIndex":before-leave"beforeHandleTabsClick"><el-tab-pane name"1" label"基础设置"><span slot&…...

编程日记 2025/7/5 11:46:24

mid360使用cartorapher进行3d建图导航

1. 添加urdf配置文件： 添加IMU配置关节点和laser关节点  <joint name"livox_frame_joint" type"fixed"> <parent link"base_link" /> <child link"livox_frame" /> <o…...

编程日记 2025/7/5 11:04:23

【CSS in Depth 2 精译_073】第 12 章 CSS 排版与间距概述 + 12.1 间距设置（中）：对 CSS 行高的深入思考

当前内容所在位置（可进入专栏查看其他译好的章节内容） 第四部分视觉增强技术 ✔️【第 12 章 CSS 排版与间距】 ✔️ 12.1 间距设置 12.1.1 使用 em 还是 px12.1.2 对行高的深入思考 ✔️12.1.3 行内元素的间距设置文章目录 12.1.2 对行高的深入思考…...

编程日记 2025/7/5 11:01:52

JAVA设计模式-观察者模式

概述： 观察者模式通常由两个对象组成：观察者和被观察者。当被观察者状态发生改变时，它会通知所有的观察者对象，使他们能够及时做出响应，所以也被称作“发布-订阅模式”。特点： 优点： 解耦且可…...

编程日记 2025/7/4 20:23:32

Java调用SSE流式接口，并流式返回给前端实现打字输出效果

目录 1.SSE概述 1.1 什么是是SSE2.2 与长链接(Long Polling)的区别长链接(Long Polling)Server-Sent Events (SSE) 比较总结 2.通过okhttp调用SSE流式接口并流式返回给前端环境要求使用okhttp相关依赖示例 3. 如果Spring Framework 低于5.0，可使用Servlet 3.0进行…...

编程日记 2025/7/5 11:51:00

倚光科技助力自由曲面设计与加工

近年来，自由曲面因其在光学、汽车、航空航天等领域的广泛应用，受到设计师和工程师的高度关注。自由曲面作为一种具有更高自由度的非球面透镜，能够在光学系统中实现更加精确的光线控制，优化像差校正，并且在满足功能需求…...

编程日记 2025/6/28 19:19:43

【推荐算法】推荐系统中的单目标精排模型

前言：推荐系统中模型发展较快，初学者【也就是笔者】很难对模型进行一个系统的学习。因此，这篇文章总结了王树森中的视频以及《深度学习推荐系统》中的单目标精排模型，绘制了一个单目标精排模型的思维导图来帮助初学者【笔者】更好…...

编程日记 2025/7/4 22:32:03

Android UI：ViewTree：源码分析：事件处理：显示事件

文章目录概述测量：measure和onMeasure View.MeasureSpecViewViewGroupLinearLayoutRelativeLayout布局：layout和onLayout ViewViewGroupLinearLayoutRelativeLayout绘制：dispatchDraw、draw和onDraw ViewViewGroupLinearLayoutRelativeLayout总结概述显示事…...

编程日记 2025/7/5 10:29:37

esp32 OTA学习笔记

csv分区表中ota-0和ota-1存放程序不超过1600kb的程序可以ota（可手动划分） 分区表中有 ota0和ota1两个数据分区。 ota是指先下载固件到ota1然后下次从ota1启动，回滚就是回到ota0 启动。关于固件： bin文件可以用arduino生成也可以…...

编程日记 2025/7/5 11:28:48

口语笔记——祈使句用法

省略主语 (You give me) a cup of tea, please. 一杯茶(You wait for) another minute. 两等一分钟(You) keep quiet. 保持安静give me a break. 饶了我吧take your hand off. 把你的手拿开take this thing away 把这东西拿开never talk to strangers. 永远不要跟陌生人说话Do…...

编程日记 2025/7/5 12:03:29

【微软azure】【devtunnel隧道】工具的使用及介绍

简介：这是一个微软自带的能进行内网穿透的工具，最长30天有效期，可以定时更新，保证端口永久可用----可以理解为永久的nginx 前提：有azure账号，且要有相关权限，试用账号是不行滴使用说明 1.环…...

编程日记 2025/7/5 11:44:49

重生之我在异世界学智力题（1）

大家好，这里是小编的博客频道小编的博客：就爱学编程很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！ 本文目录引言智力题题目：《奇怪的时钟…...

编程日记 2025/7/5 11:37:55

九、页面级变量的状态管理

状态管理概述在声明式UI编程框架中，UI是程序状态的运行结果，用户构建了一个UI模型，其中应用的运行时的状态是参数。当参数改变时，UI作为返回结果，也将进行对应的改变。这些运行时的状态变化所带来的UI的重新渲染，在ArkUI中统称为状态管理机制。自定义组件拥有变量，变…...

编程日记 2025/7/5 10:59:09

#Vue3篇：defineOptionsvueUse

定义组件name 从 3.3 开始你可以直接通过 defineOptions 来设置组件名或 inheritAttrs 属性。 defineProps() 和 defineEmits() const props defineProps<{foo: stringbar?: number }>()const emit defineEmits<{(e: change, id: number): void(e: update, val…...

编程日记 2025/7/2 16:53:11

李飞飞的生成式3D场景，对数字孪生的未来影响几何？

大家好，我是日拱一卒的攻城师不浪，致力于技术与艺术的融合。这是2024年输出的第47/100篇文章。前言这两天，AI界的教母李飞飞团队重磅发布了空间智能生成式AI大模型。仅通过一张图片就能够生成一个可操作和交互的3D空间场景。空间智能的…...

编程日记 2025/7/3 1:08:53

《操作系统 - 清华大学》6 -7：局部页面置换算法：Belady现象

文章目录 1. 定义2. LRU、FIFO和Clock的比较 1. 定义局部页面置换算法的特点是针对一个正在运行的程序，它访问内存的情况，访问页的情况，来决定应该采取什么样策略，把相应的页替换出去，站在算法本身角度来考虑置换哪个…...

编程日记 2025/7/3 15:47:06

网络原理之 TCP 协议

目录 1. TCP 协议格式 2. TCP 原理 (1) 确认应答 (2) 超时重传 (3) 连接管理 a) 三次握手 b) 四次挥手 (4) 滑动窗口 (5) 流量控制 (6) 拥塞控制 (7) 延时应答 (8) 捎带应答 3. TCP 特性 4. 异常情况的处理 1) 进程崩溃 2) 主机关机 (正常流程) 3) 主机掉电 (…...

编程日记 2025/6/30 12:27:07

pinn爱看论文展

1.zhiwang 基于物理信息神经网络的波动方程优化求解方法吴丹澜1梁展弘2余懿3蔡博3郑邦宏4王梓超4张紫玲4 1.肇庆学院计算机科学与软件学院,大数据学院2.香港城市大学电气工程系3.云浮市新兴县公安局4.肇庆学院计算机科学与软件学院、大数据学院 2，zhiwang 就爱…...

编程日记 2025/7/3 19:16:44

Burp（5）web网页端抓包与app渗透测试

声明！ 学习视频来自B站up主泷羽sec 有兴趣的师傅可以关注一下，如涉及侵权马上删除文章，笔记只是方便各位师傅的学习和探讨，文章所提到的网站以及内容，只做学习交流，其他均与本人以及泷羽sec团队无关&…...

编程日记 2025/7/3 14:03:06

Spring 基础

什么是 Spring 框架? Spring 是一款开源的轻量级 Java 开发框架，旨在提高开发人员的开发效率以及系统的可维护性。我们一般说 Spring 框架指的都是 Spring Framework，它是很多模块的集合，使用这些模块可以很方便地协助我们进行开发&#…...

编程日记 2025/6/29 19:11:33

go 集成nacos注册中心、配置中心

使用限制 Go>v1.15 Nacos>2.x 安装使用go get安装SDK： go get -u github.com/nacos-group/nacos-sdk-go/v2 快速使用初始化客户端配置ClientConfig constant.ClientConfig{TimeoutMs uint64 // 请求Nacos服务端的超时时间，默…...

编程日记 2025/7/3 18:43:47

一文掌握 OpenGL 几何着色器的使用

学习本文需要具备 OpenGL ES 编程基础，如果看起来比较费劲，可以先看入门文章 OpenGL ES 3.0 从入门到精通系统性学习教程。什么是几何着色器几何着色器（Geometry Shader） OpenGL 管线中的可选着色器阶段，位于顶点着色器（Vertex Shader）和光栅化阶段之间。其核心…...

编程日记 2025/7/3 15:47:33

《数据资产入表：企业资产评估的新契机》

《数据资产入表：企业资产评估的新契机》在当今数字经济时代，数据作为关键生产要素，其重要性日益凸显。国家高度重视数据资产，陆续出台了一系列重磅政策。其中，“数据二十条” 即《中共中央国务院关于构建数据基础制度…...

编程日记 2025/7/3 12:41:32

架构14-资源与调度

零、文章目录架构14-资源与调度 1、资源模型 （1）概述在 Kubernetes 中，资源模型是一个非常重要的概念，它涉及如何管理和分配集群中的资源，以确保 Pod 能够在最合适的节点上运行。资源模型不仅包括物理资源&#…...

编程日记 2025/6/28 20:07:27

uni-app H5端使用注意事项【跨端开发系列】

🔗 uniapp 跨端开发系列文章：🎀🎀🎀 uni-app 组成和跨端原理【跨端开发系列】 uni-app 各端差异注意事项【跨端开发系列】uni-app 离线本地存储方案【跨端开发系列】uni-app UI库、框架、组件选型指南【跨端开…...

编程日记 2025/7/2 7:54:45

springboot407美发管理系统(论文+源码)_kaic

摘要传统办法管理信息首先需要花费的时间比较多，其次数据出错率比较高，而且对错误的数据进行更改也比较困难，最后，检索数据费事费力。因此，在计算机上安装美发管理系统软件来发挥其高效地信息处理的作用&#xff0…...

编程日记 2025/7/4 16:00:32

Apache-HertzBeat 开源监控默认口令登录

0x01 产品描述： HertzBeat(赫兹跳动) 是一个开源实时监控系统，无需Agent，性能集群，兼容Prometheus，自定义监控和状态页构建能力。HertzBeat 的强大自定义，多类型支持，高性能，易扩展，希望能帮助用户快速构建自有监控系统。0x02 漏洞描述： HertzBeat(赫兹跳动) 开源实时…...

编程日记 2025/7/2 17:44:07

发送请求时遇到了数据库完整性约束错误 1048 Column ‘platform‘ cannot be null

可以这样解决在 Vue 2 中封装接口请求时，确保每次请求都包含 platform Header 参数的最佳实践是通过创建一个全局的 Axios 实例，并为这个实例设置默认的 Header。这样可以确保所有通过该实例发送的请求都会自动包含 platform 参数。此外，你…...

编程日记 2025/7/3 6:09:51

Go快速开发框架集成Vue3漂亮的动态流程图编辑和动态流程展示插件

温馨提示：我们分享的文章是给需要的人，不需要的人请绕过，文明浏览，误恶语伤人！ 前言为大家在开发流程相关业务时有个漂亮流程图展示，我们集成一个实用的流程图编辑器，让流程开发变得简单&…...

编程日记 2025/7/3 15:04:48

【SH】微信小程序调用EasyDL零门槛AI开发平台的图像分类研发笔记

文章目录微信小程序字符串字符串模板字符串拼接上传图片GET请求测试编写测试代码域名不合法问题 GET和POST请求测试微信小程序字符串字符串模板这是ES6引入的特性，允许你通过反引号（）创建模板字符串，并在其中嵌入变量或表达…...

编程日记 2025/7/3 15:35:46

NanoLog起步笔记-6-StaticLogInfo

nonolog起步笔记-6-StaticLogInfo StaticLogInfo文件名和行号文件名和行号的传入log参数 RuntimeLogger::registerInvocationSitelogid为什么只能被赋一次值 reserveAlloc加入消息头finishAlloc返回 StaticLogInfo 写C语言编译前端时，给我印象深刻的一部分是&#…...

编程日记 2025/6/30 1:12:18

【OpenCV】视频录制

初始化一个视频写入对象，目的是将图像帧序列保存为视频文件。使用了OpenCV库中的cv2.VideoWriter类来创建这个对象，并且设置了视频的编码格式、帧率以及分辨率。导入库 import cv2 import datetime cv2 是 OpenCV 库的 Python 接口，提供了…...

编程日记 2025/7/3 4:49:13

同城到家预约上门服务解决方案：家政预约同城服务小程序

### 系统架构"同城到家预约上门服务解决方案：PHP家政预约同城服务小程序"采用B/S架构，后端使用PHP语言开发，前端则基于微信小程序平台。系统分为用户端、服务端和后台管理端，各端相互依赖又相互独立，支持多种…...

编程日记 2025/7/3 5:16:56

linux-14 关于shell（十三）type，内置命令和外部命令

我们说一个命令，叫做type，先来看看type的效果，比如说我指定type后面这个命令叫cd，如下图， 你看它说什么？cd is a shell builtin，我再 type ls，看它会说什么？如下图&#…...

编程日记 2025/7/3 13:06:59

使用php生成、识别二维码

1、生成二维码要求： # 详见：https://packagist.org/packages/bacon/bacon-qr-code php: ^8.1iconv Library imagick Library # 或者：GD library 下载： # 详见：https://packagist.org/packages/bacon/bacon-qr-cod…...

编程日记 2025/7/3 11:56:12

pytorch多GPU训练教程

pytorch多GPU训练教程文章目录 pytorch多GPU训练教程1. Torch 的两种并行化模型封装1.1 DataParallel1.2 DistributedDataParallel 2. 多GPU训练的三种架构组织方式2.2 数据不拆分，模型拆分（Model Parallelism）2.3 数据拆分，模型…...

编程日记 2025/7/2 10:53:35

日拱一卒（12）——leetcode学习记录：2的幂

一、题目判断一个整数n是否是2的幂次，是返回True，否返回False 二、分析 1. 递归法：如果n是0，返回False，如果n是1，返回True，其他情况，将n//2递归 2. 数学法：还是从数…...

编程日记 2025/7/4 15:07:57

非文件形式的内存动态函数库调用接口

使用memfd的系统调用接口将动态库加载到proc虚拟文件系统，提供的fd为进程持有的句柄，通过dlopen的path指向此句柄，即可实现非文件系统加载动态链接库。文章目录一、memfd_create二、dl_open三、示例参考一、memfd_create 接口名称int mem…...

编程日记 2025/7/3 5:46:48

TimeXplusplus——提高时间序列数据的可解释性，避免琐解和分布偏移问题的深度学习可解释性的框架

摘要论文地址：https://arxiv.org/abs/2405.09308 源码地址：https://github.com/zichuan-liu/timexplusplus 信号传输技术的优化对于推动光通信的发展至关重要。本文将详细探讨线路编码技术的目标及其实现方式。线路编码旨在提高带宽和功率效率&#xf…...

编程日记 2025/6/30 5:13:33

第十七届山东省职业院校技能大赛中职组“网络安全”赛项资源任务书样题②

第十七届山东省职业院校技能大赛中职组“网络安全”赛项资源任务书样题② 模块A 基础设施设置与安全加固(200分)A-1 登录安全加固（Windows, Linux）A-2 Nginx安全策略（Linux）A-3日志监控（Windows）A-4中间件…...

编程日记 2025/6/28 20:19:45

嵌入式蓝桥杯学习9 usart串口

复制一下之前ADC的工程，打开cubemx cubemx配置 1.在Connectivity中点击USART1 Mode（模式）:Asynchronous（异步模式） 2.将PA9设置为USART1_TX，PA10设置为USART1_RX。 3.配置Parameter Settings. Baud R…...

编程日记 2025/7/5 11:58:41

golang实现简单的redis服务4.0(持久化)

redis的持久化机制与实现原理RDB工作原理问题1:如果数量很大怎么办?问题2:子线程在持久化期间有新的数据写入会发生什么?如何保证数据一致性? AOF的原理如何解决aof文件越来越大的问题aof文件如何重写?aof如何恢复数据aof文件有问题(损坏了)恢复会发生什么?怎么办?aof有哪…...

编程日记 2025/6/28 6:09:51

安卓底层相机流的传输方式

这是安卓相机流的定义 typedef enum {CAM_STREAMING_MODE_CONTINUOUS, /* continous streaming */CAM_STREAMING_MODE_BURST, /* burst streaming */CAM_STREAMING_MODE_BATCH, /* stream frames in batches */CAM_STREAMING_MODE_MAX} cam_streaming_mode_t; 在ca…...

编程日记 2025/7/2 13:38:05

【YashanDB知识库】使用c-调用yashandb odbc驱动执行SQL时报YAS-08008 not all variables bounded

本文内容来自YashanDB官网，原文内容请见 https://www.yashandb.com/newsinfo/7508307.html?templateId1718516 问题现象某客户的应用(c# asp.net)在运行时报如下异常： 问题的风险及影响客户的应用无法正常运行问题影响的版本所有的yashandb版本…...

编程日记 2025/6/30 5:01:56