【基础算法总结】BFS 解决最短路径问题

BFS 解决最短路径问题

  • 1.最短路径问题简介
  • 2.迷宫中离入口最近的出口
  • 3.最小基因变化
  • 4.单词接龙
  • 4.为高尔夫比赛砍树

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃

1.最短路径问题简介

最短路径问题是图论里面最重要的问题,它里面最短路径问题包括单源最短路、多元最短路、边权为1的最短路、带负环的最短路等等。

这里我们只说 边权为 1 的最短路径问题

那什么是最短路径问题?
比如有一些地区,地区之间有道路相连,它会给一个起点,问到达另一个点最短的路径是多少?
在这里插入图片描述

边上面可能赋予权值,权值可以理解为两个点之间的长度。然后有长度的时候问题你从 A->I 最短路径是多少?

在这里插入图片描述

但是这里我们不研究这种麻烦的最短路问题,我们只研究最简单最短路问题,边权都是为1的,意思是每一个边的权值都是相同的。 边权可以都为2、3、4等等,反正就是边权值都相同。

这类最短路问题怎么解决呢?
特别简单,从起点开始,来一次 BFS 即可。

下面模拟一下,做 BFS 我们需要一个队列,还需要一个可以是hash表,也可以是数组来标记当前这个位置是否已经访问过!

在这里插入图片描述

刚开始把起点丢入队列里面,并且在hash标记A已经被访问过。

在这里插入图片描述

接下里弹出队头元素,把队头元素能去的地方加入到队列。相当于在A这一层的基础上又往外扩了一层

在这里插入图片描述

接下来重要的来了,我们会先统计队列中有多少元素,然后同时把队列中元素都弹出去。但是还是有一个先后,所以先弹B,在弹C。我们是在一个循环中进行的,依次把这两个元素都弹出,意思就是把刚刚扩展出来的这一层在同一时间在向外扩展一层。

总结一下:弹出元素之前,先统计队列中有多少元素,然后循环把当前队列中的元素弹出,然后把与其相连的地方加入队列。

这两者虽然有先后,但是在我们看来是同时往外扩展的。
在这里插入图片描述

接下来也是这样的操作,我们先把D弹出,把D能相连的地方加进来,但是扩展D的时候,发现E已经加入到队列中,此时就不需要把E加入到队列中了。

因为这块在把后来的E加进来后面路径和之前加入的队列的E走的是一样的,而且这个后来的E加了之后也不是最优解,因为之前发现一条路到E了,而此时你的E是后过来的,那你的路径就是比我长,肯定不是最优解。

所以需要一个数组或者hash来标记当前位置是否被访问过。

在这里插入图片描述

到E的时候把和E相连的地方加入队列。
在这里插入图片描述

然后重复刚才的过程,统计队列中的元素个数,然后把F弹出去的时候会把I加入队列,把G弹出去的时候把H加入队列,但是这一步不用做了。因为把F弹出把I加入队列此时我们就已经找到终点了,后面的过程就不用进行了。我们此时已经找到最短路径了。那就是从 A -> C -> E -> F -> I。

在这里插入图片描述

接下来感性的证明一下为什么 BFS 能够找到最短路径,为什么一层一层往外拨开第一次碰到终点就说找到最短路径了呢?

从 A 到 I 其实有特别多的路,我们层序遍历的过程相当于有很多小人在A起点同时出发同时每次向后移动一个单位,原因在于我们边的权值都是一样的。当我们发现一个小人以最快的速度到达 I 这个位置,那绝对是最优的。原因就是每个人每一次移动的时候路程是相等的、速度是相等的、时间是相等的,所以最先到达 I 位置,这条路径就是最优路径。

在这里插入图片描述

这种问题一般都是问 最短路径是多少? 那如何找出最短路径是多少呢?

这里我们发现,你扩展层数是多少你的最短路径就是多少。

比如说从A扩展到B、C 这是一层,从B、C扩展到D、E 又是一层,从D、E扩展到F、G 又一层,从F、G扩展到 I 又是一层,总共扩展四层,因此最短路径是4。

所以可以搞一个变量,每扩展一层就++一下。当第一次扩展到 I 的时候停止,返回这个变量就可以了。

在这里插入图片描述

