【队列应用】Breadth First Search (BFS) 宽度优先搜索

Breadth First Search (BFS) 宽度优先搜索，顾名思义，搜索的过程是平铺开进行搜索，即从起点开始，将所有相邻的节点都搜索一遍，然后再搜索这些相邻节点的相邻节点，一层一层铺开。其搜索过程就像水中的涟漪，从中心开始，向四周进行扩散，直到遍历完。有兴趣可查看历史文章

img

之前有很多题都是以递归实现算法，今天讲的是结合队列实现。正如上面所说的，需要将所有和它相邻的节点都搜索一遍，再搜索相邻的相邻节点。这个过程与队列的FIFO是完全契合的。实现过程也非常直接：

• 起始：将起点（起点[0,0]，树的根节点）放入队列中

• 扩散：从队列中取出头节点，将它的相邻结点放入队列，不断重复这一步

  值得注意的是，不同算法从队列中取出数据的终止条件是不同的，需要小心总结。

  1. 可以是直接依赖队列是否为空来判断

     while (!q.isEmpty()) {
       //...
       q.offer();
       //...
     }

  2. 需要依赖当前队列的长度来遍历

     while (!q.isEmpty()) {
       int sz = q.size();
       while (sz-- > 0) {
         //...
         q.offer();
         //...
       }
     }

• 终止：当队列为空时，说明我们遍历了所有的结点，整个图都被搜索了一遍

动图示例

下图是《934. Shortest Bridge》的计算过程中第一步，获取二维数组中的一座岛。

1. 起点[0,0]入队；
2. 队列长度为1，从队列中取出一个，获得[0,1]、[1,0]入队；
3. 队列长度为2，分别出队后获得[1,1]、[2,0]入队；
4. 队列长度为2，分别出队后获得[3,0]入队；
5. 出队后队列为空，得到完整的岛信息。

queue-bfs-gif