欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 房产 > 家装 > 优选算法系列(7.BFS 解决最短路问题)

优选算法系列(7.BFS 解决最短路问题)

2025/4/19 3:49:33 来源:https://blog.csdn.net/2301_79903399/article/details/147258167  浏览:    关键词:优选算法系列(7.BFS 解决最短路问题)

简介:

先走到A,之后弹出A再把A能走到的地方加进去向外扩展把队列里面的元素(B,C)弹出来,再把B,C能到的地方入队列

一直这样那么最短路程就是扩展的层数。

迷宫中离入口最近的出口(medium):

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

算法:

利用层序遍历来解决迷宫问题,是最经典的做法。

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

最小基因变化(medium):

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

算法:

如果将「每次字符串的变换」抽象成图中的「两个顶点和⼀条边」的话,问题就变成了「边权为 1的最短路问题」。
因此,从起始的字符串开始,来⼀次 bfs 即可。

 

单词接龙(hard):

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

算法:

跟上题⼀样~

为高尔夫比赛砍树(hard):

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

算法:

  1. 先找出砍树的顺序;
  2. 然后按照砍树的顺序,⼀个⼀个的用bfs 求出最短路即可。

 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词