2.迷宫中离入口最近的出口

题目链接:1926. 迷宫中离入口最近的出口

题目分析:

在这里插入图片描述

给你一个 m x n 的迷宫矩阵 maze (下标从 0 开始),矩阵中有空格子(用 ‘.’ 表示)和墙(用 ‘+’ 表示)。同时给你迷宫的入口 entrance ,用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列,你可以上下左右四个方向移动,让你找到离你刚开始所在位置最近的出口并且返回路径。这里的出口就是在maze边界上的空格子。注意刚开始的位置即使就是在maze边界上的空格子上也不能算作出口。如果不存在路径返回-1.

在这里插入图片描述

算法原理:

以第一个例子为例,刚开始这个小人可以向上走也可以向左走,如果把小人抽象成点的话,此时把点连成线,会发现每次都只走一步。会发现权值都是1,所以这个问题就可以转换成 边权为1的最短路径问题。从开始点出发到边界上的点最短路径是多少。

在这里插入图片描述

边权为 1 的最短路径问题

解法:BFS
如何解决前面已经说的非常详细了。把刚开始位置加入队列,然后一层一层往外扩,直到扩展到边界上的点为止。返回扩展的层数即可。注意还要搞一个二维数组用来标记当前为止是否已经被访问过了。

class Solution {bool vis[101][101]={0};int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};
public:int nearestExit(vector<vector<char>>& maze, vector<int>& e) {int m = maze.size(), n = maze[0].size();queue<pair<int,int>> q;q.push({e[0],e[1]});vis[e[0]][e[1]] = true;int step = 0;while(q.size()){++step;int sz = q.size();for(int i = 0; i < sz; ++i){auto [a, b] = q.front();q.pop();for(int k = 0; k < 4; ++k){int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && !vis[x][y]){               if(x == 0 || x == m-1 || y == 0 || y == n-1) return step;q.push({x,y});vis[x][y] = true;}}  }}return -1;//层序遍历结束之后还没有找到出口,返回-1}
};

3.最小基因变化

题目链接: 433. 最小基因变化

题目分析:

在这里插入图片描述

基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是’A’、‘C’、‘G’ 和 ‘T’ 之一。求从基因序列 start 变为 end 所发生的有效的基因变化并且是最小的。有效的基因变化指的是start每次基因变化如果都是在基因库 bank 里就是有效的。一次基因变化就意味着这个基因序列中的一个字符发生了变化。例如,“AACCGGTT” --> “AACCGGTA” 就是一次基因变化。
在这里插入图片描述

算法原理:

先把这到题转为为之前遇到的关于图论问题中的, 边权为 1 的最短路径问题

给一个起始的基因序列,给一个终止的基因序列,想把这个起始基因序列转化为终止的基因序列。在转化过程中要求每次转化只能改变基因序列中其中一个字符并且只能从"A",“C”,“G”,"T"中任取一个字符。

在这里插入图片描述

如果把一个一个字符串抽象出图论中一个个点,那这个问题不就变成了,给一个起始位置和一个终止位置,中间有一些变化的的过程,问起始位置到终点位置最短路径是多少,这问题不就完美的抽象成图论问题吗。并且每次都是一步变化,因此就转变成 边权为 1 的最短路径问题

在这里插入图片描述

接下来就是细节问题:

肯定要创建一个队列,队列里存的是一个个字符串。而且还需要一个东西来标记当前字符串已经被搜索过了。原因是CAAA 继续向外扩展会回到AAAA这就有问题了,因此需要标记字符串已经被搜索。这里不能在用数组了,我们用hash表存一个个字符串。

在这里插入图片描述

  1. 用哈希表来标记搜索过的状态
  2. 如何枚举出当前这一次所有变化情况呢?

很简单搞一个for循环,对字符串中每一个字符遍历依次,并且每一个字符都按顺序修改成"A",“C”,“G”,“T”。这样就枚举出当前这一次所有变化情况。遍历字符串中每一个位置然后每一个位置都修改四次!而且因为我们前面有哈希表标记搜索过的状态因此不会有重复的情况,不用在判断一次当前字符串和前面字符串是否相等在修改,如 CAAA -> AAAA,因为AAAA已经被标记过搜索了,所以不用特殊判断。

  1. 枚举出来的所有情况,都需要加入到队列里面吗?

