假设你现在身处一个迷宫之中，而你对这个迷宫完全不了解，你只知道其中一定有一个点是通往出口的。现在你有个天赋技能——无限分身，你以及你的分身可以在原地分裂出多个相同的人。问：你要如何做才能保证你能最快找到出口？
（1）把起点放入队列，此时队列里面只有起点一个元素。
（2）遍历起点的所有方向，找出所有合理的并且没有被标记过的点放入队列中。
（3）当队头元素所有方向遍历完成后，队头元素出队，继续遍历当前队头元素的所有方向并且依次入队。
（4）重复执行上述操作，直到队列为空或者找到终点为止。如果队列为空，说明从起点到终点没有路径，如果找到终点，则当前路径长度就是最短路径长度
同样的，这里我们还是用数组来模拟队列（没学过的看我之前的文章）
深搜和广搜各有优缺点，从效率上看，深搜的时间复杂度远大于广搜，那么我们为什么还要学习深搜呢？因为广搜是按层拓展，处于每一层的点到起点的距离被认为是相等的，所以每一层的路径长度都必须相等，否则就不可以用广搜，所以深搜的使
用范围比广搜大。
深搜的范围不仅仅不如，很多难题不会做的时候，都需要打暴力，但是很多暴力不知道循环的终点，每次循环的变化量都不一样，所以就需要用深搜来打暴力，称为爆搜，所以学好深搜，并且熟练剪枝是很有必要的。
既然，广度优先搜索的效率远高于深度优先搜索，那么我们为什么还要学习深搜呢？广搜能不能完全代替深搜呢？
我们以前学习的深搜的题包括以下几类：
一：非最短路(只能用DFS)
（1）起点到终点的所有路径
（2）起点到终点的所有方案
二：最短路
（1）每走一步花费的代价一样(DFS和BFS)
（2）每走一步花费的代价不一样(只能用DFS)
综上所述，因为BFS是按层搜索，所以找到的起点到终点的距离一定是最短路径，并且搜索过一次就不会再搜索第二次了。同样的，当权值不同的时候，层次就会发生错误，第一次求出来的未必就是最短路。
在一个n*n的方格中，有两种颜色的格子，在相同颜色之间移动不需要消耗体力，但是在不同颜色之间移动需要消化1个单位的体力，问给定一个起点和一个终点，求起点到终点的最小体力消耗。n<=2000
这就是一道典型的权值为0和1的搜索题，如果用深搜，n<=2000,肯定超时。如果用普通广搜，搜到一个点就放入队尾，肯定是错误的，因为不满足队列中消耗的递增性。所以我们要用双端队列bfs。如果是相同颜色，无消耗，即和当前队首元素的优先级是一样的，所以我们完全可以把该点放入队首，这样不影响整个队列的有序性。如果是不同的颜色，消耗+1，和普通广搜一样，放入队尾，仍然可以保持原来的优先级。虽然这种思路很简单，但是在写法细节上和普通广搜还是有一些区别，一定要熟悉两种写法，以免混淆在一起。
有的时候会出现一种奇怪的题，虽然每条路径的长度不完全相同，但是也有规律性，比如路径长度只有0和k(常数),并且数据范围很大n<=1000,如果用深搜，时间过不了，如果用广搜，感觉按层拓展又不对。
实际上，当路径长度为0的时候就表示在当前这一层，我们可以很容易用循环来实现，但是实际上我们可以用双端队列来实现。
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/bcyy/27775.html