广度优先搜索怎么看（广度优先搜索序列怎么做）

大家好，我是讯享网，很高兴认识大家。

 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg>

讯享网

假设你现在身处一个迷宫之中，而你对这个迷宫完全不了解，你只知道其中一定有一个点是通往出口的。现在你有个天赋技能——无限分身，你以及你的分身可以在原地分裂出多个相同的人。问：你要如何做才能保证你能最快找到出口？

（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的时候就表示在当前这一层，我们可以很容易用循环来实现，但是实际上我们可以用双端队列来实现。

讯享网

广度优先搜索怎么看（广度优先搜索序列怎么做）

相关推荐