并不需要,只需要把枚举出来并且在基因库bank里面的才加入到队列。

  1. 如何快速判断是否在基因库中存在

把基因库中的字符串加入到hash表。此时枚举出来的字符串就可以在这个hash表找一下就可以。

class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_set<string> hash(bank.begin(),bank.end());// 存储基因库里面的基因序列unordered_set<string> vis; // ⽤来标记已经搜索过的状态if(startGene == endGene) return 0;if(!hash.count(endGene)) return -1;queue<string> q;q.push(startGene);vis.insert(startGene);int step = 0;string change = "ACGT";while(q.size()){step++;int n = q.size();while(n--){string t = q.front();q.pop();for(int i = 0; i < 8; ++i){string tmp = t;//细节问题,我们只是修改字符串的一个字符,下一次还想在原始字符串中修改下一个字符for(int j = 0; j < 4; ++j){tmp[i] = change[j];if(hash.count(tmp) && !vis.count(tmp)){if(tmp == endGene) return step;q.push(tmp);vis.insert(tmp);} }}}}return -1;}
};

4.单词接龙

题目链接:127. 单词接龙

题目分析:

在这里插入图片描述

给一个起始单词给一个终止单词求起始单词转化为终止单词 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0 。这道题和上面几乎是一模一样,唯一不一样的就是求得是最短转换序列 中的 单词数目 。转化规则还是每次遍历字符串中每一个位置,每一个位置都可以 从 ‘a’~‘z’ 中按照顺序改变,但是不是盲目改变,改变之后得字符串必须在wordList字典中存在才行。才属于一次有效改变。

算法原理:

和最小基因序列几乎一模一样,不过就换成了每个位置从 ‘a’ ~ ‘z’ 中选,而且最终返回的是 最短转换序列 中的 单词数目 ,因此第一个进入队列的也要算上。

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> hash(wordList.begin(),wordList.end());unordered_set<string> vis;// ⽤来标记已经搜索过的状态if(!hash.count(endWord)) return 0;queue<string> q;q.push(beginWord);vis.insert(beginWord);int ret = 1;while(q.size()){ret++;int n = q.size();while(n--){string t = q.front();q.pop();for(int i = 0; i < t.size(); ++i){string tmp = t;for(char ch = 'a'; ch <= 'z'; ++ch){tmp[i] = ch;if(hash.count(tmp) && !vis.count(tmp)){if(tmp == endWord) return ret;q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};

4.为高尔夫比赛砍树

题目链接: 675. 为高尔夫比赛砍树

题目分析:

在这里插入图片描述
给一个mxn的矩阵,

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

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

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

在这里插入图片描述

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

算法原理:

当我们把题意搞清楚,我们知道砍树不能随便砍,必须按照从底到高顺序来砍,因此我们必须先想办法把下标中的树先按照从低到高排下序,然后从(0,0)开始砍。此时这个问题就转化为,1->2 只要知道1->2最短距离不就可以了吗,然后就可以砍2号树。在然后从 2->4,只要知道2->4最短距离然后就可以砍4号树。。。。 这不就变成了若干个迷宫问题了吗。然后把所有最短距离加起来就行了。

在这里插入图片描述

那如何先对树进行一下排序把砍树的顺序找到呢?
可以先用数组把所有待砍树的下标保存起来,然后根据下标所对应的值对下标进行排序。

