BFS 的核心思想应该不难理解的，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。
BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多，至于为什么，我们后面介绍了框架就很容易看出来了。

要说框架的话，我们先举例一下 BFS 出现的常见场景好吧，问题的本质就是让你在一幅「图」中找到从起点 **start** 到终点 **target** 的最近距离，这个例子听起来很枯燥，但是 BFS 算法问题其实都是在干这个事儿，把枯燥的本质搞清楚了，再去欣赏各种问题的包装才能胸有成竹嘛。
这个广义的描述可以有各种变体，比如走迷宫，有的格子是围墙不能走，从起点到终点的最短距离是多少？如果这个迷宫带「传送门」可以瞬间传送呢？
再比如说两个单词，要求你通过某些替换，把其中一个变成另一个，每次只能替换一个字符，最少要替换几次？

  1. # 模版
  2. def bfs(self, nums):
  3.     queue = [起始点]    # 队列实现BFS
  4.     visited = set()    # 记录访问过的元素点，避免“回头”访问，陷入循环
  5.     visited.add(起始点) # 将起点加入队列
  6.     depth = 0 # 记录扩散的步数
  7.     while queue:
  8.         # 将所有节点同时向前扩散一步
  9.         for _ in range(len(queue)):
  10.             cur = queue.pop(0)
  11.             if 找到目标:
  12.                 return depth
  13.             # 将cur的【所有相邻且没被访问过的节点】加入队列
  14.             for near in cur的邻近节点：
  15.                 if near not in visited:
  16.                     queue.append(near)
  17.                     visited.add(near)
  18.         depth += 1    # 记录路径长度
  1. # 二叉树的最小深度
  2. class Solution:
  3.     '''BFS迭代方法'''
  4.     def minDepth(self, root: TreeNode) -> int:
  5.         if not root:
  6.             return 0
  8.         depth = 1
  9.         queue = [root]
  10.         while queue:
  11.             for i in range(len(queue)):
  12.                 node = queue.pop(0) # 切记要先取出
  13.                 if not node.left and not node.right:
  14.                     return depth
  15.                 if node.left:
  16.                     queue.append(node.left)
  17.                 if node.right:
  18.                     queue.append(node.right)
  19.             depth += 1
  20.         return depth

岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
输入：grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出：1
输入：grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出：3

  1. class Solution(object):
  2.     def numIslands(self, grid):
  3.         # 方法一：广度优先遍历 BFS
  4.         def bfs(grid, i, j):
  5.             queue = [[i, j]]
  6.             while queue:
  7.                 [i, j] = queue.pop(0)
  8.                 if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':
  9.                     grid[i][j] = '0'
  10.                     queue += [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]
  11.         count = 0
  12.         for i in range(len(grid)):
  13.             for j in range(len(grid[0])):
  14.                 if grid[i][j] == '0': 
  15.                     continue
  16.                 bfs(grid, i, j)
  17.                 count += 1
  18.         return count
  21.         # 方法二：深度优先遍历DFS，这种好理解
  22.         def dfs(grid, i, j):
  23.             if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0': 
  24.                 return
  25.             # 将岛屿所有节点删除，以免之后重复搜索相同岛屿
  26.             grid[i][j] = '0'
  27.             dfs(grid, i + 1, j)
  28.             dfs(grid, i, j + 1)
  29.             dfs(grid, i - 1, j)
  30.             dfs(grid, i, j - 1)
  31.         count = 0
  32.         for i in range(len(grid)):
  33.             for j in range(len(grid[0])):
  34.                 if grid[i][j] == '1':
  35.                     # 从 (i, j) 向此点的上下左右 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 做深度搜索
  36.                     dfs(grid, i, j)
  37.                     count += 1
  38.         return count

