问题引入
对于每一个问题,都会有相应的解,在之前的学习中求解的过程,都是以一条条线的形式产生可能解进行筛选验证是否正确。本章节我们来考虑另外一种思路,类似于洪水爆发,从一个源头开始逐渐蔓延开来,直到所有可达的区域都被洪水淹没,所以我们也把这种算法称之为洪泛法。洪泛法会以面的形式同步扩展更多的可行解,进而拓展广度。
单纯的文字描述无法很好的帮助同学们理解上面的说法,认真学完本章节的内容,相信同学们可以很好的理解广度优先搜索算法。
广度优先搜索算法
广度优先搜索(英文:Breadth-First Search,简称BFS)的思路是会优先考虑每种状态和初始状态的距离,也就是与初始状态越接近的情况就会优先考虑。再具体一点:每个时刻(阶段)要做的事情就是从上个时刻(阶段)每个状态扩展出新的状态。
广度优先搜索使用队列或数组模拟实现:先将初始状态加入到空的队列中,然后每次取出队首,找出队首所能扩展到的状态,再将其压入队列;如此反复,直到队列为空。这样就能保证一个状态在被访问时一定是采用的最短路径。
例如洪水从A点爆发(如下左图所示),在每个点都沿着上下左右的方向淹没相邻的点,那么最终整个地图淹没的时间如下右图所示。
把扩展的情况按层次划分,可以得到下图:
可以发现,广搜更适合解决从起始点到目标点的最短路问题。一般来说,题目描述的是求解最少多少步、最短距离、最短时间这种问题可以考虑用广搜求解。
广搜的模板:
本章节例题将以两种解法进行全面充分的学习广度优先搜索的实现方式,增强同学们的理解。
1. 队列(推荐写法)
2. 数组模拟队列(重点学习)
全局状态变量
void bfs(当前结点)
{
当前结点入队
while (队列不为空)
{
取出队首节点作为当前结点
if (当前节点是目标结点)
进行相应处理(输出当前解、更新最优解、退出返回等)
for (由当前结点衍生新结点)
{
if (新结点没有访问过 && 需要访问)
{
新结点入队
}
}
//队首结点已衍生完毕,没有用处了
队首结点出队
}
}
int main() {
...;
bfs(初始结点);
...;
}
广搜在搜索过程中形象化的运行过程: