栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode刷题 - 广度优先搜索与深度优先搜索小结

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode刷题 - 广度优先搜索与深度优先搜索小结

一.广度优先搜索

一般用来:

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.使用在模拟流程,寻找所有情况全排列解

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/978838.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号