深度优先和广度优先 的区别 ,用法。

如题所述

1、主体区别

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件)。

宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。

2、算法区别

深度优先搜索是每次从栈中弹出一个元素,搜索所有在它下一级的元素,把这些元素压入栈中。并把这个元素记为它下一级元素的前驱,找到所要找的元素时结束程序。

广度优先搜索是每次从队列的头部取出一个元素,查看这个元素所有的下一级元素,把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱,找到所要找的元素时结束程序。

3、用法

广度优先属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。

深度优先即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。

扩展资料:

实际应用

BFS在求解最短路径或者最短步数上有很多的应用,应用最多的是在走迷宫上,单独写代码有点泛化,取来自九度1335闯迷宫一例说明,并给出C++/Java的具体实现。

在一个n*n的矩阵里走,从原点(0,0)开始走到终点(n-1,n-1),只能上下左右4个方向走,只能在给定的矩阵里走,求最短步数。n*n是01矩阵,0代表该格子没有障碍,为1表示有障碍物。

int mazeArr[maxn][maxn]; //表示的是01矩阵int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4个方向,int visit[maxn][maxn]; //表示该点是否被访问过,防止回溯,回溯很耗时。核心代码。基本上所有的BFS问题都可以使用类似的代码来解决。

参考资料来源:百度百科-广度优化

参考资料来源:百度百科-深度优化

温馨提示:答案为网友推荐,仅供参考
相似回答