广度优先搜索算法代码（广度优先搜索原理）



中国年已经过完了，伙伴们该学习起来啦！！！

今天带来了广度优先搜索的原理解析，广度优先搜索（BFS）是一个使用广泛的基础算法，掌握了这种算法会让很多之前没有思路的算法也会题迎刃而解！！！

BFS算法在竞赛时被用于寻找最短路程的题目，我们在理解它的原理时可以把他理解为一个“树”，这个算法就是计算“树”的每一个“孩子”的过程， 例如下面这个题

    请找A到F的最短距离

现在我们将他转换成树来求解：

准换为树之后可以轻易的发现在树的第四层（层数从0开始）第一次出现了我们需要的结果“F”，那么4就是我们需要的最终结果。我们的代码就是创建这棵树并计算树的各个孩子的过程，因为寻找的是最短路程我们在写代码的时候需要舍弃已经计算过的点，我们可以通过构建一个数组来标注那些点已经被经过，为了实现逐层计算我们可以通过创建一个队列来进行每一层的计算。

问题描述

　　农夫John的一头牛逃跑了，他想要将逃跑的牛找回来。现假设农夫John和牛的位置都在一条直线上，农夫John的初始位置为N（0≤N≤100,000），牛的初始位置为K（0≤K≤100,000）。农夫John有两种移动方式：行走和传送。
　　行走：农夫John可以从当前位置X移动到X-1或X+1，花费时间1分钟。
　　传送：农夫John可以从当前位置X传送到2×X，花费时间1分钟。
　　现假设牛逃跑后的位置一直保持不变，请编写一个程序，计算农夫John找到牛的最短时间。

输入格式

　　输入N和K（中间用一个空格间隔）。

输出格式

　　输出最短的寻找时间，单位分钟。

样例输入

5 17

样例输出

4

样例中农夫的移动路径为5-10-9-18-17，花费时间为4分钟。

这个题我们可以理解为从N位置到达K位置的最短距离，但是我们这次构建树的分支就有3种，分别是“左”、“右”、“传送”。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/22010.html