秒懂算法 | 搜索基础

本篇介绍了BFS和DFS的概念、性质、模板代码。 

01、搜索简介

搜索，就是查找解空间，它是“暴力法”算法思想的具体实现。

暴力法（Brute force，又译为蛮力法）：把所有可能的情况都罗列出来，然后逐一检查，从中找到答案。这种方法简单、直接，不玩花样，利用了计算机强大的计算能力。

搜索是“通用”的方法。一个问题，如果比较难，那么先尝试一下搜索，或许能启发出更好的算法。竞赛的时候，遇到不会的难题，如果有时间，就用搜索提交一下，说不定判题数据很弱，就通过了。

搜索的思路很简单，但是操作起来也并不容易。一般有以下操作：

（1）找到所有可能的数据，并且用数据结构表示和存储。常用的搜索算法是BFS和DFS。

（2）优化。尽量多地排除不符合条件的数据，以减少搜索的空间。

（3）用某个算法快速检索这些数据。

02、搜索算法的基本思路

搜索的基本算法是：深度优先搜索（DFS, Depth-First Search）、宽度优先搜索（BFS, Breadth-First Search，或称为广度优先搜索）。

这两个算法的思想，用老鼠走迷宫