5.2　广度优先遍历

相对于DFS来说，BFS的变种比较少，能解决的问题种类比较单一。

BFS比较适合用来找最短距离，因此如果题目中提到了最短距离，首先应该想到使用BFS。

使用BFS进行解题的思路同样是定义起始节点和结束节点，从起点开始不断深入其他节点，在搜索的过程中判断是否满足特定条件。BFS和DFS只是遍历的方向不同，即上面提到的DFS是尽可能深地搜索树的分支，而BFS则是一层一层地访问节点。队列可以帮我们实现“一层一层地访问节点”的效果。其本质就是不断访问邻居，把邻居逐个加入队列，根据队列先进先出的特点，把每一层节点访问完后，会继续访问下一层节点。

伪代码如下。

小提示：如果是在带权图上进行BFS，则可以考虑使用优先队列来完成。

接下来，我们通过力扣（LeetCode）中的路径和问题、岛屿和问题来详细讲解DFS和BFS的思路。