基本模板:BFS on tree
# Init
q = deque([root]) # 用作 queue
# loop
while q: # 当 q 不为空
node = q.popleft() # 当前节点
# 对当前节点进行操作
# 遍历子节点:
# append 到 q
要点
popleft()
之后基本模板的变体
# Init
## 处理 root
q = deque([root]) # 用作 queue
# loop
while q: # 当 q 不为空
node = q.popleft() # 当前节点
# 遍历子节点:
# 对当前子节点进行操作
# append 到 q
要点
进阶 1,分层遍历
# Init
q = deque([root]) # 用作 queue
layer = 0 #!! 当前层 index
# loop
while q: # 当 q 不为空
for _ in range(len(q)): #!! index `_` 不重要
node = q.popleft() # 当前节点
# 对当前节点进行操作
# 遍历子节点:
# append 到 q
layer += 1 #!! 层 index 加一
要点
for
循环(all iterations) 都是完整的一层for
循环(all iterations) q 里面存着下一层的全部节点进阶 2,图上的 BFS,加入查重
# Init
q = deque([root]) # 用作 queue
qed = set(q) #!! 用于记录进入过 q 的节点
layer = 0 # 当前层 index
# loop
while q: # 当 q 不为空
for _ in range(len(q)): # index `_` 不重要
node = q.popleft() # 当前节点
# 对当前节点进行操作
# 遍历子节点:
if 子节点 not in qed: #!! 之前是否进入过 q
# append 到 q
#!! add 到 qed
layer += 1 # 层 index 加一
要点
进阶 3, Topology sorting
# 定义
graph = dict() #!! key: node label, value [label of neighbors dicts]
indegree = dict() #!! key: node label, value int indegree
# 初始化
q = deque([]) #!! 中包含所有indegree == 0 的 node
# BFS loop
while q: # 当 q 不为空
node = q.popleft() # 当前节点
# 对当前节点进行操作, 记述或者记录
# 遍历子节点 nei:
indegree[nei] -= 1 #!! 入度减一
if indegree[nei] == 0: #!! 如果入度已经减为零
q.append(nei) # append 到 q
要点