BFS算法套路框架

广度优先搜素（BFS）和深度优先搜素(DFS)是图遍历的两种经典算法，DFS是向下越来越深入，而BFS就是四处扩散越来越开拓。

BFS应用场景：找到从起点到终点的最近距离。

框架套路：

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路
    
    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        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 (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
            }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

cur.adj()表示与当前结点相连的节点。

visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要 visited。

题目：

111. 二叉树的最小深度 (opens new window)

752. 打开转盘锁 (opens new window)

二叉树的最小深度

题目：

思想：

最小深度其实可以使用递归来解决，但是这里我们就使用BFS。那么题目条件如何转为最短路径呢？最小深度就是根节点到叶节点最短路径。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 当前节点能够连接的节点队列
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        int depth = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                // 当前节点
                TreeNode current = queue.poll();
                // 如果是叶节点
                if(current.left == null && current.right == null) {
                    return depth;
                }
                // 将当前节点所连接的节点加入节点队列
                if(current.left != null) {
                    queue.offer(current.left);
                }
                if(current.right != null) {
                    queue.offer(current.right);
                }
            }
            depth++;
        }
        return depth;
    }
}

打开转盘锁

题目：

思想：

这个类似我们的密码箱，有四个位置，然后每次调整一个位置，且一个位置的数字只能跳转一次。相当于我们在这种情况下要找最快解密的方法，且同时在解密的过程中要避免死亡字符串。

我们把每一个字符串当作一个节点，那么它相邻的节点是什么？

比如0000,就有8个相邻的节点：0001，0010，0100，1000，9000，0900，0090，0009。前四个是向上调整,后四个是向下调整。

这样我们就可以每次遍历一个节点之后，把该节点的相邻节点（无重复节点）添加到节点队列，使用模板即可。

代码：

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> deadensList = new HashSet<>();
        // 所有死亡字符串加入set集合
        deadensList.addAll(Arrays.asList(deadends));
        // 当前节点队列
        Queue<String> queue = new LinkedList<>();
        // 访问过的节点队列
        Set<String> visited = new HashSet<>();
        queue.offer("0000");
        visited.add("0000");
        int step = 0;

        while(!queue.isEmpty()) {
            // 当前队列的大小
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                // 当前的字符串
                String current = queue.poll();
                // 避开所有死亡字符串
                if(deadensList.contains(current)) {
                    continue;
                }
                if(current.equals(target)) {
                    return step;
                }
                // 将临近的节点加入节点队列
                for(int j = 0; j < 4; j++) {
                    // 向上的四个临近节点
                    String upStr = up(current, j);
                    if(!visited.contains(upStr)) {
                        queue.offer(upStr);
                        visited.add(upStr);
                    }
                    // 向下的四个临近节点
                    String downStr = down(current, j);
                    if(!visited.contains(downStr)) {
                        queue.offer(downStr);
                        visited.add(downStr);
                    }
                }

            }
            step++;
        }
        return -1;
    }

    /**
     * 向上调整
     */
    String down(String src, int j) {
        char[] ch = src.toCharArray();
        if(ch[j] == '0') {
            ch[j] = '9';
        } else {
            ch[j] -= 1;
        }
        return new String(ch);
    }

    /**
     * 向下调整
     */
    String up(String src, int j) {
        char[] ch = src.toCharArray();
        if(ch[j] == '9') {
            ch[j] = '0';
        } else {
            ch[j] += 1;
        }
        return new String(ch);
    }
}

参考

BFS 算法解题套路框架 (opens new window)