首页 > 其他 > 详细

深搜(DFS)与广搜(BFS)区别

时间:2018-07-21 21:04:46      阅读:175      评论:0      收藏:0      [点我收藏+]

最近做了不少的搜索题,时而用到DFS时而用到BFS,这里对两种搜索方法做一个总结。

 

广度优先搜索算法(Breadth-First-Search,缩写为 BFS),是一种利用队列实现的搜索算法。简单来说,其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。

先搜索邻居,搜完邻居再搜邻居的邻居。

其中俩个思想:   1 .队列不为空则循环

                            2.将未访问的邻接点压入队列后面,然后从前面取出并访问(这样就做到了广度优先)

图的解释:

                         0

                   1          2

             3        4   5        6

这个是二叉树的例子,这里如果是广度优先的话,访问的顺序依次是0123456.

 

 

深度优先搜索算法(Depth-First-Search,缩写为 DFS),是一种利用递归实现的搜索算法。简单来说,其搜索过程和 “不撞南墙不回头” 类似。

从起点出发,先把一个方向的点都遍历完才会改变方向......

 先找到出发点,依次对找其所有未访问的邻接点做dfs(仔细想想,这里,未访问完邻居继续做dfs,这样就做到了深度优先)

 

这里贴一个树的深度优先搜索树的例子

这个树很简单:

                         0

                   1          2

             3        4   5        6

是一个二叉树。

如果是深度优先算法来搜,则搜索顺序应该为:0134256

 

各自用途

1.BFS是用来搜索最短径路的解是比较合适的,比如求最少步数的解,最少交换次数的解,因为BFS搜索过程中遇到的解一定是离根最近的,所以遇到一个解,一定就是最优解,此时搜索算法可以终止。这个时候不适宜使用DFS,因为DFS搜索到的解不一定是离根最近的,只有全局搜索完毕,才能从所有解中找出离根的最近的解。(当然这个DFS的不足,可以使用迭代加深搜索ID-DFS去弥补)


2.DFS是空间效率高,DFS不需要保存搜索过程中的状态,而BFS在搜索过程中需要保存搜索过的状态,而且一般情况需要一个队列来记录。


3.DFS适合搜索全部的解,因为要搜索全部的解,那么BFS搜索过程中,遇到离根最近的解,并没有什么用,也必须遍历完整棵搜索树,DFS搜索也会搜索全部,但是相比DFS不用记录过多信息,所以搜素全部解的问题,DFS显然更加合适,一般情况下,DFS也需要高效的剪枝操作。 

 

这里是关于DFS中剪枝的一篇说明博客

深搜(DFS)与广搜(BFS)区别

原文:https://www.cnblogs.com/wkfvawl/p/9347828.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!