class Solution {int m,n;
public:int cutOffTree(vector<vector<int>>& f) {m = f.size(), n = f[0].size();// 1. 准备⼯作:找出砍树的顺序vector<pair<int, int>> trees;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(f[i][j] > 1) trees.push_back({i, j});sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const pair<int, int>& p2){return f[p1.first][p1.second] < f[p2.first][p2.second];});// 2. 按照顺序砍树int bx = 0, by = 0;int ret = 0;for(auto& [a, b] : trees){int step = bfs(f, bx, by, a, b);if(step == -1) return -1;ret += step;bx = a, by = b;}return ret;}bool vis[51][51];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey){if(bx == ex && by == ey) return 0;queue<pair<int, int>> q;memset(vis, 0, sizeof vis); // 清空之前的数据q.push({bx, by});vis[bx][by] = true;int step = 0;while(q.size()){step++;int sz = q.size();while(sz--){auto [a, b] = q.front();q.pop();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 && f[x][y] && !vis[x][y]){if(x == ex && y == ey) return step;q.push({x, y});vis[x][y] = true;}}}}return -1;}

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

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

相关文章

Day17 枚举、typedef、位运算、堆空间的学习

目录 枚举 typedef 位运算 堆上的空间 枚举 一个一个列举出来&#xff0c;是指将变量的值一一列举出来&#xff0c;变量的值只限于列举出来的值的范围内。 作用&#xff1a; 1、为了提高代码的可读性 2、提高代码的安全性 枚举类型 基本语法&#xff1a; enum 枚举名 { …

根据toml编译生成whl

1、安装build pip install build如果已经安装build, 那就执行一下升级命令 python3 -m pip install --upgrade build2、在pyproject.toml所在的文件夹那一层执行 # -w:生成whl文件 -v:显示python编译过程 python3 -m build -w -v2.1 当出现以下输出&#xff0c;需要耐心等待…

Java 集成测试详解及示例

通过综合指南探索 Java 集成测试的世界。了解工具、流程和最佳实践&#xff0c;并辅以实际示例。 随着软件系统变得越来越大、越来越复杂&#xff0c;组件和服务以错综复杂的方式交互&#xff0c;集成测试已变得不可或缺。通过验证所有组件和模块在组合时是否正常工作&#xff…

入门岛2-python实现wordcount并进行云端debug

书生大模型学习 任务&#xff1a; 1.实现一个wordcount函数&#xff0c;统计英文字符串中每个单词出现的次数。返回一个字典&#xff0c;key为单词&#xff0c;value为对应单词出现的次数。 2.Vscode连接InternStudio debug TIPS&#xff1a;记得先去掉标点符号,然后把每个单词…

Mybatis学习-day19

Mybatis学习-day19 1. resultMap resultMap 是 MyBatis 中最复杂的元素&#xff0c;主要用于解决实体类属性名与数据库表中字段名不一致的情况&#xff0c;可以将查询结果映射成实体对象。 <resultMap id"staffAndDep" type"com.easy.bean.Staff">…

解決android Studio在导入已有的工程 build 时出现的错误

最近在学习andriod方面的知识&#xff0c;第一次使用android Studio导入别人的项目&#xff0c;从导入到build出现了几个问题&#xff0c;在这里记录以下解决过程。 SDK location not found 如下图报错所示&#xff0c;看网上教程有的说是SDK未安装&#xff0c;这里我是明确自…

两个AI关小黑屋:Llama3.1把Claude Opus聊自闭了

把Llama 3.1 405B和Claude 3超大杯Opus双双送进小黑屋&#xff0c;你猜怎么着—— Llama把Claude整得精神崩溃了&#xff0c;Claude明确拒绝继续聊天&#xff0c;还要再被Llama PUA的那种。 在一场AI和AI对话的安全词模拟实验中&#xff0c;X上的这位人类监督者记录下了一出好…

【HarmonyOS NEXT星河版开发学习】小型测试案例12-点赞案例

个人主页→VON 收录专栏→鸿蒙开发小型案例总结​​​​​ 基础语法部分会发布于github 和 gitee上面&#xff08;暂未发布&#xff09; 前言 本案例主要运用了交互点击事件和基础的算术运算符的应用&#xff0c;难度并不大&#xff0c;卡片的制作相对来说并不是太难&#xff0…

机器学习/深度学习——模型的欠拟合和过拟合,正则化方法详解

机器学习/深度学习——模型的欠拟合和过拟合&#xff0c;正则化方法 详解 搭配以下文章进行学习&#xff1a; 卷积神经网络&#xff1a; 深度学习——卷积神经网络&#xff08;convolutional neural network&#xff09;CNN详解&#xff08;一&#xff09;——概述. 步骤清晰…

深度解析HAProxy:构建高可用负载均衡的终极指南

目录 haproxy配置文件组成 实验环境 haproxy安装 haproxy的配置文件说明 全局配置段global 多进程和多线程配置 代理配置段proxies server配置说明 实验相关配置 测试效果&#xff1a; haproxy的状态页 socat命令 socat命令的一些常用示例 HAProxy的调度算法 静…

网鼎杯-2018-Web-Unfinish

先尝试万能注入&#xff1a; 如果万能注入缺少符号&#xff0c;如果加符又进不去&#xff0c;那我们尝试扫描文件,然后发现有一个register.php的文件&#xff0c;应该是注册页面&#xff0c;我们去打开 知道存储的文件&#xff0c;并利用状态码进行过滤 我们注册的用户名就是aa…

【Redis 进阶】集群(重点理解流程和原理)

一、基本概念 前面学习的哨兵模式&#xff0c;提高了系统的可用性。但是真正用来存储数据的还是 master 和 slave 节点&#xff0c;所有的数据都需要存储在单个 master 和 slave 节点中。如果数据量很大&#xff0c;接近超出了 master / slave 所在机器的物理内存&#xff0c…

【数据结构详解】——冒泡排序(动图详解)

目录 &#x1f552; 1. 冒泡排序 &#x1f552; 1. 冒泡排序 &#x1f4a1; 算法思想&#xff1a;两两比较相邻记录的关键字&#xff0c;如果反序则交换&#xff0c;直到没有反序的记录为止。一共进行n-1趟这样的交换将可以把所有的元素排好。 代码实现如下&#xff1a; voi…

uniapp点击图片预览,关闭预览图片后自动触发onshow生命周期,怎么解决?

第一&#xff0c;页面的数据会实时更新&#xff0c;所以接口请求需要在onshow中&#xff0c;变量figh初始为true&#xff0c;数据列表信息可直接调用获取 当点击查看图片时改变&#xff0c;变量figh为false&#xff0c;此时onshow里面的this.postlist()不触发。 此时&#xff0…

国产大模型市场遇冷:挑战与机遇并存,一般人学大模型,我劝你算了吧

前阵子&#xff0c;大模型赛道非常热闹&#xff0c;360、字节、KIMI、知乎等公司纷纷召开发布会&#xff0c;推出自己独具特色的新产品&#xff0c;一时间引发市场的不少想象和讨论。在看似百花齐放、万紫千红的同时&#xff0c;K哥也观察到了一些不好的迹象&#xff0c;这些“…

【软件测试】功能测试理论基础

目录 项目的测试流程&#x1f3f4; 需求评审 评审形式 测试人员在需求评审中职责 测试计划与方案 测试计划 问题 测试方案&#x1f3f4; 测试计划与方案的对比 功能测试设计&#x1f3f4; 测试设计的步骤 项目的测试流程&#x1f3f4; 作用&#xff1a; 有序有效开展…

力扣Hot100-994腐烂的橘子

中等 在给定的 m x n 网格 grid 中&#xff0c;每个单元格可以有以下三个值之一&#xff1a; 值 0 代表空单元格&#xff1b;值 1 代表新鲜橘子&#xff1b;值 2 代表腐烂的橘子。 每分钟&#xff0c;腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格…

MiniCPM-V: A GPT-4V Level MLLM on Your Phone 手机上的 GPT-4V 级多模态大模型

GitHub - OpenBMB/MiniCPM-V: MiniCPM-V 2.6: A GPT-4V Level MLLM for Single Image, Multi Image and Video on Your Phone 2408.01800 (arxiv.org) 目录 Introduction Model Architecture Training End-side Deployment MiniCPM-V是一种高效的多模态大型语言模型&…

cad文字转arcgis注记

cad中文字转为arcgis注记&#xff0c;步骤如下&#xff1a; 1、将dwg文件下annotation文件加到图层中 2、文件点击右键&#xff0c;转换地理数据库注记 3、 导入默认地理数据库中&#xff0c;或自己新建地理数据库&#xff0c;起个文件名、点确定&#xff08;注意&#xff1a…

手机CPU性能天梯图(2024年8月),含安兔兔/GB6/3DMark跑分

原文地址&#xff08;高清无水印原图/持续更新/含榜单出处链接&#xff09;&#xff1a; 2024年8月手机处理器天梯图 2024年8月1日更新日志&#xff1a;由于近期并未有新处理器发布&#xff0c;故只做常规更新&#xff1b;移除鲁大师天梯图&#xff1b;补充其它天梯图数量。 -…