lc刷题笔记-搜索算法-dfs, bfs

搜索算法主要是基于BFS和DFS实现的，刷题参考了labuladong的解题模板。刷题过程中比较困惑我的几个点，比如dfs和batcktrack的区别，dfs什么时候有需要返回值，什么时候不需要（most case，如8岛屿数量）

DFS和backtrack的区别：
1.backtrack需要对遍历的position做选择，遍历每一种选择，同时dfs下一个，再撤回选择，如lc8皇后，解数独
2.dfs不需要做选择，只需走下去，同时跳过已经遍历过的点；

什么时候主函数需要遍历，什么时候主函数只需要调用一次：
1. backtrack主函数不需要遍历，只需要调用即可
2. dfs由于不一定能达到所有node，因此需要在主函数for遍历所有node，如岛屿问题

什么时候用DFS，什么时候用BFS：
1.用BFS：
a.最少情况用BFS：可以提前结束，如111叉树最小深度，如773滑动谜题；
b.拓扑问题用，如lc210 课程表2
2.用DFS：BFS解决不了的问题：，可以用DFS，如岛屿问题。感觉几乎BFS的问题都可以用DFS解决；BFS的优势是可以在最小深度提前结束。缺点是空间复杂度受宽度影响

dfs深搜函数：
什么时候需要返回值：需要记录dfs深度或数量信息的，如695岛屿的最大面积
什么时候不需要返回值：只需要dfs标记是否访问过即可，如200岛屿数量