概述
典型BFS三层循环:
先明确队列中放的是什么，即满足怎样的条件才能入队。例如，拓扑排序入度为0的节点入队。
-
队列不空, while queue
-
分层遍历，for当前层的size。
循环何时可省？ 不需要分层 -
从当前点出发，向周围点去循环
例如:拓扑排序去for循环遍历当前点的邻居节点。
循环何时可省？ 二叉树层序遍历，周围点只可能有左右孩子，无需for循环。node.left, node.right分别看一眼即可。
宽搜要点
-
使用队列为主要数据结构Queue
-
是否需要分层实现：分层打印多一层for循环，len(queue)缓存队列每一层大小。
-
for _ range(len(queue)): 错，需缓存
二叉树上的宽搜
Binary Tree Level Order Traversal
Binary Tree Zigzag Level Order Traversal
Serialize and Deserialize Binary Tree
序列化是指将内存中的数据结构转为字符串的过程。系列化：object -> string；反序列化: string -> object。
图上的宽搜
图上的宽搜与树的区别：图有环，同一节点可能重复进入队列。需用集合存储访问过的结点。queue.append与visited.add成对存在。
数据结构：队列 + 集合
- 图如何存储？ 临接点
class GraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []