6. BFS

Template

// BFS问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q = new LinkedList<>(); // 核心数据结构
    Set<Node> visited = new HashMap<>(); // 避免走回头路
    
    q.offer(start); // 将起点加入队列
    visited.add(start);

    while (!queue.isEmpty()) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj()) {
                if (!visited.contains(x) {
                    q.offer(x);
                    visited.add(x);
                }
            }
        }
    }
    // 如果走到这里，说明在图中没有找到目标节点
}

Typical problems

• Binary tree min depth

//Calculate the minimum depth of a tree
int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    // root 本身就是一层，depth 初始化为 1
    int depth = 1;
    
    while (!q.isEmpty()) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            /* 判断是否到达终点 */
            if (cur.left == null && cur.right == null) 
                return depth;
            /* 将 cur 的相邻节点加入队列 */
            if (cur.left != null)
                q.offer(cur.left);
            if (cur.right != null) 
                q.offer(cur.right);
        }
        /* 这里增加步数 */
        depth++;
    }
    return depth;
}

• Open the lock

public int openLock(String[] deadends, String target) {
    Set<String> dead = new HashSet<>();
    for (String d : deadends) dead.add(d);

    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();

    int depth = 0;
    String marker = "0000";

    if (dead.contains(marker)) return -1;

    queue.offer(marker);
    visited.add(marker);

    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size > 0) {
            String lockPosition = queue.poll();
            if (lockPosition.equals(target)) {
                return depth;
            }

            for (int i = 0; i < 4; i++) {
                char c = lockPosition.charAt(i);
                String s1 = lockPosition.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + lockPosition.substring(i + 1);
                String s2 = lockPosition.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + lockPosition.substring(i + 1);

                if (!visited.contains(s1) && !dead.contains(s1)) {
                    queue.offer(s1);
                    visited.add(s1);
                }
                if (!visited.contains(s2) && !dead.contains(s2)) {
                    queue.offer(s2);
                    visited.add(s2);
                }
            }
            size--;
        }
        depth++;
    }

    return -1;
}