ACM | BFS 广度优先算法

Slide 1

ACM程序设计

Slide 2

预备知识

队列特点： 1、先进先出(FIFO) 2、从队头删除元素 3、在队尾加入元素

常见操作：判断队列是否为空查询队列大小访问队首元素访问队尾元素加入元素删除元素

Slide 3

STL中队列的基本用法

创建队列对象：queue<元素类型> 队列名; 队列添加元素：队列名.push(元素名); 去掉队首元素：队列名.pop(); 访问队首元素：队列名.front(); 访问队尾元素：队列名.back(); 判断是否为空：队列名.empty(); 返回队列大小：队列名.size();

Slide 4

STL实例介绍

int a,b,c,d;
queue<int> q;
q.push(1);  q.push(3); q.push(4);  q.pop();
a=q.front();
b=q.back();
c=q.size();
d=q.empty();
cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;

Slide 5

第七讲

宽度优先搜索（BFS）

Slide 6

例1

输入一棵二叉树，如何对该二叉树进行层次遍历？所谓“层次遍历”就是从上到下，从左到右的顺序进行遍历。例如，右边的树层次遍历的结果是？

5 1 7 2 4 6 3

Slide 7

算法思想：维护一个队列，用于存放节点的信息。当访问到一个节点的时候，先访问该节点，然后将该节点的左右儿子分别入对列。

ccbl(int root)
	queue<int> Q ;创建一个队列
	Q.push(root) ;将根节点入队列
	while(队列不为空){
	获得队首元素               //这一行和下一行能交换吗？
	将队首元素出队
	输出当前节点的值
	如果该节点的左儿子不为空，将左儿子加入到队列中
	如果该节点的右儿子不为空，将右儿子加入到队列中
  }

树的层次遍历

Slide 8

图的BFS示意图

Slide 9

例2

有一个奇怪的电梯，他可以停在任何一层，并且在每个楼层有一个Ki（0 <= Ki <= N）。电梯只有两个按钮：上、下。当你在第i层，如果你按下“UP”按钮，你将上升Ki层，也就是说，你将会到达第i+Ki层，如果你按下“DOWN”按钮，你会下降 Ki层，即您将前往第i-Ki层。当然，电梯不能高于N，也不能低于1。例如，有5层的建筑物，并且k1=3，k2=3，k3=1，k4=2，k5=5。从1楼开始，你可以按下“UP”按钮，你会到4楼，但如果你按下“DOWN”按钮，电梯不做处理，因为它不能下到-2楼。问：当你在A楼而想去B楼时，至少须按下“UP”或“DOWN”按钮多少次？其中，1 <= N,A,B <= 200

Slide 10

例2

能看出这是一个搜索题吗？能否根据样例画出对应的状态转移图？ 5 1 5 3 3 1 2 5 通过这个题目能否总结出：BFS最适合哪一类的求解？

Slide 11

例2

#include<bits/stdc++.h>
using namespace std;
int N,Start,End;
int a[202];
int vis[202];
struct pos
{   int level;    //含义？
    int steps;    //含义？
};
void bfs();


int main()
{   while(scanf("%d",&N)==1)
    {   if(N == 0) break;
        scanf("%d%d",&Start,&End);
        for(int i = 1; i <= N; i++)
        {   scanf("%d",&a[i]);
            vis[i] = 0;
        }
        bfs();
    }
    return 0;
}

Slide 12

void bfs()
{   pos cur,nex;
    cur.level = Start;
    cur.steps = 0;
    queue<pos>qu;
    qu.push(cur);
    vis[Start] = 1;
    while(!qu.empty())
    {   cur = qu.front();
        qu.pop();
        if(cur.level == End)
        {   printf("%d\n",cur.steps);
            return;
        }
        nex.level=cur.level + a[cur.level];
        nex.steps = cur.steps + 1;
        

	if(nex.level <= N)
        {   if(vis[nex.level] == 0)
            {   vis[nex.level] = 1;
                qu.push(nex);     }
        }
        nex.level= cur.level - a[cur.level];
        nex.steps = cur.steps + 1;
        if(nex.level >= 1)
        {   if(vis[nex.level] == 0)
            {   vis[nex.level] = 1;
                qu.push(nex);      }
        }
    }
    printf("-1\n");
    return;
}

Slide 13

例3

