BFS
预备知识:队列
特点:先进先出(FIFO),队头删除元素,队尾插入元素
基本用法:见文件
对于bfs,我们需要一层一层遍历所有节点,那么相邻节点的访问顺序该如何确定?因此我们需要队列去存储和操作,需要使先遍历到的结点先被存储,直到当前层都被存储之后,按存储的先后顺序,先被存储的节点也会先被取出,继续遍历子节点。符合队列的FIFO特点
基本思想
解决问题
- 从A出发是否存在到达B的路径(DFS也行)
- 从A出发到达B的最短路径(DFS+剪枝也行,容易TLE)
基本思想
从初始状态s(图上某个节点出发)开始利用规律,生成所有可能状态,构成树的下一层节点
检查是否出现目标状态g,若未出现则对该层所有状态节点分别利用规则,生成在下一层的所有状态节点
对新一层继续检查重复上述操作直到出现目标状态
注意:BFS实际上是传回经过边数最少的解,因此对于所有边长度(边权)相同的情况,此时就一定是从根节点到目标节点最短的路径,BFS先找到的就一定是最短的,但如果是加权边,BFS传回的就不一定最短了。对于加权路径的最短路,我们使用Dijkstra算法求解。
基本步骤
- 起始:将起点(根节点)放入队列中
- 扩散:从队列中取出队头结点,将其相邻节点放入队列,不断重复
- 终止:当队列为空是,说明遍历完了所有节点
空间复杂度
板子
1 | Node bfs(node source, node target){ |
例:二叉树的层次遍历-queue的实现解释
层次遍历:从上到下,从左到右进行遍历
思想
维护队列,用于存放节点信息,当访问到一个节点时,先访问该节点,然后将该节点的左右儿子分别入队列
伪代码
1
2
3
4
5
6
7
8
9
10bfs(int root){
queue<int> q;
q.push(root);
while q不为空:
获得队首元素
队首元素出队
输出当前节点值
if 该节点左儿子不为空:将左儿子加入队列
else if 该节点右儿子不为空:将右儿子加入队列
}例:对于一个层次遍历:5172463的树
队列q:
放入root节点:q:5
队列空否? 不空,输出5并删除,q:
有孩子否?有,放入5的左右孩子1 7,q:1 7
队列空否? 不空,输出1并删除,q:7
有孩子否?有,放入1的左右孩子2 4,q:7 2 4
队列空否? 不空,输出7并删除,q:2 4
有孩子否?有,放入7的左右孩子6 3,q:2 4 6 3
队列空否? 不空,输出2并删除,q:4 6 3
有孩子否?无,继续,q:4 6 3
剩下三个相同 q:6 3 q:6 q:
例:图的bfs
- 图与树类似,但图任何两点间都可以有边,故方法相似
- 但图没有层次关系,访问的是某点的邻接点,若一个点已经访问过就没必要在访问了:如B的邻接点AEC,若想要放进去子节点,则AE没有必要再入队列
- 步骤:放入起始节点,循环判断队列空不空,若不空则放入相邻节点
- BFS最适合的:寻找最少几步能达到目标(特殊的最短路问题)
例:奇怪的电梯
奇怪的电梯
题目描述
呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第
层楼( )上有一个数字 ( )。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如: 代表了 ( , ,……),从 楼开始。在 楼,按“上”可以到 楼,按“下”是不起作用的,因为没有 楼。那么,从 楼到 楼至少要按几次按钮呢? 输入格式
共二行。
第一行为三个用空格隔开的正整数,表示
( , )。 第二行为
个用空格隔开的非负整数,表示 。 输出格式
一行,即最少按键次数,若无法到达,则输出
-1。样例 #1
样例输入 #1
1
2 >5 1 5
>3 3 1 2 5样例输出 #1
1 >3提示
对于
的数据, , , 。 本题共
个测试点,前 个每个测试点 分,最后一个测试点 分。
如样例:从1楼到5楼,可以从1->4->2->5 按三次按钮
搜索状态:从一个状态出发,根据题目不断转移状态直到到达目标状态,对实例如图:
如题:从1楼开始
1楼只能往上到4楼,四楼只能往下到2楼,二楼只能往上到五楼
所以这是一个典型的二叉树,起始状态为起点,目标状态为样例输入的楼层
- 记录按按钮次数:使用结构体将楼层和按钮次数封装
代码
1 |
|
例:非常可乐
大家一定觉的运动以后喝可乐是一件很惬意的事情,但是seeyou却不这么认为。因为每次当seeyou买了可乐以后,阿牛就要求和seeyou一起分享这一瓶可乐,而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子,它们的容量分别是N 毫升和M 毫升 可乐的体积为S (S<101)毫升 (正好装满一瓶) ,它们三个之间可以相互倒可乐 (都是没有刻度的,且 S==N+M,101>S>0,N>0,M>0) 。聪明的ACMER你们说他们能平分吗?如果能请输出倒可乐的最少的次数,如果不能输出”NO”。
Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量,以”0 0 0”结束。
Output
如果能平分的话请输出最少要倒的次数,否则输出”NO”。
Sample
输入
1
2
3 7 4 3
4 1 3
0 0 0输出
1
2
3 No
3
看似找不出图的一个搜索:只要根据信息能表示出状态,且状态能根据规则进行转移就可以用搜索
定义节点状态:三杯水量+当前状态最少倒水次数
状态转移如图(以4 1 3为例,最后一位是次数):
- 目标状态:达到两个量相等一个量为0
- 倒水要求:只能倒满或者倒空
- 这种题目称为隐式图
- 如何剪枝:访问过的节点不在访问
例:离开中山路
离开中山路
题目背景
《爱与愁的故事第三弹·shopping》最终章。
题目描述
爱与愁大神买完东西后,打算坐车离开中山路。现在爱与愁大神在
处,车站在 处。现在给出一个 的地图, 表示马路, 表示店铺(不能从店铺穿过),爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间,他要求最短到达目的地距离(每两个相邻坐标间距离为 )。你能帮他解决吗? 输入格式
第
行包含一个数 。 第
行到第 行:整个地图描述( 表示马路, 表示店铺,注意两个数之间没有空格)。 第
行:四个数 。 输出格式
只有
行,即最短到达目的地距离。 样例 #1
样例输入 #1
1
2
3
4
5 >3
>001
>101
>100
>1 1 3 3样例输出 #1
1 >4提示
对于
数据,满足 。 对于
数据,满足 。
可以使用方向数组来转移状态:
对于网格地图,可以定义一个二维数组
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};则遍历四个方向可以
1
2
3
4for (int i = 0; i <4; i++){
x2 = x1+dir[i][0];
y2 = y1+dir[i][1];
}坑点:输入中间无空格,是一起输入的,需要用字符串转换为某行某列(ascii转化,
char - 'a')存入数组
代码
1 | /*迷宫问题如果要求最短路径(权值为1)相关,则可以选用bfs |