1.简介

BFS是Breadth First Search，中文翻译为宽度有限搜索。主要是出现在二叉树、数组（棋盘）和图（拓扑排序）中的宽度搜索。

---

2.适用场景

① 图的遍历 

图的遍历主要涉及层级遍历、连通性和拓扑排序3个方面。

层级遍历：是指可以将二叉数、数据和图分为多层，并按照每层元素的顺序进行遍历。

连通性：例如判断图是否连通，图的两个节点是否有可项链的路线。

拓扑排序 ：举例一个拓扑图是否可以根据需求，走出相应的路线，即为拓扑排序。

② 求简单图的最短路径 

简单图为无环和平行边的图。

可将图中的点分为多层，最短路径即为找到的target在第几层。

3.例题

题目

解析：

题解图示

根据二叉树序列化的数据，可以画出二叉树的结构，如上图所示。BFS的思路流程为遍历二叉树的每一层。第一次遍历level 0，将root根节点放入队列中，然后开始判断队列中是否有元素，有元素则执行相应的task（在本题中为记录使用过的颜色），执行完毕后，若左右子节点存在则添加至队列中，最后在将该节点pop出去。

---

代码：

```

/**

* Definition for a binary tree node.

* public class TreeNode {

*    int val;

*    TreeNode left;

*    TreeNode right;

*    TreeNode(int x) { val = x; }

* }

*/

class Solution {

    public int numColor(TreeNode root) {

        Set<Integer> numSet = new HashSet<Integer>();

        if (root == null) {

            return numSet.size();

        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        queue.offer(root);

        while (!queue.isEmpty()) {

            int queueSize = queue.size();

            for (int i = 0; i < queueSize; i++) {

                TreeNode node = queue.poll();

                numSet.add(node.val);

                if(node.left != null){

                    queue.offer(node.left);

                }

                if(node.right != null){

                    queue.offer(node.right);

                }

            }

        }

        return numSet.size();

    }

}

```