理论基础

BFS的对象是一张或多张图，可能是邻接表或邻接矩阵等数据结构表示的图，也可能是由状态间的逻辑关系构成的抽象的图。

BFS一般用途：联通区域、最短路径、最少操作、模拟广度过程（病毒传播、火势蔓延等）。

技巧与优化

• 可以用双端队列记录遍历的节点。
• 需要区分不同层的结果或无法使用双端队列（例如每层需要排序或去重）时，可以用两个容器轮替充当当前层和下一层。对于Python这种全是引用的语言，可以用一个临时容器储存下一层结果，再cur_level = next_level即可。
• 双向BFS可以优化时间复杂度。

最短路径

LC 127. 单词接龙

求最短接龙路径长度。需要优化建图，加入连接到真实单词的虚拟节点，不然建图时间复杂是O(n)。可以双向BFS。

LC 126. 单词接龙 II

求所有的最短接龙路径。记录最短路径上的节点。需要优化建图。不可以双向BFS。DFS回溯得到所有的最短路径。

最少操作

用BFS求最少操作一般用于有多个结果都是最少操作的情况，此时搜索的是不同步数的操作得到的各个状态构成的抽象的图。

LC 301. 删除无效的括号

每一层为上一层操作的所有结果，需要去重，每一次操作为删除一个括号。