深度优先（深度优先算法和广度优先算法）

by intanet.cn ca 算法 on 2024-03-19

本篇文章给大家谈谈深度优先，以及深度优先算法和广度优先算法对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

1、深度优先遍历的思想是什么？
2、深度优先和广度优先的区别，用法。
3、什么是深度优先搜索？
4、请解释“层优先”和“深度优先”的含义？

深度优先遍历的思想是什么？

深度优先遍历类似树的先序遍历，是树的先序遍历的推广。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先遍历的思想是：首先访问图中某指定的起始点vi，袜碰然后由vi出发访问它的任一个邻接点vj，再从vj出发访问vj任一个未被访问的邻接点vk，接着从vk出发进行类似的访问，如此进行下去，一直到某顶点已没有未被访问过的邻接点，则退回一步，找前一个顶点的其他尚未被访问的邻接点。如果有尚未被访问的邻接点，则访问此顶点后，好唤再从该顶点出发进行与前述类似的访问；如果退回一步后，前一个顶点也没有未被访问的邻接点，则再向前回告袜谈退一步再进行搜索，重复上述过程，直到所有顶点均被访问过为止。

[img]

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

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问题都可以使用类似的代码来解决。

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

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

什么是深度优先搜索？

深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。由此可见，把通常问题转化为洞渣树的问题是至关重要的一步，完成了树的转换基本完成了问题求解。

(1)减少节点数，思想：尽可能减少生成的节点数

(2)定制回溯边界，思想：定制回溯边界条件，剪掉不可能得到最优解的子树

在很多情况下，我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解，搜索到后也只能回溯。为了避免出现这种情况，我们需要灵活地去定制回溯搜索的边界。在深度优先搜索的过程当中，往往有很多走不通的“死路”。假如我们把这些“死路”排除在外，不是可以节省很多的时间吗？打一个比方，前面有一个路径，别人已经提示：“这是死路，肯定不通”，而你的程序仍然很“执着”地要继续朝这个方向走，走到头来才发现，别人的提示是正确的。这样，浪费了很多的时间。针对这种情况，我们可以把“死路”给昌扮标记一下不走，就可以得到更高的搜索效率耐颤灶。