BFS——认识广度优先搜索 2023年03月05日 算法·第一弹

wangyuzhe 蒟蒻 2023-03-05 16:36:46 0

欢迎来到广度优先的世界

广度优先算法(Breadth-First Search),同广度优先搜索,又称作宽度优先搜索,或横向优先搜索,简称BFS

风和日丽的一天,一位叫小明的同学被困在了迷宫里,现在你在迷宫的左上角,你希望用最短的路径把他救出来,你会怎么做?

由于我们不知道小明的位置,所以只能一条一条的试,我们可以从上下左右走,而每到一个地方也可以上下左右走,但是绝不走重复路也不碰到墙壁,就像下面这张图

这样,只要我们不被迷宫困住,就一定可以找到小明

那么我们该如何实现广度优先呢?

这里我们先来认识一种数据结构:队列

队列的特性是先进先出(比如说在排队时(没人插队),最先进入队伍的最先出去),我们发现,广度优先恰恰也可以用先进先出的方式实现

可以先把第一个坐标加入队列,遍历上下左右4个方向,如果我可以到达,就把它压入队列

然后while(!q.empty()),只要队列不空,那就继续遍历

这里解释一下STL里队列里的成员函数:

queue <int> q;//创建一个变量名为q,类型为int的队列,注意,类型可以是结构体等等
q.empty()//返回值为true或false,表示队列是否为空
q.size()//队列里还有的元素数量
q.front()//返回队头
q.pop()//压出队头
q.push(x)//压入x

最后,请大家尝试用所学的知识完成:#252. Lake Counting,相信聪明的你一定能做出来

{{ vote && vote.total.up }}