BFS的缺点适用情况
BFS的一般步骤：
- 1、将初始点（一个或多个）加入队列
- 2、从队列头取出点，判断初始点的周边点，将符合条件的点加入队列尾部
- 3、重复2操作，直至队列为空。(一般每个点只加入队列一次)
BFS的缺点：
在搜索过程中，BFS必须要保存搜索过程中的状态，用于判重。
- 注意，用于保存搜索过程的点的数据结构，要是hashset类型的。至于为什么，参考Python 中list ,set,dict的大规模查找效率总结的很到位了。如果用in 方法去判断元素是否在list中时，会超时。所以最好用set。
- 即使用了set，也是需要一定的时间复杂度的。因此势必会花掉一些时间和空间。
BFS的适用情况
一般在树或者图中，用BFS的可能性比较大。
1.BFS是用来搜索最短径路的解是比较合适的，比如求最少步数的解，最少交换次数的解，因为BFS搜索过程中遇到的解一定是离根最近的，所以遇到一个解，一定就是最优解，此时搜索算法可以终止。
这个时候不适宜使用DFS，因为DFS搜索到的解不一定是离根最近的，只有全局搜索完毕，才能从所有解中找出离根的最近的解。（当然这个DFS的不足，可以使用迭代加深搜索ID-DFS去弥补）
DFS的缺点以及适用情况
DFS的优点
2.空间优劣上，DFS是有优势的，DFS不需要保存搜索过程中的状态，而BFS在搜索过程中需要保存搜索过的状态，而且一般情况需要一个队列来记录。
因为根据栈的思想，DFS在搜索一个点以后，会弹出该点，就不需要保存已经搜索过的点。而BFS是必定保存搜索过的点的。
DFS的缺点
因为DFS含有栈的思想，因此经常用递归解决问题，但是如果不给递归限制深度，往往会超过时间与空间复杂度的。
二维数组的题目，N小于20的，适用DFS。而一般 N<= 200，N<=1000这种，一定不可能用DFS去做。而且并不只是整个题目不能用DFS，其中的每一步也不能使用DFS。
上面的N指的应该是递归深度**。
比如LeetCode中的Unique Paths，若是用大集合，会超时，该题适合用DP解。
DFS的适用情况：
3.DFS适合搜索全部的解，因为要搜索全部的解，那么BFS搜索过程中，遇到离根最近的解，并没有什么用，所以搜素全部解的问题，DFS显然更加合适。
当求解目标，必须要走到最深（例如树，走到叶子节点）才能得到一个解，这种情况适合用深搜。
综述
1、对于一般的图（比如例题中的词梯），而不是二维数组这样的存在来说
-
BFS适用于最短问题。而且必须用set类型来保存中间搜索过的点。
-
DFS适用搜索全部的解，或者求节目表要走到最深处的问题。
-
尽管DFS不保存中间状态，也要限制递归深度才行。递归深度过深，也会超时 。
2、特例——二维数组
无论是BFS还是DFS，在遇到二维数组是，情况就不一样了。因为一般的图，没有一个固定的形状，没法用一些技巧，避免用set判重。
而二维数组，可以用一些技巧，避免用set判重。
2.1、技巧：将搜索过的“O”变成不用搜索的“X”。
在BFS的例题，Surrounded Islands中，对四条边进行搜索“O”，并且在递归中，把搜索到的“O”都变成了“X”，这样在下次遇到点的时候，只需要比较判断是不是“O”就行了，不需要再用in方法在set中查找了。
在DFS的例题numIslands中，对于已经搜索过的点，也可以用同样的技巧。
#######################################################
DFS不需要也不能保存中间状态，比如在二维数组的问题，numIsland这题中，如果用set把访问过的点坐标存储起来，在每次递归的时候都用in方法判重，会因为有大量的判重操作而超时。
所以可以通过构造一个与输入相同shape的二维数组来对每个坐标是否访问过进行追踪，把每次判断的时间复杂度控制在O(1)，或者就用上面的技巧。
网友评论