打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
输入：deadends = [“0201”,”0101”,”0102”,”1212”,”2002”], target = “0202”
输出：6
解释：
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的，
因为当拨动到 “0102” 时这个锁就会被锁定。
输入: deadends = [“8888”], target = “0009”
输出：1
解释：
把最后一位反向旋转一次即可 “0000” -> “0009”。

  1. class Solution(object):
  2.     def openLock(self, deadends, target):
  3.         # 可抽象成最短路径问题，由起始点'0000'到目标target的最短路径长度，路径中不能经过死亡数字。套用上面框架即可。
  4.         # BFS
  5.         queue = ['0000']
  6.         visited = set()
  7.         visited.add('0000')
  8.         deadset = set(deadends)
  9.         depth = 0
  10.         while queue:
  11.             for _ in range(len(queue)):
  12.                 cur = queue.pop(0)
  13.                 if cur in deadset:
  14.                     continue             # 如果cur是死亡数字，则不选这条路径
  15.                 if cur == target:
  16.                     return depth          # 如果cur = target，则找到目标，返回depth
  17.                 # 将当前cur元素的所有邻近元素加入队列和visited
  18.                 for i in range(4):
  19.                     up = self.up(cur, i)
  20.                     if up not in visited:
  21.                         queue.append(up)
  22.                         visited.add(up)
  23.                     down = self.down(cur, i)
  24.                     if down not in visited:
  25.                         queue.append(down)
  26.                         visited.add(down)
  27.             depth += 1
  28.         return -1
  30.     def up(self, s, i):
  31.         """将字符串s的第i个元素向上拨动一位，并返回拨动后的字符串"""
  32.         s_list = list(s)
  33.         if s_list[i] == '9':
  34.             s_list[i] = '0'
  35.         else:
  36.             s_list[i] = str(int(s_list[i])+1)
  37.         return "".join(s_list)
  39.     def down(self, s, i):
  40.         """将字符串s的第i个元素向下拨动一位，并返回拨动后的字符串"""
  41.         s_list = list(s)
  42.         if s_list[i] == '0':
  43.             s_list[i] = '9'
  44.         else:
  45.             s_list[i] = str(int(s_list[i])-1)
  46.         return "".join(s_list)

迷宫

  1. mete = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  2.         [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
  3.         [1, 0, 0, 1, 0, 1, 0, 1, 0, 1],
  4.         [1, 0, 1, 0, 0, 0, 0, 1, 0, 1],
  5.         [1, 0, 1, 0, 1, 0, 1, 1, 0, 1],
  6.         [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
  7.         [1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
  8.         [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
  11. class Solution(object):
  12.     # 方法一：深度优先，但是不是最优解
  13.     def dfs_stack(self, start, end, mete):
  14.         stack = [start]
  15.         while stack:
  16.             now = stack[-1]
  17.             if now == end:
  18.                 print(stack)
  19.                 return True
  20.             x, y = now
  21.             mete[x][y] = 2
  22.             if mete[x - 1][y] == 0:
  23.                 stack.append([x - 1, y])
  24.                 continue
  25.             elif mete[x][y - 1] == 0:
  26.                 stack.append([x, y - 1])
  27.                 continue
  28.             elif mete[x + 1][y] == 0:
  29.                 stack.append([x + 1, y])
  30.                 continue
  31.             elif mete[x][y + 1] == 0:
  32.                 stack.append([x, y + 1])
  33.                 continue
  34.             else:
  35.                 stack.pop()
  36.         return False
  38.     # 方法二：广度优先，最优解
  39.     def bfs_queue(self, start, end, mete):
  40.         def dfs(next_x, next_y):
  41.             if mete[next_x][next_y] == 0:
  42.                 queue.append([next_x, next_y, len(tmp) - 1]) # 如果不统计路径，这个len(tmp) - 1就没用
  43.                 mete[next_x][next_y] = 2
  45.         x1, y1 = start
  46.         queue = [[x1, y1, -1]]  # 如果不统计路径，这个1就没用
  47.         mete[x1][y1] = 2
  48.         tmp = []
  49.         while queue:
  50.             now = queue.pop(0)
  51.             tmp.append(now)
  53.             if now[0:2] == end:
  54.                 # 这段代码统计路径路径
  55.                 # path = []
  56.                 # i = len(tmp) - 1
  57.                 # while i >= 0:
  58.                 #     path.append(tmp[i][0:2])
  59.                 #     i = tmp[i][2]
  60.                 # path = path[::-1]
  61.                 # print(path)
  62.                 return True
  64.             dfs(now[0] - 1, now[1])
  65.             dfs(now[0], now[1] + 1)
  66.             dfs(now[0] + 1, now[1])
  67.             dfs(now[0], now[1] - 1)
  68.         else:
  69.             return False
  72. start = [1, 1]
  73. end = [6, 8]
  74. A = Solution()
  75. print(A.bfs_queue(start, end, mete))
  76. print(A.dfs_stack(start, end, mete))