先来看一个问题：搜索的核心是什么？
搜索的核心：就是暴力枚举所有可能！
不会吧？！这么通俗，这么接地气？
高端的食材往往只需要最朴素的烹饪方式！
这就是搜索问题的核心，算法什么的，可以看作是对暴力枚举的辅助。
搜索的常用算法：DFS(深度优先) 和 BFS(广度优先)
DFS 和 BFS 是搜索的核心，贯穿始终。
DFS 的概念源自图论，但搜索中的 DFS 和图论中的 DFS 有一些区别：搜索中的 DFS 一般指通过递归实现暴力枚举；如果不使用递归，也可使用栈来实现，但本质上是类似的。
DFS：将状态空间映射成一张图，状态就是图中的节点，状态之间的联系就是图的边，然后在这张图上进行深度优先遍历；
BFS：也是先影射成一张图：只不过遍历的策略变为了广度优先，一层层铺开遍历而已；
所以 BFS 和 DFS 只是遍历这个状态图的两种方式罢了，关键在于如何构建状态图。
注意事项：
本质上，对上面所说的图进行遍历，最终会生成一颗搜索树。为了避免重复访问，需要记录已访问过的节点，这些是所有搜索算法的共有特性，需要牢记。
另外，在树上遍历，不用担心是否有环，因为树的本质是一个简单无环图，记录已经访问的节点是为了减少时间复杂度，避免重复操作。
DFS 算法流程
- 1、首先将根节点入stack；
- 2、从stack取出第一个节点，判断是否为target；如果找到，则结束搜寻并回传结果，否则将它的某一个尚未被检验的直接子节点入栈（BFS和DFS的基本区别就是此处的，子节点入栈方式）
- 3、重复步骤 2。
- 4、如果不存在未检测过的直接子节点(某个分支已遍历完成)，则将上一级节点加入stack中，并重复步骤 2；
- 5、重复步骤 4；
- 6、若stack为空，表示整张图都检查过了，即图中为搜寻到target，结束并回传false；
注：这里的 stack 可理解为自实现的栈，也可以理解为调用栈
DFS 遍历技巧
DFS 常见的有三种方式：前序遍历、中序遍历、后序遍历；
前中后序，对应的就是树的 左、根、右 节点；
如何分辨该使用哪种遍历方式呢，其实并不难，因为大多数情况下，搜索过程中，当前节点的结果都需要依赖其他节点，因而诞生了这三种根据不同顺序遍历的方法。
比如，当前节点需要依赖其子节点的计算结果，那么就需要考虑，使用后序遍历，自底向上，遍历了；
反之，如果当前节点需要依赖其父节点的信息，那么就需要使用，前序遍历，自顶向下，遍历了。
参考下图，DFS的深度优先遍历顺序是：A-》B-》E；
DFS示例.png
BFS 算法流程
BFS 也是图论中算法的一种，不同于 DFS， BFS 采用的是横向搜索方式，辅助算法实现的数据结构通常采用队列结构，而DFS通常使用栈结构(见上面描述)。
具体来说，我们不断从队头取出状态，然后将此状态对应的决策产生的所有新状态推入队尾，重复以上过程直至队列为空；
- 1、首先将根节点放入队列中。
- 2、从队列中取出第一个节点，并检验它是否为目标值：如果找到目标，则结束搜索并回传结果；否则将它所有尚未检验过的直接子节点加入队列。
- 3、若队列为空，表示整张图都检查过了，即图中没有找到目标值。结束搜索并回传false。
- 4、重复步骤 2。
参考下图，BFS的广度优先遍历，会在每一层先遍历自己的同胞节点：
BFS.png
DFS 和 BFS 的使用区别
一般情况，力扣中关于搜索的题目，首先考虑DFS，大部分时候可以解决；
而BFS一般考虑用来处理最短路径问题，用一个哈希表 dist 记录从源点到图中其他点的距离；
这个 dist 也可以充当防止环产生的功能，这是因为第一次到达一个点后，再次到达此点的距离，一定比第一次到达的路径大，利用此特点，就可知道是否是第一次访问了。
DFS 和 BFS 的差异
DFS 和 BFS 都是对题目设置的状态空间进行搜索但：
- DFS 在分叉点会任选一条深入进入，即先挑自己的儿子节点搜索，遇到终点则返回，再次返回到分叉口(同胞节点)后，尝试下一个选择。基于此，我们可以在路径上记录一些数据；
- BFS 在分叉点会选择将所有同胞节点的路径各尝试一次，因此需要使用队列来存储待处理的节点，队列中最多包含两层元素，且满足单调性，即相同层级(同胞节点)的元素在一起；
村长总结
总结一下搜索类题目的的常见解题套路：
- 1、根据题目要求构建状态空间（画图）；
- 2、对图进行遍历（BFS 或者 DFS）；
- 3、记录和维护状态（比如 visited 维护访问情况， 队列和栈维护状态的决策方向等）；
几个小技巧：
- DFS 通常都是有递推关系的，而递归关系就是图的边；梳理出递归关系后，就明白选择哪种遍历方式(前、中、后序遍历)，更合理了；
- BFS 由于其单调性，因此适合求解最短距离问题；
- BFS 中用到的队列，不一定非得是队列结构，也可以用哈希表替代，比如村长用PHP刷题，而PHP是没有队列这种数据结构的，所以都是用数组类型模拟；
- visitd(记录已访问节点) 和 dist/cost(记录距离花费等) 都可以起到记录节点访问情况的目的，以防止环的产生。
。。。
如果觉得本文对你有那么一丢丢的帮助，就抬起爪子点个赞吧！
网友评论