算法简介
广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS； BFS是用于图的查找算法(要求能用图表示出问题的关联性)。
BFS可用于解决2类问题：
从A出发是否存在到达B的路径；
从A出发到达B的最短路径(这个应该叫最少步骤合理)；
其思路为从图上一个节点出发，访问先访问其直接相连的子节点，若子节点不符合，再问其子节点的子节点，按级别顺序依次访问，直到访问到目标节点。
空间复杂度：
因为所有节点都必须被储存，因此BFS的空间复杂度为 O(|V| + |E|)，其中 |V|是节点的数目，而|E|是图中边的数目。
注：另一种说法称BFS的空间复杂度为 O(B**M)，其中B是最大分支系数，而M是树的最长路径长度。由于对空间的大量需求，因此BFS并不适合解非常大的问题。
时间复杂度：
最差情形下，BFS必须寻找所有到可能节点的所有路径，因此其时间复杂度为O(|V| + |E|)，其中|V|是节点的数目，而|E|是图中边的数目。
BFS解决的问题：
一般我们在算法中常用BFS来解决图、树和表格的搜索判断问题。在力扣中还是有很多题型都是套用BFS模板经行解题。而今天也是给大家带来一套BFS的解题模板，能够帮助大家能够快速的解决类似的问题！
BFS代码模板
具体过程如下：
1.准备工作：创建一个visited数组，用来记录已被访问过的顶点；创建一个队列，用来存放每一层的顶点；初始化图G。
2.从图中的v0开始访问，将的visited[v0]数组的值设置为true，同时将v0入队。
3.只要队列不空，则重复如下操作：
(1)队头顶点u出队。 (2)依次检查u的所有邻接顶点w，若visited[w]的值为false，则访问w，并将visited[w]置为true，同时将w入队。
表格类型模板
单源BFS
例题：岛屿数量
本题是一个很经典的搜索问题，最常见的解法就是使用BFS和DFS。因为本次讲解的是BFS模块，所以就拿BFS来进行解题（直接套用模板）。也会在接下来的【算法模板】系列更新DFS的模板算法！
代码块：
#设置四个方向 d = [(1,0),(-1,0),(0,1),(0,-1)] m = len(grid)#表格长度 n = len(grid[0])#表格宽度 #一个判断边界的函数 def check(i,j): #如果在这个矩阵里面则返回True，反之返回False； if i >= 0 and j >= 0 and j < n and i < m: return True else: return False #定义我们的核心模块BFS算法。 def bfs(i,j): #我们需要把岛屿先变为海洋，避免后面的误判 grid[i][j] = "0" #在python中我们可以用列表拿来当作一个队列，并把（i，j）坐标放在队列中。 stack = [(i,j)] #对队列进行一个循环然，直到队列为空才结束此次循环。 while stack: #队头出队，然后把队头的坐标分别赋值给x 和 y x , y = stack.pop(0) #然后我们需要对（x，y）坐标的上下左右进行一个判断。 for k,l in d: #如果没有超过边界且是陆地的情况下，把该陆地沉海变为0且把该坐标入队。 if check(x + k,y + l) and grid[x + k][y + l] == "1": stack.append((x + k,y + l)) grid[x + k][y + l] = "0" #设置一个变量统计岛屿的数量。 res = 0 for i in range(m): for j in range(n): #当在循环的时候碰见陆地则变量res + 1，并且让这块陆地的所有相邻陆地沉海（变为0），防止后面的误判。 if grid[i][j] == "1": bfs(i,j) res += 1 #最后返回陆地的值 return res
模块思路总结：
1、首先需要设置上下左右四个方向，且获取矩阵的长和宽。
2、写一个判断坐标是否越界的函数。
3、写核心模块bfs，首先需要有一个队列负责放入符合条件的坐标并对出队的坐标判断上下左右的坐标是否符合条件，如果符合条件则把岛屿沉入海底（变为0）。这样就能把一个岛屿全部沉入海底，并不会影响其他岛屿。
4、最后循环表格进行判断是否为陆地，在进行统计。
多源BFS:
在上述我们讲的是单源的BFS，而现在我们又来拓展一下多源的BFS。
那单源和多源有什么区别呢？
下面是通过我的理解来给大家解释一下。
| 单源 | 多源 |
我们现在应该都是直到并发这个概念吧，而单源则就代表这个程序是不支持并发，每次就只能运行一个线程。 |
多源则可以形象的解释为可以并发，是多源BFS是可以同时进行搜索。 |
例题：地图分析
你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用0和 1标记好了。其中0代表海洋，1代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1)这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
示例一：
输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。
思路：本题就是一个多源的BFS扩散问题，按照上图我们可以让四个陆地都进行一个同时扩散，则需要几次同时扩撒本题的结果就是多少！
代码：
class Solution: def maxDistance(self, grid: List[List[int]]) -> int: #检查边缘 def check(i,j,m,n): if i >= 0 and j >= 0 and i < m and j < n: return True else: return False n = len(grid) #上下四周的方向 d = [(1,0),(-1,0),(0,1),(0,-1)] #用列表来当队列 queue = [] #减去自身的一次 step = -1 #先把所有岛屿都添加到队列中，准备多源BFS for i in range(n): for j in range(n): if grid[i][j] == 1: queue.append((i,j)) #判断如果测试例子中grid中都是1或者都是0，则返回-1，代表没有。 if len(queue) == 0 or len(queue) == n ** 2: return step #使用队列对上下左右进行判断 while queue: #这个for是一个多源BFS的一个关键点，表示同时扩散的重要地方！ for i in range(len(queue)): x, y = queue.pop(0)#出队列 for k , l in d: #判断周围的海 if check(x + k , y + l , n, n) and grid[x + k][y + l] == 0: queue.append((x +k,y + l )) grid[x + k ][ y + l ] = grid[x ][y ] + 1 step += 1#每循环一次就表示陆地对海洋的距离 return step#最后返回距离值
秒杀两题不够爽不要着急我专门为大家准备了更多的习题带给大家呢嘿嘿嘿嘿！！！！
