一文弄懂BFS【广度优先搜索(Breadth-First Search)】

BFS,全名为广度优先搜索(Breadth-First Search),是一种用于图或树的遍历或搜索的算法。它的主要思想是由节点自身开始向它的邻居节点新进展开搜索,因此也常被形象地称为“层序遍历”。
BFS 基本思想
BFS 工作原理是,从开始节点开始,在访问节点的邻居节点之前,我们先访问其它节点。换句话说,我们旧基于当前层次来遍历节点,然后移至下一层再遍历节点。BFS 是以一种队列(Queue)结构的方式运行的,首先我们有一个包含开始节点的队列,然后:
- 我们从队列的前端取出一个节点
- 为了防止回溯和重复访问,我们会标记取出的节点为已访问
- 针对取出的节点,把尚未访问过的邻居节点全部加入队列
- 我们重复以上步骤,直至队列为空
通过以上步骤,你将会发现,你在访问节点的时候,首先访问的是距离开始节点最近的节点(层次最低的节点),然后层次逐渐提升,这就是 BFS 的特性。
BFS 伪代码模板
BFS 主要应用于树和图结构的遍历,因此伪代码也大致分为对应的两类(以下都是基于未标记图进行的操作):
- 树的广度优先搜索
function BFS(root) {initialize queue;queue.push(root);while(!queue.empty()) {node = queue.front();queue.pop();process(node); //处理节点nodes = generate_related_nodes(node); //获取与节点相关的未访问过的子节点queue.push(nodes);}
}
- 图的广度优先搜索
function BFS(graph, start) {initialize queue and visited set;queue.push(start);visited.insert(start);while(!queue.empty()) {node = queue.front();queue.pop();process(node); //处理节点nodes = generate_related_nodes(node); //获取与节点相关的邻居节点for(node in nodes) {if(node not in visited) { //如果邻居节点尚未访问过queue.push(node);visited.add(node);}}}
}
接下来举出六个BFS经典问题,详细介绍和解题思路:
- 二叉树的层次遍历
在这个问题中,我们需要通过 BFS 遍历二叉树的每一层,以二维数组的形式返回结果。
vector<vector<int>> levelOrder(TreeNode* root) {if (!root) return {};vector<vector<int>> result;queue<TreeNode*> q;q.push(root);while (!q.empty()) {vector<int> one_level;for (int i = q.size(); i > 0; i--) {TreeNode* node = q.front();q.pop();one_level.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}result.push_back(one_level);}return result;
}
- 岛屿的个数
给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。
解题思路主要是遍历二维数组,当遇到 ‘1’ 时,通过 BFS 搜索并 ‘感染’ 周围的 ‘1’,最后计算 ‘1’ 的个数。
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};void bfs(vector<vector<char>>& grid, int x, int y, int row, int col) {queue<pair<int, int>> q;q.push({x, y});grid[x][y] = '0'; // 把 '1' 感染为 '0'while (!q.empty()) {auto [r, c] = q.front();q.pop();for (int i = 0; i < 4; ++i) {int nx = r + dx[i], ny = c + dy[i];if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == '1') {q.push({nx, ny});grid[nx][ny] = '0';}}}
}int numIslands(vector<vector<char>>& grid) {int row = grid.size();if (row == 0) {return 0;}int col = grid[0].size();int res = 0;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (grid[i][j] == '1') {bfs(grid, i, j, row, col);++res; // 计算岛屿数量}}}return res;
}
- 打开密码锁的最少步数
给你一个初始为 ‘0000’ 的四位密码,你可以每次对密码的任意一位做上下旋转:旋转一次可以将该位的数字增加 1 或减少 1 。求出最少的旋转次数,使得密码等于 target 。
int openLock(vector<string>& deadends, string target) {unordered_set<string> dead(deadends.begin(), deadends.end());if (dead.count("0000")) return -1;if (target == "0000") return 0;unordered_map<string, int> dist{{"0000", 0}};queue<string> q;q.push("0000");while (!q.empty()) {string t = q.front(); q.pop();for (int i = 0; i < 4; i++) {for (int j = -1; j <= 1; j += 2) {string str = t;str[i] = (str[i] - '0' + j + 10) % 10 + '0';if (str == target) return dist[t] + 1;if (!dead.count(str) && !dist.count(str)) {dist[str] = dist[t] + 1;q.push(str);}}}}return -1;
}
- 图中两点间最短路径长度
给定一个无向图,求从起点 s 到终点 t,最短路径长度是多少。
vector<unordered_set<int>> g; // 图
unordered_map<int, int> dist; // 从起点到每个点的距离int bfs(int s, int t) {queue<int> q;q.push(s);dist[s] = 0;while (!q.empty()) {int x = q.front(); q.pop();for (int y : g[x]) {if (!dist.count(y)) {dist[y] = dist[x] + 1;q.push(y);}}}return dist[t];
}
- 找到最近的医院
给定一个二维的 0-1 矩阵,1 表示医院,0 表示型房屋。求每个房屋距离最近医院的距离。
vector<vector<int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};vector<vector<int>> findNearestHospital(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dist(m, vector<int>(n, INT_MAX));queue<pair<int, int>> q;// BFS 队列// 先把所有的医院节点放进队列,然后开始 BFSfor(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == 1) {dist[i][j] = 0;q.push({i, j});}}}while(!q.empty()) {auto cur = q.front(); q.pop();for(auto dir : dirs) {int nx = cur.first + dir[0], ny = cur.second + dir[1];if(nx >= 0 && ny >= 0 && nx < m && ny < n) {if(dist[nx][ny] > dist[cur.first][cur.second] + 1) {dist[nx][ny] = dist[cur.first][cur.second] + 1;q.push({nx, ny});}}}}return dist;
}
- 最小基因变异
给定两个基因序列 start 和 end,一个基因库表 bank,求出把 start 变到 end 所需要的最小变异次数。一次基因变化代表改变一个字母。
int minMutation(string start, string end, vector<string>& bank) {unordered_set<string> dict(bank.begin(), bank.end());if (!dict.count(end)) return -1;unordered_map<string, int> dist{{start, 0}};queue<string> q;q.push(start);while (!q.empty()) {string gene = q.front(); q.pop();if (gene == end) return dist[gene];for (int i = 0; i < gene.size(); i++) {string newGene = gene;for (char c : "ACGT") {newGene[i] = c;if (dict.count(newGene) && !dist.count(newGene)) {dist[newGene] = dist[gene] + 1;q.push(newGene);}}}}return -1;
}
如果你想更深入地了解人工智能的其他方面,比如机器学习、深度学习、自然语言处理等等,也可以点击这个链接,我按照如下图所示的学习路线为大家整理了100多G的学习资源,基本涵盖了人工智能学习的所有内容,包括了目前人工智能领域最新顶会论文合集和丰富详细的项目实战资料,可以帮助你入门和进阶。
链接: 人工智能交流群【最新顶会与项目实战】(点击跳转)

相关文章:
一文弄懂BFS【广度优先搜索(Breadth-First Search)】
BFS,全名为广度优先搜索(Breadth-First Search),是一种用于图或树的遍历或搜索的算法。它的主要思想是由节点自身开始向它的邻居节点新进展开搜索,因此也常被形象地称为“层序遍历”。 BFS 基本思想 BFS 工作原理是,从开始节点开…...
深度学习记录--logistic回归函数的计算图
计算图用于logistic回归函数 先回顾一下单一样本的logistic回归损失函数的公式,公式如下: 将logistic函数用计算图表示出来(以两个基础量为例),计算图如下: 前向传播已经完成,接下来完成后向传播 运用链式法则依次求…...
Java基本数据类型详解
✨个人主页:全栈程序猿的CSDN博客 💨系列专栏:Java从入门到精通 ✌座右铭:编码如诗,Bug似流星,持续追求优雅的代码,解决问题如同星辰般自如 Java是一种强类型语言,数据类型在程序中起…...
第十五届蓝桥杯模拟赛(第二期)
大家好,我是晴天学长,本次分享,制作不易,本次题解只用于学习用途,如果有考试需要的小伙伴请考完试再来看题解进行学习,需要的小伙伴可以点赞关注评论一波哦!后续会继续更新第三期的。Ǵ…...
命令模式-C++实现
命令模式是一种行为型设计模式,它将请求封装成一个对象,从而能使你可以用不同的请求对客户端进行参数化。该模式允许请求的发送者和接收者进行解耦,发送者不需要知道接收者的信息,只需要通过命令对象来与它进行交互。 命令模式有…...
3dMax拼图生成工具Puzzle2D使用教程
Puzzle2D for 3dsMax拼图生成工具使用教程 Puzzle2D简介: 2D拼图随机生成器(英文:Puzzle2D) ,是一款由#沐风课堂#用MAXScript脚本语言开发的3dsMax建模小工具,可以随机创建2D可编辑样条线拼图图形。可批量…...
git报错invalid object xxx和unable to read tree xxxxxx
电脑出问题了,导致git仓库像是被损坏了一样,执行git status就会报错unable to read ree,无法正常提交代码至仓库,原因是本地代码仓库.git文件损坏了,无法找到正确的提交历史和路径。 找到了一个解决办法: …...
会泽一村民上山放羊吸烟引发森林火灾,AI科技急需关注
2023年4月,会泽县古城街道厂沟村委会望香台山林中发生了一场由疏忽引发的森林火灾。张某某在放羊时未完全熄灭烟头,导致7.33公顷的林地和草地被焚毁,直接经济损失高达29.097万元。这一事件再次凸显了日常生活中的安全隐患。 在这一背景下&…...
docker-compose部署zabbix+grafana
1.引言 1.1目的 zabbixgrafana实现图形化监控 2.部署环境 服务器ip服务版本192.168.5.137zabbix-server6.0.21192.168.5.137grafana10.2.2192.168.5.152zabbix-client6.0.21 3.部署zabbix-server 3.1 创建zabbix目录 mkdir zabbix3.2 编写docker-compose文件 cd zabbix…...
ios 逆向分分析,某业帮逆向算法(二)
接上讲 上次hook 发现自己的数据有点问题。才发现是自己的编辑器识别出问题了。 上篇sub_1029B6898函数hook数据如下: [iOS Device::作业帮 ]-> arg2: 0 1 2 3 4 5 6 7 8 9 A B C D E F 0123456789ABCDEF 00000000 37 32 65 64 38 31 32 38…...
openCv颜色矩
颜色矩(Color Moments)是一种常用的图像特征描述方法,用于表示图像中颜色的分布和统计特征。它是基于图像的颜色直方图而计算得到的。 颜色矩通常包括三个维度:平均值、方差和偏度。具体来说: 平均值(Mean…...
〖大前端 - 基础入门三大核心之JS篇㊹〗- DOM事件委托
说明:该文属于 大前端全栈架构白宝书专栏,目前阶段免费,如需要项目实战或者是体系化资源,文末名片加V!作者:不渴望力量的哈士奇(哈哥),十余年工作经验, 从事过全栈研发、产品经理等工作…...
正是阶段高等数学复习--函数极限的计算
之前在预备阶段中函数极限的解决方式分三步,第一步观察形式并确定用什么方式来解决,第二步化简,化简方式一共有7种,分别是最重要的三种(等价替换、拆分极限存在的项、计算非零因子)以及次重要的4种…...
Linux-usb触摸板去除鼠标箭头
usb触摸板会同时加载hid-generic.c和hid-multitouch.c驱动 [ 213.602561] usb 4-1: new full-speed USB device number 2 using ohci-platform [ 213.834953] usb 4-1: New USB device found, idVendor6615, idProduct108c, bcdDevice 1.30 [ 213.835048] usb 4-1: New USB…...
【微信小程序】英文字母不换行问题 flex布局字符超出宽度折行问题:设置了word-break: break-all;和flex: 1;冲突flex不生效问题
flex布局中英文字符超出宽度不会自动折行的问题,但是设置了word-break: break-all;前面设置的flex: 1;就不生效了 1.英文字母不换行问题 .view_text {word-break: break-all; }如果使用flex仅仅设置word-break: break-all;是会影…...
python--自动化办公(Word)
python自动化办公之—Word python-docx库 1、安装python-docx库 pip install python-docx2、基本语法 1、打开文档 document Document() 2、加入标题 document.add_heading(总标题,0) document.add_heading(⼀级标题,1) document.add_heading(⼆级标题,2) 3、添加文本 para…...
sourceTree的下载和安装
sourceTree的下载和安装 一、概述 SourceTree 是一款免费的 Git 和 Hg 客户端管理工具,支持 Git 项目的创建、克隆、提交、push、pull 和合并等操作。它拥有一个精美简洁的界面,大大简化了开发者与代码库之间的 Git 操作方式,这对于不熟悉 …...
解决:ModuleNotFoundError: No module named ‘PyQt5‘
解决:ModuleNotFoundError: No module named ‘PyQt5’ 文章目录 解决:ModuleNotFoundError: No module named PyQt5背景报错问题报错翻译报错位置代码报错原因解决方法安装PyQt5在PyCharm中配置PyQt5对于新项目对于已有项目 今天的分享就到此结束了 背景…...
极客时间 - 如何成为学习高手【文章笔记 + 思考总结】
如何成为学习高手【文章笔记 思考总结】 高度自律 高度自律 5分钟起步法。 稍微走在计划前面。 替代拖延法。 自律:从不自律的念头中,约束自己。有变弱倾向时进行对抗。 在一种痛苦和另一种痛苦之间做选择,选择那个有意义的痛苦。 在某些固…...
前端笔记(二):CSS 选择器与特性
CSS(层叠样式表)是一种样式表语言,用于描述HTML或XML文档的呈现方式。它定义了如何在屏幕、纸张或其他媒体上显示文档的样式、布局和外观。 里面的代码由 选择器 { } 组成 体验 CSS CSS 可以让我们界面变得更加美观,这是 CSS 的…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
