1. import collections
    2. def BFS(root, target):
    3.     queue = collections.deque() # 所有节点将会被放入队列等待被处理
    4.     step = 0
    5.     queue.append(root)
    7.     # BFS
    8.     while len(queue) != 0:
    9.         step += 1
    10.         # 迭代所有已经存在队列中的节点
    11.         size = len(queue)
    12.         for i in range(size):
    13.             cur = the first node in queue
    14.             return step if cur is target
    15.             while cur.next:
    16.                 add next to queue
    17.             remove cur from queue

    模板二：利用哈希表来解决不会访问一个节点两次

    1. import collections
    2. def BFS(root, target):
    3.     queue = collections.deque() # 所有节点将会被放入队列等待被处理
    4.     hash_set = {} # 记录已经访问过的，visited，
    5.     step = 0 # 记录扩散的步数
    6.     queue.append(root) # 将起点加入队列
    8.     # BFS
    9.     while len(queue) != 0:
    10.         step += 1
    11.         # 迭代所有已经存在队列中的节点
    12.         size = len(queue)
    13.         # 将当前队列中的所有节点向四周扩散
    14.         for i in range(size):
    15.             cur = the first node in queue
    16.             return step if cur is target # 判断是否到达终点
    17.             # 将相邻节点加入队列
    18.             while cur.next:
    19.                 if cur not in hash_set:
    20.                     add next to queue
    21.                     add next to used
    22.             remove cur from queue