广度优先遍历

「广度优先遍历」在直观上是「声波」「水波」的传播。「广度优先遍历」的一个重要作用是：寻找无权图的单元最短路径。

重点概括

• 「广度优先遍历」与「深度优先遍历」一样，都是遍历的方式，很多「树」的问题也可以使用「广度优先遍历」解决；
• 「广度优先遍历」像水波纹、声波一样，每一层「同时」向外扩散；
• 「广度优先遍历」可以用于求解 无权图的最短路径；
• 「拓扑排序」的一种经典实现就是「广度优先遍历」。

题号	链接	题解
剑 13	机器人的运动范围 (opens new window)（中等）	深度优先遍历、广度优先遍历 (opens new window)
207	课程表 (opens new window)（中等）	拓扑排序、深度优先遍历 (opens new window)
210	课程表 II (opens new window)（中等）	拓扑排序（广度优先遍历） + 深度优先遍历（Java、Python） (opens new window)
993	二叉树的堂兄弟节点 (opens new window)（中等）	深度优先遍历、广度优先遍历 (opens new window)
690	员工的重要性 (opens new window)（简单）	深度优先遍历、广度优先遍历（Java、Python） (opens new window)
1306	跳跃游戏 III (opens new window)（中等）	广度优先遍历 (opens new window)
365	水壶问题 (opens new window)（中等）	图的广度优先遍历（Java） (opens new window)
127	单词接龙 (opens new window)（中等）	广度优先遍历、双向广度优先遍历（Java、Python） (opens new window)
126	单词接龙 II (opens new window)（困难）	单双向广度优先遍历 + 回溯算法（Java、Python） (opens new window)

树的广度优先遍历的一些问题、LeetBook 里的一些问题。

---

作者：liweiwei1419 链接：https://suanfa8.com/breadth-first-search 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。