本文主要是介绍BFS 解决最短路问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
例题一
解法(bfs 求最短路):
算法思路:
利⽤层序遍历来解决迷宫问题,是最经典的做法。我们可以从起点开始层序遍历,并且在遍历的过程中记录当前遍历的层数。这样就能在找到出⼝的时候,得到起点到出⼝的最短距离。
![](https://img-blog.csdnimg.cn/direct/1dc7a31648214a4cabe98ac6184cd09f.png)
例题二
![](https://img-blog.csdnimg.cn/direct/f41c115eb5af47f58f0a50bb281c1e2b.png)
解法:
算法思路:
如果将「每次字符串的变换」抽象成图中的「两个顶点和⼀条边」的话,问题就变成了「边权为 1
的最短路问题」。因此,从起始的字符串开始,来⼀次 bfs 即可。
![](https://img-blog.csdnimg.cn/direct/65a463729b5b42fda2572f491169f448.png)
例题三
解法:
跟上题⼀样~
![](https://img-blog.csdnimg.cn/direct/f4ea23a8235e4882b3af24a259d7d996.png)
例题四
解法:
算法思路:
a. 先找出砍树的顺序;
b. 然后按照砍树的顺序,⼀个⼀个的⽤ bfs 求出最短路即可。
![](https://img-blog.csdnimg.cn/direct/c974c0950fdf4bc78f4786b7c9a43c15.png)
这篇关于BFS 解决最短路问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!