刷题笔记六：广度优先搜索‼️

还是跟以前的笔记一样，总结参考了作者高畅的LeetCode101, 题目都是来自leetcode, 题解用的语言是python！
核心：广度优先搜索(breadth-first search，BFS)不同与深度优先搜索，它是一层层进行遍历的，因此需要用先入先出的队列而非先入后出的栈进行遍历。由于是按层次进行遍历，广度优先搜索时 按照“广”的方向进行遍历的，也常常用来处理最短路径等问题。
考虑如下一颗简单的树。我们从1号节点开始遍历，假如遍历顺序是从左子节点到右子节点， 那么按照优先向着“广”的方向前进的策略，队列顶端的元素变化过程为 [1]->[2->3]->[4]，其中 方括号代表每一层的元素。

这里要注意，深度优先搜索和广度优先搜索都可以处理可达性问题，即从一个节点开始是否 能达到另一个节点。因为深度优先搜索可以利用递归快速实现，很多人会习惯使用深度优先搜索 刷此类题目。实际软件工程中，笔者很少见到递归的写法，因为一方面难以理解，另一方面可能 产生栈溢出的情况;而用栈实现的深度优先搜索和用队列实现的广度优先搜索在写法上并没有太 大差异，因此使用哪一种搜索方式需要根据实际的功能需求来判断。

例题：
LC 934. shortest bridge: 给定一个二维 0-1 矩阵，其中 1 表示陆地，0 表示海洋，每个位置与上下左右相连。已知矩 阵中有且只有两个岛屿，求最少要填海造陆多少个位置才可以将两个岛屿相连。
题析：本题实际上是求两个岛屿间的最短距离，因此我们可以先通过深度优先的搜索方法找到其中一个岛屿，然后利用广度优先搜索，查找其与另一个岛屿的最短距离。
题解：请看图。

笔记持续更新，求加米，谢谢！