题目描述：每当刘一丁买了可乐，刘二丁就要求和他一起分享，而且一定要喝的和刘一丁一样多。但刘一丁的手中只有两个杯子，它们的容量分别是N和M毫升,可乐的体积为S（S<101）毫升(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。

如果能平分，请输出倒可乐的最少次数，如果不能，请输出"NO"。

Input

7 4 3
4 1 3
0 0 0

Output

NO
3

Slide 14

啊，这连图都没有，也能搜索？！！如何定义节点信息（状态）？三杯水量 + 当前状态最少倒水次数有了状态如何转移呢? 有了状态、有了转移(边),是否就能进行搜索了?！我们称之为——“隐式图” 如何优化（剪枝）？已经访问的节点不再访问（做标记）

例3

Slide 15

状态转移规则（倒水规则）：如果i水杯内水的容量大于j水杯内倒满所需的容量x，则——i水杯倒水后的容量为：i-x,j水杯倒水后容量为:j+x 如果i水杯内水的容量小于j水杯内倒满所需的容量x，则——i水杯倒水后的容量为：0,j水杯倒水后容量为:j+x 每操作一次，最少倒水次数+1

例3

Slide 16

例4

题目大意：给定起始位置a和目标位置b，请计算从a到b路上骑士移动的最少次数。注：骑士即象棋中的马，走日字。 Sample Input

a1 h8

Sample Output

To get from a1 to h8 takes 6 knight moves.

Slide 17

跳马规则

在2×3的矩形里

Slide 18

例如：从a1到e4

当目标出现在所扩展出的结点里，结果就找到了。

To get from a1 to e4 takes 3 knight moves.

例4

Slide 19

从初始状态S开始，利用规则，生成所有可能的状态，构成树的下一层节点。检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别依次利用规则,生成再下一层的所有状态节点。对新一层的所有状态节点继续检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开，直到出现目标状态为止。

BFS基本思想：

Slide 20

BFS算法（伪代码）

Node bfs(node source , node target){
	memset(visit , 0 , sizeof(visit)) ;
	queue<node> Q ;
	Q.push(source) ;
	visit[source] = 1 ;
	while(!Q.empty()){
		Node a = Q.front();
		Q.pop() ;
		if(a==target)  	{   return a ;	}
		for(对于a所有的后继节点 b)
			if(visit[b]){  continue ;	}
			Q.push(b) ;
			visit[b] = 1 ;   //剪枝，保证节点只进队列一次
	}
	return NULL ;
}

Slide 21

预备知识-优先队列（priority_queue）

特点： 1、在队尾加入元素 2、从队头删除元素 3、每次取出的是具有最高优先权的元素（不一定先进先出）

常见操作：判断队列是否为空查询队列大小返回优先权最高的元素加入元素删除元素

Slide 22

STL中优先队列的基本用法

创建队列对象：priority_queue<元素类型> 队列名; 队列添加元素：队列名.push(元素名); 去掉第一个元素：队列名.pop(); 判断是否为空：队列名.empty(); 返回队列大小：队列名.size(); 访问最优元素：队列名.top();

Slide 23

优先队列实例1：

#include<bits/stdc++.h>
using namespace std;
int main() 
{    priority_queue<int> q; 
     int t, a=2, b=5, c=3;
     q.push(a);   q.push(b);   q.push(c); 
     while (!q.empty()) 
     {   t = q.top(); 
         q.pop(); 
         cout << t <<  endl; 
     } 
     return 0; 
}

运行结果：

5
3
2

Slide 24

优先队列实例2：

struct T 
{  int x, y, z; 
   friend bool operator < (const T &t1, const T &t2) 
   {  	if (t1.z!= t2.z) return t1.z > t2.z;  
		else if(t1.y!=t2.y) return t1.y<t2.y;
		else return t1.x>t2.x;
   }      
}t; 
int main() 
{    priority_queue<T> q; 
     T a={4,4,3}, b={2,2,5},  c={1,2,5}, d={2,1,5};
     q.push(a);   q.push(b);  q.push(c); q.push(d);
     while (!q.empty()) 
     {   t = q.top();     q.pop(); 
         cout << t.x << " " << t.y << " " << t.z <<  endl;     }
      return 0; 
}

Slide 25

例5

题目大意：丁爸被火星人抓走，关在一个\(N * M\)矩形的监狱（监狱里有墙壁、道路和警卫队）。丁爸的学生想拯救他（到达丁爸停留的位置即视为成功）。拯救过程中若遇到警卫，则必须干掉。假设每次向上，向下，向右，向左移动需要1个单位时间，杀死一个守卫额外需要1个单位时间。请计算：拯救丁爸需要的最短时间。（每次只能上，下，左，右移动到边界内的邻居网格。）

Sample Input

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

Sample Output

Slide 26

如果使用传统的BFS，局限性在哪里？出队元素所记忆的时间并不是层次递增的... 希望的效果？让因为遇到士兵而多花时间的结点在队列中向后推迟一层出队实现方法：优先队列——根据时间进行优先性选择，每次出队当前队列中记录时间最少的元素思考：前来拯救的学生有多个，如何方便处理？

要点分析：

ACM | BFS 广度优先算法

https://acm.nanyan.cc/posts/4740.html

作者

nanyan

发布于

2023年11月23日

许可协议

PTA | 指针相关题目及解析上一篇

ACM | 背包算法下一篇