概述

典型BFS三层循环:

先明确队列中放的是什么，即满足怎样的条件才能入队。例如，拓扑排序入度为0的节点入队。

1. 队列不空, while queue

2. 分层遍历，for当前层的size。
   循环何时可省？ 不需要分层

3. 从当前点出发，向周围点去循环
      例如:拓扑排序去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 = []

图的遍历

层级遍历

由点及面

拓扑排序

Topological Sorting

矩阵上的宽搜