1.搜索
搜索包括深度优先搜索和广度优先搜索，这两种算法是算法竞赛的基础。本专题全面介绍这两种算法的思想、编码、应用和扩展。它不仅能直接用于解决问题，也启发了很多高级算法
搜索简介
搜索是 "暴力法" 算法思想的具体实现。暴力法(Brute Force)又称为蛮力法，把所有可能的情况都罗列出来，然后逐一检查，从中找到答案。这种方法简单直接，不玩花样，利用了计算机强大的计算能力
搜索是"通用"的方法。如果一个问题比较难，可以先尝试搜索，或许能启发出更好的算法。竞赛时遇到难题，如果有时间，试试用搜索提交，说不定判题数据很弱，就通过了
搜索的思路很简单，但是操作起来也并不容易，一般有如下步骤
- 找到所有可能的数据，并且用数据结构表示和存储
- 优化。尽量多地排除不符合条件地数据，以减少搜索的空间
- 用某个算法快速检索这些数据
搜索算法的基本思路
搜索的基本算法分成两种：深度优先搜索(Depth-First-Search,DFS)和广度优先搜索(Breadth-First-Search,BFS)
这两个算法的思想可以用"小老鼠走迷宫"的例子说明，又形象又透彻。迷宫内部的路错综复杂，小老鼠从入口进去后，怎样才能找到出口 ? 有两种不同的方法
- 一只老鼠走迷宫。它在每个路口都选择先走左边(先走右边也可以)，能走多远就走多远，直到碰壁无法继续前进，然后回退一步改走右边，继续往下走。这个办法能走遍所有路，并且不会重复(回退不算重复)。这个思路就是 DFS
- 一群老鼠走迷宫。假设老鼠无限多，这群老鼠进入迷宫后，在每个路口都派出部分老鼠探索所有没走过的路。走某条路的老鼠，如果碰壁无法前行就停下；如果到达的路口已经有别的老鼠探索过，也停下。显然，所有道路都能走到，并且不会重复。这个思路就是 BFS，BFS 看起来像"并行计算"，不过由于程序是单机顺序运行的，可以把 BFS 看作并行计算的模拟
BFS 是"全面扩散、逐层递进"；DFS 是"一路到底，逐步回退"
下面以一棵二叉树为例，演示 BFS 和 DFS 的访问顺序
BFS 的访问顺序是 E B G A D F I C G
访问次序为
- 第一层 E
- 第二层 B G
- 第三层 A D F I
- 第四层 C H
BFS 的特点是分层访问，每层访问完毕后才访问下一层
DFS 的访问顺序是先访问左节点在访问右节点，访问顺序是 E B A D C G F I H
BFS的代码实现
BFS 的代码实现可描述为 "BFS=队列"。为什么"BFS=队列" ? 以小老鼠走迷宫为例，从起点 s 开始一层一层地扩散出去，处理完离 s 近的第 i 层之后，在处理第 i+1 层。这一操作用队列最方便，处理第 i 层的节点 a 时候，把 a 的第 i+1 层的邻居放到队列队尾部即可。队列内的节点有一下两个特征
- 处理完第 i 层后，才会处理第 i+1层
- 队列中在任意时刻最多有两层节点，其中第 i 层节点都在第 i+1 层前面
代码框架
全局状态变量void BFS()
{定义状态队列初始状态入队while(队列不为空){取出队首状态作为当前状态if(当前状态是目标状态){进行相应处理（输出当前解、更新最优解、退出返回等）} else{for(所有可行的新状态) {if(新状态没有访问过 && 需要访问) // 可行性剪枝、最优性剪枝、重复性剪枝{新状态入队}}} }
}
下面分析 BFS 遍历二叉树的复杂度
