欢迎回到：遇见蓝桥遇见你，不负代码不负卿！

目录

一、广度优先搜索算法（BFS） 

典例一：二叉搜索树的范围和

方法一：DFS解法

方法二：BFS解法

典例二：二叉树的层序遍历

典例三：二叉树的层序遍历 II

典例四：岛屿数量

方法一：DFS解法 

方法二：BFS解法

五、易错误区

六、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿！

搜索算法在蓝桥中考的还是很频繁的，之前发表了二叉树数据结构以及深度优先搜索章节，前面还是比较简单的，这里的广度优先搜索可能稍微复杂那么一丢丢，因为要用到队列，不过我们可以使用STL容器也是很方便就解决了。 

【声明】：由于前半部分是基础知识点定义部分，所以前面一小半部分的赘述笔者是参考力扣官方给出的定义以及《算法笔记》一书。

一、广度优先搜索算法（BFS） 

对于广度优先搜索的定义及特点，力扣官方是这样给出的： 

广度优先搜索算法（Breadth-First Search，缩写为 BFS），又称为宽度优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。广度优先搜索也广泛应用于图论问题中。 

齐头并进的广度优先遍历

说明：遍历到一个结点时，如果这个结点有左（右）孩子结点，依次将它们加入队列。 

可能上面讲的不够细节，下面详细介绍何为”广搜”：

首先呢，铁汁们先将之前的DFS章节前面的迷宫问题再回顾一下，知道何为“死胡同”以及“岔道口”

https://blog.csdn.net/weixin_57544072/article/details/121262172https://blog.csdn.net/weixin_57544072/article/details/121262172

前面介绍了深度优先搜索，可知DFS是以深度作为第一关键词的，即当岔道口时总是先选择其中的一条岔道前进，而不管其他岔路，直到碰到死胡同时才返回岔道口并选择其他岔路。接下来将介绍的广度优先搜索（Breadth First Search， BFS）则是以广度为第一关键词，当碰到岔道口时，总是先依次访问从该岔道口能直接到达的所有节点，然后再按这些节点被访问的顺序去依次访问它们能直接到达的所有节点，以此类推，直到所有节点都被访问为止。

这就跟在平静的水面中投入一颗小石子一样，水花总是以石子落水处为中心，并以同心圆的方式向外扩散至整个水面，从这点来看和DFS那种沿着一条线前进的思路是完全不同的。

概念部分就讲这么多咯，我呢一直是以讲题目练习为主，OK，废话不多说，咱们走起来！

典例一：二叉搜索树的范围和

原题链接：https://leetcode-cn.com/problems/range-sum-of-bst/https://leetcode-cn.com/problems/range-sum-of-bst/

注意：二叉搜索树的特点就是左子树都比根要小，右子树都比根要大！ 

题目描述：

方法一：DFS解法

本题很简单，铁汁们看代码里面的注释就能理解啦。

代码执行：

方法二：BFS解法

使用广度优先搜索的方法，用一个队列 q 存储需要计算的节点。每次取出队首节点时，若节点为空则跳过该节点，否则按方法一中给出的大小关系来决定加入队列的子节点。

代码执行：

典例二：二叉树的层序遍历

原题链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

题目描述：

代码中注释给得很详细咯，快去康康叭。 

代码执行：

典例三：二叉树的层序遍历 II

原题链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

题目描述：

哈哈，本题主要是让大家熟练掌握二叉树的层序遍历才添加进来的，本题呢，直接将最后存放到二维数组中的数据反转（#include<algorithm>头文件下）即可。 

代码执行：

典例四：岛屿数量

原题链接：https://leetcode-cn.com/problems/number-of-islands/https://leetcode-cn.com/problems/number-of-islands/

题目描述：

方法一：DFS解法 

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0（也就是下面代码中所说的“同化”）

代码执行：

方法二：BFS解法

同样地，我们也可以使用广度优先搜索代替深度优先搜索。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列（注意哦，是将其对应的下标存放到队列中的）开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。

代码执行：

五、易错误区

最后需要指出的是，当使用STL的queue时，元素入队的push操作只是制造了该元素的一个副本入队，因此在入队后对原元素的修改是不会影响队列中的副本，同样的，对队列中副本的修改也不会改变原元素，需要注意由此可能引入的bug！ 

例如下面这个例子：

发现上面出现的问题了吗，这就是说，当需要对队列中的元素进行修改而不仅仅是访问时，队列中存放的元素最好不要是元素本身，而是它们对应的编号（如果是数组的话则是下标）。

例如把上面的程序改成下面这样：

六、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿！

搜索的基础部分到这里就结束咯，不过嘞，不会这么简单就结束掉的，后面的话笔者还会出一个蓝桥杯冲刺专栏，还有大量的练习以及相当一部分的真题！OK，今天就到这里咯，下一章节讲的是动态规划（DP）哈。

如果大家有所收获的话，麻烦给俺个三连呗，万分感谢，抱拳了哈。