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 ArrayDeque<TreeNode>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        List<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

public List<List<Integer>> levelOrder(TreeNode root) {
    List result = new ArrayList();
    
    if (root == null) {
        return result;
    }
    
    List<TreeNode> queue = new ArrayList<TreeNode>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        List<TreeNode> nextQueue = new ArrayList<TreeNode>();
        result.add(queue);

        for (TreeNode head : queue) {
            if (head.left != null) {
                nextQueue.offer(head.left);
            }
            if (head.right != null) {
                nextQueue.offer(head.right);
            }
        }
        queue = nextQueue;
    }
    
    return result
}

DummyNode

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

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

0,#,1,2,#,3,4,5,6,#

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

public List<List<Integer>> levelOrder(TreeNode root) {
    List result = new ArrayList();
    
    if (root == null) {
        return result;
    }
    
    Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
    queue.offer(root);
    queue.offer(null);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node == null) {
            if (queue.size() == 0) {
                break;
            }
            result.add(level);
            level = new ArrayList<Integer>();
            queue.offer(null);
            continue;
        }
        level.add(node.val);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    
    return result
}