BFS

BFS适用场景

1. 分层遍历
   • 一层一层的遍历一个图、树、矩阵
   • 简单图最短路径（边长都为1）
2. 连通块问题
   • 连通图中一个点找到其他所有连通的点
   • 找到所有方案问题的一种非递归实现方式
3. 拓扑排序
   • 实现容易度远超过DFS

BFS的三种实现方式

通过二叉树层次遍历为例

单队列

实现最简单和标准

public List<List<Integer>> levelOrder(TreeNode root) {
    List result = new ArrayList();
    
    if (root == null) {
        return result;
    }
    
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    
    while (!queue.empty()) {
        ArrayList<Integer> level = new ArrayList<Integer>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode head = queue.poll();
            level.add(head.val);
            if (head.left != null) {
                queue.offer(head.left);
            }
            if (head.right != null) {
                queue.offer(head.right);
            }
        }
        result.add(level);
    }
    
    return result
}

双队列

（效率比单队列低，因为这个）

Queue、nextQueue

下一层的放入nextQueue

DummyNode

链表中为避免删除和插入头结点的特判

在bfs中用来区分不同的层级，区分各层

优点：可以减少for循环嵌套层数