27. BFS和DFS基础知识

一、DFS和BFS的区别和优势

1. 说明：

1. BFS（宽度有限搜索）
2. DFS（深度有限搜索）

2. 优劣势：

1. BFS   需要把下一层所有的方案都存下来，需要很大的空间，空间是指数级别的；
   DFS   需要的空间只与路径的长度有关系。
2. BFS优势：有可以寻找最小的优势 （最小性）
3. DFS：一条路走到黑
4. DFS劣势：
   1. 空间复杂度和深度成正比
   2. C++的限制：栈空间默认只有4M
   3. DFS搜索时，系统栈分到栈空间里面的，当搜索层数太多时，系统栈就会爆掉，就是RE，大概搜索 10万 层时就会RE
   4. 所以说，如果层数深的话，尽量用BFS，避免爆栈

3. 区别

BFS：

1. 空间是指数级别的，比较大！！！
2. 不会有爆栈的风险
3. 能搜索：最短，最小……

DFS：

1. 空间和深度成正比，比较小！！！
2. 有爆栈的风险，比如树的深度最坏可能有100000层，此时会爆栈
3. 不能搜：最短，最小……