BFS 即广度优先搜索算法（Breadth-First-Search）
广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法
简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。 如果所有节点均被访问，则算法中止。 BFS同样属于盲目搜索。
一般用队列数据结构来辅助实现BFS算法。
时间复杂度：邻接表的时候是O(|V| + |E|)。其中 |V| 是节点的数目，|E| 是图中边的数目。
如下图，其广度优先算法的遍历顺序为：1->2->3->4->5->6->7->8
算法步骤：
- 首先将根节点放入队列中。
- 从队列中取出第一个节点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入队列中。
- 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
- 重复步骤2。
更具体点的:
广度优先搜索算法如下：（用QUEUE）队列
(1) 把初始节点S0放入Open表中；
(2) 如果Open表为空，则问题无解，失败退出；
(3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；
(4) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；
(5) 若节点n不可扩展，则转第(2)步；
(6) 扩展节点n，将其不在Closed表和Open表中的子节点 (判重) 放入Open表的尾部，并为每一个子节点设置指向父节点的指针(或记录节点的层次），然后转第(2)步。
入门：抓住那头牛
题目：
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
- 1、从X移动到X-1或X+1，每次移动花费一分钟
- 2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
bfs解：
假设农夫起始位于点3，牛位于5 ，N=3,K=5，最右边是6。 如何搜索到一条走到5的路径？
策略：广度优先搜索：
给节点分层。起点是第0层。从起点最少需n步就能到达的点属于第n层。
第1层：2,4,6
第2层：1,5
第3层：0
依层次顺序，从小到大扩展节点。把层次低的点全部扩展出来后，才会扩展层次高的点。
搜索过程（节点扩展过程）：
3
2 4 6
1 5
问题解决。
扩展时，不能扩展出已经走过的节点(要判重） 。
优点：
可确保找到最优解
缺点：
但是因扩展出来的节点较多，且多数节点都需要保存，因此需要的存储空间较大。
用队列存节点。
由上述bfs算法步骤可得：
- 首先先将初始 节点3 放入Open队列里。
- 然后从Open队列里取出 节点3 并放入Closed队列里。然后将节点3下一层的 节点2，4，6 依次放入Open队列里。
- 然后从Open队列里取出 节点2 并放入Closed队列里。然后将节点2下一层的节点1放入Open队列里。
- 然后从Open队列里取出 节点4 并放入Closed队列里。然后将节点4下一层的节点5放入Open队列里。
- 然后从Open队列里取出 节点6 并放入Closed队列里。然后将节点6下一层的没有节点可以放入Open队列里，则跳过进行下一步。
- 然后从Open队列里取出 节点1 并放入Closed队列里。然后将节点1下一层的节点0可以放入Open队列里。
- 然后从Open队列里取出 节点5 并放入Closed队列里。目标节点5出队列，问题解决！
代码实现：
// c++
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int N,K;
const int MAXN = 100000;
int visited[MAXN+10]; //判重标记,visited[i] = true表示i已经扩展过
struct Step{
int x; //位置
int steps; //到达x所需的步数
Step(int xx,int s):x(xx),steps(s) { }
};
queue<Step> q; //队列,即Open表
int main() {
cin >> N >> K;
memset(visited,0,sizeof(visited));
q.push(Step(N,0));
visited[N] = 1;
while(!q.empty()) {
Step s = q.front();
if( s.x == K ) { //找到目标
cout << s.steps <<endl;
return 0;
}
else {
if( s.x - 1 >= 0 && !visited[s.x-1] ) {
q.push(Step(s.x-1,s.steps+1));
visited[s.x-1] = 1;
}
if( s.x + 1 <= MAXN && !visited[s.x+1] ) {
q.push(Step(s.x+1,s.steps+1));
visited[s.x+1] = 1;
}
if( s.x * 2 <= MAXN &&!visited[s.x*2] ) {
q.push(Step(s.x*2,s.steps+1));
visited[s.x*2] = 1;
}
q.pop();
}
}
return 0;
}
程序演示：
参考学习于：
https://www.coursera.org/learn/suanfa-jichu
原文链接https://blog.csdn.net/weixin_43347550/article/details/105817615
转载：https://blog.csdn.net/weixin_43347550/article/details/105817615