BFS 的核⼼思想应该不难理解的，就是把⼀些问题抽象成图，从⼀个点开始，向四周开始扩散。⼀般来说，我们写 BFS 算法都是⽤「队列」这种数据结构，每次将⼀个节点周围的所有节点加⼊队列。
BFS 相对 DFS 的最主要的区别是： BFS 找到的路径⼀定是最短的，但代价 就是空间复杂度⽐ DFS ⼤很多。
BFS算法框架：
# 计算从起点 start 到终点 target 的最近距离
def BFS(start, target):
q = [] # 核⼼数据结构
visited = set() # 避免走回头路
q.append(start) # 将起点加⼊队列
visited.add(start)
step = 0 # 记录扩散的步数
while q:
n = len(q)
# 将当前队列中的所有节点向四周扩散
for i in range(n):
cur_node = q.pop()
# 划重点：这⾥判断是否到达终点
if cur_node is target:
return step
# 将 cur 的相邻节点加⼊队列
for x in cur_node.child: # 此处省略简写
if x not in visited:
q.append(x)
visited.add(x)
# 划重点：更新步数在这⾥
step += 1
队列 q 是BFS 的核⼼数据结构；cur_node .child 泛指 cur_node 相邻的节点，⽐如说⼆维数组中， cur_node 上下左右四⾯的位置就是相邻节点； visited 的主要作⽤是防⽌⾛回头路，⼤部分时候都是必须的，但是像⼀般的⼆叉树结构，没有⼦节点到⽗节点的指针，不会⾛回头路就不需要
visited 。
⼆叉树的最⼩⾼度
示例代码：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
queue = collections.deque([(root, 1)])
while queue:
node, depth = queue.popleft()
if (not node.left) and (not node.right):
return depth
if node.left:
queue.append((node.left, depth+1))
if node.right:
queue.append((node.right, depth+1))
return depth解开密码锁的最少次数
详见博文：打开转盘锁_IT之一小佬的博客
示例代码：
from collections import deque
class Solution(object):
def openLock(self, deadends, target):
# 如果target是'0000'则不需要拨动 返回0
if target == "0000":
return 0
dead = set(deadends)
if "0000" in dead:
return -1
def num_up(x, i):
lst = list(x)
if lst[i] == "9":
lst[i] = "0"
else:
lst[i] = str(int(lst[i]) + 1)
return "".join(lst)
def num_down(x, i):
lst = list(x)
if lst[i] == "0":
lst[i] = "9"
else:
lst[i] = str(int(lst[i]) - 1)
return "".join(lst)
step = 0 # 拨动次数 初始时没拨所以次数为0
queue = deque()
visited = set() # 存放已经比较过的字符组合、死亡数字组合 避免死循环
visited.update(deadends) # 初始化为死亡数字组合
queue.append("0000")
while queue:
length = len(queue) # 按层处理队列中的字符串
for i in range(length):
cur = queue.popleft() # 当前处理的节点
if cur in visited: # 当前节点已经处理过或属于死亡数字组合 所以跳过
continue
else:
visited.add(cur) # 首次比较 加入已经处理的集合
# 判断是否满足终止条件
if cur == target:
return step
# 不满足终止条件将所有相邻的节点加入队列
for j in range(4): # cur的每位数都可以上拨或下拨 这些都是cur的相邻节点
up = num_up(cur, j)
# 需要判断上拨、下拨后的组合是否合法（在不在visited里） 不合法就跳过
if up not in visited:
queue.append(up)
down = num_down(cur, j)
if down not in visited:
queue.append(down)
# 每循环一遍是一次拨动 次数要+1
step += 1
# 所有可能都穷举后无法达到target说明不能解锁 返回-1
return -1
deadends = ["0201", "0101", "0102", "1212", "2002"]
target = "0202"
obj = Solution()
ans = obj.openLock(deadends, target)
print(ans)
