概述

典型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

矩阵上的宽搜

Comments