BFS解决最短路问题(详解)

news/2024/7/14 18:26:24/文章来源:https://blog.csdn.net/2302_79862386/article/details/139247145

目录

BFS简介 && 框架:

一.二叉树的最小深度 

二:迷宫中里入口最近的出口:

 三.最小基因变化:

 四:单词接龙:

​五:为高尔夫比赛砍树:


BFS简介 && 框架:

说到BFS,想必大家都不陌生,我们在学习二叉树的遍历时所用到的层序遍历其实就是BFS,那么BFS能解决什么样的问题呢?通过本文标题,你也大致能猜到----解决最短路问题,这是一个比较经典的问题,当然,BFS还能解决很多其他问题,本文就着重介绍其中一种---最短路问题。

BFS基本概念:

  • BFS(广度优先搜索):是一种图形搜索算法,它从根节点开始,逐层地向下扩展搜索。BFS通常用队列来实现,即先进先出的数据结构。这意味着每个节点都将按照它们被发现的顺序进行处理。具体地说,BFS算法会首先访问根节点,然后将其所有相邻的节点加入队列中。接下来,它将按照与队列中节点相同的顺序访问这些新节点,并将它们的相邻节点加入队列中。该过程一直持续到所有节点都被访问为止。

我们先举例一下 BFS 出现的常见场景吧,问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离,这个例子听起来很枯燥,但是 BFS 算法问题其实都是在干这个事儿 ,其对应的大致框架如下:

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {Queue<Node> q; // 核心数据结构Set<Node> visited; // 避免走回头路q.offer(start); // 将起点加入队列visited.add(start);while (q not empty) {int sz = q.size();/* 将当前队列中的所有节点向四周扩散 */for (int i = 0; i < sz; i++) {Node cur = q.poll();/* 划重点:这里判断是否到达终点 */if (cur is target)return step;/* 将 cur 的相邻节点加入队列 */for (Node x : cur.adj()) {if (x not in visited) {q.offer(x);visited.add(x);}}}}// 如果走到这里,说明在图中没有找到目标节点
}

一.二叉树的最小深度 

先来个简单的问题实践一下 BFS 框架吧,判断一棵二叉树的最小高度,这也是力扣第 111 题「二叉树的最小深度open in new window」: 

题目描述:

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明:叶子节点是指没有子节点的节点。

这题比较简单,直接套用上面的框架即可,遇到第一个叶子节点直接返回对应深度即可:

代码详解:

class Solution {public int minDepth(TreeNode root) {Queue<TreeNode> q = new LinkedList<>();if(root == null){return 0;}int depth = 1;//初始树的深度是1q.offer(root);while(!q.isEmpty()){int sz = q.size();for(int i = 0;i < sz;i++){TreeNode cur = q.poll();if(cur.left == null && cur.right == null){return depth;}//----->如果cur == null --->//  cur.left不存在,null指针异常/*       q.offer(cur.left);q.offer(cur.right);不能直接将节点放入队列,*/if(cur.left != null){//要判空q.offer(cur.left);}if(cur.right != null){q.offer(cur.right);}}depth++;}return depth;}
}

运行结果:

这里注意这个 while 循环和 for 循环的配合,while 循环控制一层一层往下走,for 循环利用 sz 变量控制从左到右遍历每一层二叉树节点,将节点加入到队列中

二:迷宫中里入口最近的出口:

题目链接:1926. 迷宫中离入口最近的出口 - 力扣(LeetCode)

题目描述:

给你一个 m x n 的迷宫矩阵 maze (下标从 0 开始),矩阵中有空格子(用 '.' 表示)和墙(用 '+' 表示)。同时给你迷宫的入口 entrance ,用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作,你可以往  或者  移动一个格子。你不能进入墙所在的格子,你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子entrance 格子 不算 出口。 

请你返回从 entrance 到最近出口的最短路径的 步数 ,如果不存在这样的路径,请你返回 -1 。

思路:我们可以从起点开始层序遍历,并且在遍历的过程中记录当前遍历的层数。这样就能在找到出⼝的 时候,得到起点到出⼝的最短距离

其中,为了方便表示四个方向,我们可以通过定义两个数组来表示方向:dx[ ],dy[ ],其中dx[ ],dy[ ]的位置要一一对应,具体操作如下:

代码详解:

class Solution {int[] dx = {0,0,-1,1};int[] dy = {1,-1,0,0};boolean[][] used;public int nearestExit(char[][] maze, int[] e) {int m = maze.length,n = maze[0].length;used = new boolean[m][n];//HashSet -- > Set来记录路径(走过的就不要再去走了)Queue<int[]> q = new LinkedList<>(); //int[]用来记录maze的下标q.offer(new int[]{e[0],e[1]});used[e[0]][e[1]] = true;int step = 0;//初始步数是0while(!q.isEmpty()){int sz = q.size();step++;for(int i = 0;i < sz;i++){int[] arr = q.poll();int a = arr[0],b = arr[1];for(int k = 0;k < 4;k++){//四个方向int x = dx[k] + a,y = dy[k] + b;if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && !used[x][y]){if(x == 0 || x == m - 1 || y == 0 || y == n - 1){return step;}q.offer(new int[]{x,y});used[x][y] = true;}}}}return -1;//找不到就返回-1}
}

运行结果:

 三.最小基因变化:

题目链接:433. 最小基因变化 - 力扣(LeetCode)

题目描述:

基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是 'A''C''G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

  • 例如,"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化,只有基因库中的基因才是有效的基因序列。(变化后的基因必须位于基因库 bank 中)

给你两个基因序列 start 和 end ,以及一个基因库 bank ,请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化,返回 -1 。

注意:起始基因序列 start 默认是有效的,但是它并不一定会出现在基因库中。

思路:用哈希表来记录搜索过的状态,存储基因库的信息(后续O(1)的时间查找),遍历一个字符串,将每个位置的可能的四种情况全部枚举出来,将没有被搜过或者存在基因库中的节点加入到队列。

代码详解:

class Solution {public int minMutation(String startGene, String endGene, String[] bank) {Set<String> hash = new HashSet<>();Set<String> vis = new HashSet<>();for(String x : bank) hash.add(x);char[] change = {'A','C','G','T'};if(!hash.contains(endGene)) return -1;if(endGene.equals(startGene)) return 0;Queue<String> q = new LinkedList<>();q.offer(startGene);vis.add(startGene);int step = 0;while(!q.isEmpty()){step++;int sz = q.size();while(sz-- != 0){String cur = q.poll();for(int i = 0;i < 8;i++){char[] temp = cur.toCharArray();for(int j = 0;j < 4;j++){temp[i] = change[j];String next = new String(temp);if(!vis.contains(next) && hash.contains(next)){if(next.equals(endGene)) return step;q.offer(next);vis.add(next);}}}}}return -1;}
}

运行结果:

 四:单词接龙:

题目链接:127. 单词接龙 - 力扣(LeetCode)

题目描述:

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk

  • 每一对相邻的单词只差一个字母。
  •  对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。
  • sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ,返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0 。

与上面一题基本类似,直接看代码:

class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Set<String> hash = new HashSet<>();//用于记录单词库中的单词Set<String> vis = new HashSet<>();//用于记录路径for(String x : wordList) hash.add(x);char[] change = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};//记录要该表的列表//处理一下边界条件//if(beginWord.equals(endWord)) return 1; -->题目给出不会相等if(!hash.contains(endWord)) return 0;//bfsQueue<String> q = new LinkedList<>();q.offer(beginWord);vis.add(beginWord);int step = 1;//用于记录单词数while(!q.isEmpty()){step++;int sz = q.size();while(sz-- != 0){String cur = q.poll();int k = cur.length();for(int i = 0;i < k;i++){char[] temp = cur.toCharArray();for(int j = 0;j < 26;j++){temp[i] = change[j];String next = new String(temp);//满足条件入队列if(!vis.contains(next) && hash.contains(next)){if(next.equals(endWord)) return step;//找到直接返回单词数q.offer(next);vis.add(next);}}}}}return 0;}
}

运行结果:

五:为高尔夫比赛砍树:

题目链接:675. 为高尔夫比赛砍树 - 力扣(LeetCode)

题目描述:

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示, 在这个矩阵中:

  • 0 表示障碍,无法触碰
  • 1 表示地面,可以行走
  • 比 1 大的数 表示有树的单元格,可以行走,数值表示树的高度

每一步,你都可以向上、下、左、右四个方向之一移动一个单位,如果你站的地方有一棵树,那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树,每砍过一颗树,该单元格的值变为 1(即变为地面)。

你将从 (0, 0) 点开始工作,返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树,返回 -1 。

可以保证的是,没有两棵树的高度是相同的,并且你至少需要砍倒一棵树。

思路:

a. 先找出砍树的顺序;

b. 然后按照砍树的顺序,⼀个⼀个的⽤ bfs 求出最短路即可。 

代码详解:

class Solution {int m,n;public int cutOffTree(List<List<Integer>> forest) {m = forest.size();n = forest.get(0).size();//将是树的位置装入容器中List<int[]> trees = new ArrayList<>();for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(forest.get(i).get(j) > 1){trees.add(new int[]{i,j});}}}//排序,按照树的相对高度对树对应坐标排序Collections.sort(trees,(a,b) ->{return forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]);});int res = 0;int bx = 0,by = 0;for(int[] tree : trees){int x = tree[0],y = tree[1];//拿出下一个要去的位置的下表int step = bfs(forest,bx,by,x,y);//迷宫问题if(step == -1) return -1;res += step;//所有路径的最小值的和,就是答案bx = x;by = y;//更新起始位置的值}return res;}//迷宫问题->找到目标位置的最小步数int[] dx = {0,0,-1,1};int[] dy = {1,-1,0,0};public int bfs(List<List<Integer>> forest,int bx,int by,int ex,int ey){if(bx == ex && by == ey) return 0;//如果目标就在原地,直接返回boolean[][] used = new boolean[m][n];Queue<int[]> q = new LinkedList<>();q.offer(new int[]{bx,by});used[bx][by] = true;int step = 0;while(!q.isEmpty()){step++;int sz = q.size();while(sz-- != 0){int[] temp = q.poll();int a = temp[0],b = temp[1];for(int i = 0;i < 4;i++){int x = a + dx[i],y = b + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && !used[x][y] && forest.get(x).get(y) != 0){if(x == ex && y == ey) return step;q.offer(new int[]{x,y});used[x][y] = true;}}}}return -1;//没找到就返回-1}
}

结语: 写博客不仅仅是为了分享学习经历,同时这也有利于我巩固知识点,总结该知识点,由于作者水平有限,对文章有任何问题的还请指出,接受大家的批评,让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注,你们的鼓励是我创作的最大动力!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1052235.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

在C++中自定义命名空间,在命名空间中定义string变量,同时定义一个函数实现单词逆置

代码 #include <iostream> #include <cstring> using namespace std; namespace my_space {string s;void reverse(string s);//定义逆置函数 } using namespace my_space; void my_space::reverse(string s){int lens.size();int i0;int jlen-1;while(i<j){//…

CIM模型

CIM 是 Esri 制图信息模型。 它是一个地图内容规范,用于记录在保存、读取、引用或打开时如何永久保留描述不同项目组件的信息。 该规范以 JSON 表示,适用于 ArcGIS 应用程序和 API 中的地图、场景、布局、图层、符号和样式。 CIM 不仅限于制图设置。 要了解属性的组织方式以及…

如何停止 iPad 和 iPhone 之间共享短信,独立接收和发送消息

概括 在当今高度互联的数字世界中&#xff0c;Apple 设备之间的无缝连接性提供了极大的便利&#xff0c;尤其是在消息同步方面。iPhone 和 iPad 用户通常可以享受到设备间短信的自动同步功能&#xff0c;这意味着无论是在哪个设备上&#xff0c;用户都可以接收和回复消息。然而…

六.逼格拉满-Prometheus+Grafana微服务监控告警

前言 微服务架构是一个分布式系统&#xff0c;由多个独立的服务组成&#xff0c;每个服务可能运行在不同的容器、虚拟机或物理机上&#xff0c;那么在生产环境中我们需要随时监控服务的状态&#xff0c;以应对各种突发情况&#xff0c;比如&#xff1a;内存爆满&#xff0c;CP…

【Oracle篇】rman工具实用指南:常用命令详解与实践(第二篇,总共八篇)

&#x1f4ab;《博主介绍》&#xff1a;✨又是一天没白过&#xff0c;我是奈斯&#xff0c;DBA一名✨ &#x1f4ab;《擅长领域》&#xff1a;✌️擅长Oracle、MySQL、SQLserver、阿里云AnalyticDB for MySQL(分布式数据仓库)、Linux&#xff0c;也在扩展大数据方向的知识面✌️…

[NISACTF 2022]easyssrf、[NISACTF 2022]level-up

[NISACTF 2022]easyssrf 使用dirsearch扫描后没发现什么路径 尝试访问127.0.0.1&#xff0c;成功了 访问127.0.0.1/flag.php提示有文件/fl4g 使用file://协议读取文件/fl4g&#xff0c;提示除此页面外还有一个ha1x1ux1u.php页面。 file:///fl4g 直接访问&#xff0c;发现GET…

google浏览器下载和相应驱动下载

1、chromedriver 115及115之后版本下载地址&#xff1a; https://googlechromelabs.github.io/chrome-for-testing/ 2、chromedriver 115之前版本下载地址&#xff08;已停止更新115及之后版本&#xff09;&#xff1a; http://chromedriver.storage.googleapis.com/index.html…

PVE 虚拟机环境下删除 local-lvm分区

1、删除逻辑卷 lvremote pve/data 2、扩展逻辑卷 lvextend -l 100%FREE -r pve/root 3、 修改存储目录内容 点击 Datacenter - Storage &#xff08;1&#xff09;删除local-lvm分区 &#xff08;2&#xff09;编辑local分区&#xff0c;在内容一项中勾选所有可选项。

python数据处理与分析入门-Pandas数据可视化例子

相关内容 Matplotlib可视化练习 Pandas 数据可视化总结 柱状图 reviews[points].value_counts().sort_index().plot.bar()散点图 reviews[reviews[price] < 100].sample(100).plot.scatter(xprice, ypoints)蜂窝图 reviews[reviews[price] < 100].plot.hexbin(xprice…

C++:vector基础讲解

hello&#xff0c;各位小伙伴&#xff0c;本篇文章跟大家一起学习《C&#xff1a;vector基础讲解》&#xff0c;感谢大家对我上一篇的支持&#xff0c;如有什么问题&#xff0c;还请多多指教 &#xff01; 如果本篇文章对你有帮助&#xff0c;还请各位点点赞&#xff01;&#…

分类和品牌关联

文章目录 1.数据库表设计1.多表关联设计2.创建表 2.使用renren-generator生成CRUD1.基本配置检查1.generator.properties2.application.yml 2.生成代码1.进入localhost:81生成代码2.将main目录覆盖sunliving-commodity模块的main目录 3.代码检查1.注释掉CategoryBrandRelationC…

沃飞携AE200真机亮相澳门,全方位赋能城市低空出行

5月22日-25日&#xff0c;第四届BEYOND国际科技创新博览会&#xff08;BEYOND Expo 2024&#xff09;在澳门盛大举行。吉利沃飞长空携旗下全自研产品AE200真机亮相&#xff0c;吸引了现场众多领导嘉宾以及媒体、观众的关注。 作为亚洲顶尖的年度科技盛会&#xff0c;本届BEYOND…

面试-软件工程与设计模式相关,Spring简介

面试-软件工程与设计模式相关&#xff0c;Spring简介 1.编程思想1.1 面向过程编程1.2 面向对象编程1.2.1 面向对象编程三大特征 1.3 面向切面编程1.3.1 原理1.3.2 大白话&#xff1f;1.3.3 名词解释1.3.4 实现 2. 耦合与内聚2.1 耦合性2.2 内聚性 3. 设计模式3.1 设计模型七大原…

nodejs安装配置

nodejs安装 打开nodejs官网(https://nodejs.org/en/download/package-manager)&#xff0c;参考安装步骤操作。 更新镜像源 输入以下命令&#xff0c;将npm的镜像源设置为淘宝镜像。网上资料中&#xff0c;淘宝镜像地址多为https://registry.npm.taobao.org&#xff0c;这个…

js之图片上传

话不多说&#xff0c;直接上干货&#xff0c;注释在代码里面 下面是效果图和代码 <!DOCTYPE html> <html lang"zh"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-sca…

景源畅信:新手做抖音运营难不难?

在这个信息爆炸的时代&#xff0c;社交媒体平台如抖音已经成为了人们日常生活中不可或缺的一部分。随着抖音的兴起&#xff0c;越来越多的人开始尝试进入这个领域&#xff0c;希望通过抖音运营实现自己的价值。然而&#xff0c;对于新手来说&#xff0c;抖音运营是否真的容易呢…

现代前端工程化实践:Git、Husky、Commitlint与PNPM的协同作战

引言 Git Husky 与 Commitlint 是两个在 Git 工作流程中非常实用的工具&#xff0c;它们可以帮助团队维护代码质量和提交规范。Husky 是一个 Git 钩子管理器&#xff0c;允许你在仓库级别方便地配置钩子脚本&#xff1b;而 Commitlint 则是用来规范 Git 提交信息的工具&#x…

Bootstrap5

Bootstrap5-容器 容器是Bootstrap—个基本的构建块&#xff0c;它包含、填充和对齐给定设备或视口中的內容。 Bootstrap 需要一个容器元素来包裏网站的内容 我们可以使用以下两个容器类&#xff1a; .container 类用于固定宽度并支持响应式布局的容器。.container-fluid 类用…

左外连接和右外连接的区别?举例说明——以力扣sql 1378. 使用唯一标识码替换员工ID为例

左外连接&#xff08;LEFT JOIN&#xff09;和右外连接&#xff08;RIGHT JOIN&#xff09;的主要区别在于哪个表的所有行会保留在结果集中 1. 左外连接 (LEFT JOIN) 左外连接会返回左表中的所有行以及右表中符合连接条件的行。如果右表中没有匹配的行&#xff0c;结果集中右…

剖析【C++】——类与对象(上)超详解——小白篇

目录 1.面向过程和面向对象的初步认识 1.面向过程&#xff08;Procedural Programming&#xff09; 2.面向对象&#xff08;Object-Oriented Programming&#xff09; 概念&#xff1a; 特点&#xff1a; 总结 2.C 类的引入 1.从 C 语言的结构体到 C 的类 2.C 中的结构…