一般用来:
1.遍历树结构(level order)
2.遍历图结构(BFS,Topological)
3.遍历二维数组
模板// 计算从起点start到终点target的最近距离
int BFS(Node start,Node target){
Queue q; // 核心数据结构
Set visited; // 避免走回头路
q.offer(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数
while(q not empty){
int sz = q.size();
for(int i = 0;i < sz;i++){
Node cur = q.poll();
if(cur is target)
return step;
for(Node x: cur.adj())
if(x not in visited){
q.offer(x);
visited.add(x);
}
}
step++;
}
}
优点
对于解决最短或最少问题特别有效,而且寻找深度小,但缺点是内存消耗费量大(需要开大量的数组单元用来存储状态,取决于树本身的形状,扁平还是长条)
数据结构上的运用BFS选取状态用队列的形式,先进先出
总结bfs最擅长解决哪一类问题?bfs与dfs的效率哪个更好?
首先,bfs最擅长解决哪一类问题?bfs和dfs的效率哪个更好?
1.比如求最少步数的解,最少交换次数的解,因为bfs搜索过程中遇到的解一定是离根最近的,所以遇到一个解,一定就是最优解,此时搜索算法可以终止。这个时候不适合使用dfs,因为dfs搜索到的解不一定是离根最近的,只有全局搜索完毕,才能从所有解中找出离根最近的解
2.dfs是空间效率高,dfs不需要保存搜索过程中的状态(在heap中纵向),而bfs在搜索过程中需要保存搜索过的状态(横向level),而且一般情况需要一个队列来记录。详细来说的话取决于树(图)的形状,扁的还是长条形
3.dfs适合搜索全部的解,因为要搜索全部的解,那么bfs搜索过程中,遇到离根最近的解,并没有什么用,也必须遍历完整棵搜索树,dfs搜索也会搜索全部,但是相比dfs不用记录过多信息(Java heap帮你保存了,除非overflow需要自己外部开一个空间做stack),所以搜索全部解的问题,dfs显然更加合适,一般情况下,dfs也需要高效的剪枝操作
4.可以双向bfs优化搜索的速度,进阶还会有 A * search
二.深度优先搜索深度优先遍历的主要思想是:首先以一个未被访问过的顶点作为起始顶点,沿当前顶点的边走到未访问过的顶点;当没有未访问过的顶点时,则回到上一个顶点,继续试探访问别的顶点,直到所有的顶点都被访问。
沿着某条路径遍历直到末端,然后回溯,再沿着另一条进行同样的遍历,直到所有顶点都被访问过为止。
模板result = []
def backtrack(路径,选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径,选择列表)
撤销选择
优点
扁平型tree内存开销较小
能处理子节点较多或树层次过深的情况(相比BFS)
一般用于解决连通性问题(是否有解)
对于解决遍历和求所有问题有效,对于问题搜索深度小的时候处理速度迅速
缺点只能寻找有解但无法最快找到最优解(寻找最优解同样要遍历所有路径)
数据结构上的运用
DFS用递归的形式,用到了栈结构,先进后出
复杂度DFS的复杂度与BFS的复杂度大体一致,不同之处在于遍历的方式与对于问题的解决出发点不同,DFS适合目标明确,而BFS适合大范围的寻找
一般使用场景1.模板dfs,mask举例dfs
2.外部空间dfs(用stack写成iterative way,for example tree traversal)
3.dfs + memo(DP剪枝)
4.使用在模拟流程,寻找所有情况全排列解



