算法竞赛专题解析│搜索基础：算法竞赛专题解析│搜索基

原标题：算法竞赛专题解析│搜索基础

文章图片
本篇介绍了BFS和DFS的概念、性质、模板代码。
*本文内容由罗勇军老师提供。
01
搜索简介
搜索，就是查找解空间，它是“暴力法”算法思想的具体实现。
暴力法（Bruteforce ，又译为蛮力法）：把所有可能的情况都罗列出来，然后逐一检查，从中找到答案。这种方法简单、直接，不玩花样，利用了计算机强大的计算能力。
搜索是“通用”的方法。一个问题，如果比较难，那么先尝试一下搜索，或许能启发出更好的算法。竞赛的时候，遇到不会的难题，如果有时间，就用搜索提交一下，说不定判题数据很弱，就通过了。
搜索的思路很简单，但是操作起来也并不容易。一般有以下操作：
（1）找到所有可能的数据，并且用数据结构表示和存储。常用的搜索算法是BFS和DFS 。
（2）优化。尽量多地排除不符合条件的数据，以减少搜索的空间。
（3）用某个算法快速检索这些数据。
02
搜索算法的基本思路
搜索的基本算法是：深度优先搜索（DFS,Depth-FirstSearch）、宽度优先搜索（BFS,Breadth-FirstSearch ，或称为广度优先搜索）。
这两个算法的思想，用老鼠走迷宫的例子来说明，又形象又透彻。
迷宫内部的路错综复杂，老鼠从入口进去后，怎么才能找到出口？有两种不同的方法：
（1）一只老鼠走迷宫。它在每个路口，都选择先走右边（当然，选择先走左边也可以），能走多远就走多远；直到碰壁无法再继续往前走，然后往回退一步，这一次走左边，然后继续往下走。用这个办法，能走遍所有的路，而且不会重复（回退不算重复走）。这个思路，就是DFS 。
（2）一群老鼠走迷宫。假设老鼠是无限多的，这群老鼠进去后，在每个路口，都派出部分老鼠探索所有没走过的路。走某条路的老鼠，如果碰壁无法前行，就停下；如果到达的路口已经有别的老鼠探索过了，也停下。很显然，所有的道路都会走到，而且不会重复。这个思路，就是BFS 。 BFS看起来像“并行计算” ，不过，由于程序是单机顺序运行的，所以，可以把BFS看成是并行计算的模拟。
简洁地说：BFS是“逐层扩散” ， DFS是“一路到底、逐层回退” 。
下面用一棵二叉树为例子，演示BFS和DFS的访问顺序。

文章图片
▍图1一棵二叉树
（1）BFS的访问顺序是：{EBGADFICH} ，即“第1层E–第2层BG–第3层ADFI–第4层CH” 。
（2）DFS的访问顺序，设先访问左节点，后访问右节点，那么访问顺序是：{EBADCGFIH} 。需要注意的是，访问顺序不是输出顺序。例如上面的二叉树，它的中序遍历、先序遍历、后序遍历都不同，但是对节点的访问顺序是一样的（实际上就是先序遍历）。具体操作，见下一节的代码。
03
BFS的性质和代码实现
BFS和DFS的实现：“BFS=队列” ， “DFS=递归” 。
为什么“BFS=队列”呢？以老鼠走迷宫为例，从起点s开始，一层一层地扩散出去。处理完离s近的第i层之后，再处理第i+1层。这一操作用队列最方便，处理第i层的节点a时，把a的第i+1层的邻居，放到队列尾部即可。
队列内的节点有2个特征：
（1）处理完第i层后，才会处理第i+1层；
（2）队列中最多有2层节点，其中第i层节点都在第i+1层前面。
下面给出BFS遍历图1二叉树的代码。分别给出了静态版和指针版二叉树的代码，竞赛中一般用静态版二叉树，不易出错。两个代码都使用STL的queue队列。
两个代码的输出都是：EBGADFICH 。
BFS（静态版二叉树）
#include<bits/stdc++.h>
usingnamespacestd;
constintmaxn=100005;
structNode{//静态二叉树
charvalue;
intlchild,rchild;
}node[maxn];
intindex=0;//记录节点
intnewNode(charval){
node[index].value=https://pcff.toutiao.jxnews.com.cn/p/20210226/val;
node[index].lchild=-1;//-1表示空
node[index].rchild=-1;
returnindex++;
}
voidinsert(int&father,intchild,intl_r){//插入孩子
if(l_r==0)//左孩子
node[father].lchild=child;
else//右孩子
node[father].rchild=child;
}
intbuildtree{//建一棵二叉树
intA=newNode('A');intB=newNode('B');intC=newNode('C');
intD=newNode('D');intE=newNode('E');intF=newNode('F');