广度优先遍历(BFS)算法框架

DFS算法可以被认为是回溯算法，BFS算法出现的场景：在一副图中找到从起点 start到终点 target 的最近距离。比如两个单词通过替换某些字母，把其中一个变为另一个，每次只能替换一个字母。下面是BFS的算法伪代码：

// 计算从起点 start 到终点 target 的最近距离
int DFS(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;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 泛指与cur相邻的节点，整个代码可以描述成为了计算起点和终点的最近距离，从根节点开始遍历整个结构，使用队列q来存储每次的节点，step存储进行的步数。遍历的过程，将cur的相邻的点加入到队列里面， 如果达到了设置的终止条件，就返回，否则就继续step计数。

为什么要用队列存储？因为本质上树的节点，用linkedlist存储的。

二叉树的最小高度:

int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>(); 
  //说明: Java的Queue是一个接口,LinkedList实现了Queue的接口，因此不用强制转型。如果给的是ArrayList则必须强制转型。例如Queue<Integer> qq = (Queue<Integer>) new ArrayList<Integer>();
    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) //二叉树中的相邻节点就是left和right
                q.offer(cur.left);
            if (cur.right != null) 
                q.offer(cur.right);
        }
        /* 这里增加步数 */
        depth++;
    }
    return depth;
}

解开密码锁的次数

int openLock(String[] deadends, String target) {
    // 记录需要跳过的死亡密码
    Set<String> deads = new HashSet<>();
    for (String s : deadends) deads.add(s);
    // 记录已经穷举过的密码，防止走回头路
    Set<String> visited = new HashSet<>();
    Queue<String> q = new LinkedList<>();
    // 从起点开始启动广度优先搜索
    int step = 0;
    q.offer("0000");
    visited.add("0000");
    
    while (!q.isEmpty()) {
        int sz = q.size();
        /* 将当前队列中的所有节点向周围扩散 */
        for (int i = 0; i < sz; i++) {
            String cur = q.poll();
            
            /* 判断密码是否合法，是否到达终点 */
            if (deads.contains(cur))
                continue;
            if (cur.equals(target))
                return step;
            
            /* 将一个节点的未遍历相邻节点加入队列 */
            for (int j = 0; j < 4; j++) {
                String up = plusOne(cur, j);
                if (!visited.contains(up)) {
                    q.offer(up);
                    visited.add(up);
                }
                String down = minusOne(cur, j);
                if (!visited.contains(down)) {
                    q.offer(down);
                    visited.add(down);
                }
            }
        }
        /* 在这里增加步数 */
        step++;
    }
    // 如果穷举完都没找到目标密码，那就是找不到了
    return -1;
}

可以使用双向 BFS 算法来提高效率，代码稍加修改即可：

int openLock(String[] deadends, String target) {
    Set<String> deads = new HashSet<>();
    for (String s : deadends) deads.add(s);
    // 用集合不用队列，可以快速判断元素是否存在
    Set<String> q1 = new HashSet<>();
    Set<String> q2 = new HashSet<>();
    Set<String> visited = new HashSet<>();
    // 初始化起点和终点
    q1.add("0000");
    q2.add(target);
    int step = 0;
    
    while (!q1.isEmpty() && !q2.isEmpty()) {
        // 哈希集合在遍历的过程中不能修改，
        // 用 temp 存储 q1 的扩散结果
        Set<String> temp = new HashSet<>();

        /* 将 q1 中的所有节点向周围扩散 */
        for (String cur : q1) {
            /* 判断是否到达终点 */
            if (deads.contains(cur))
                continue;
            if (q2.contains(cur))
                return step;
            visited.add(cur);

            /* 将一个节点的未遍历相邻节点加入集合 */
            for (int j = 0; j < 4; j++) {
                String up = plusOne(cur, j);
                if (!visited.contains(up))
                    temp.add(up);
                String down = minusOne(cur, j);
                if (!visited.contains(down))
                    temp.add(down);
            }
        }
        /* 在这里增加步数 */
        step++;
        // temp 相当于 q1
        // 这里交换 q1 q2，下一轮 while 就是扩散 q2
        q1 = q2;
        q2 = temp;
    }
    return -1;
}