BFS模板-526互联

#class Solution:
#     def BFS(self, start, target):
#         q = []  # 用一个列表做队列
#         v = []  # 记录走过的路
#         q.append(start)  # 把起点放入队列
#         v.append(start)  #加入走过的路
#         step = 0  # 记录扩散步数
#         while q:  # 当队列不为空时
#             size = len(q)
#             # 将当前队列中的所有节点向四周扩散
#             for _ in range(size):
#                 cur = q.pop(0)  # 从头部取出节点
#                 if cur == target:  # 判断是否到达终点
#                     return step
#                 for x in cur.neighbors:  # 将cur的相邻节点加入队列
#                     if x not in v: #如果结点没有访问过
#                         q.append(x)
#                         v.append(x)
#             step += 1  # 增加步数