BFS技巧

2020-08-28

关于BFS的思考

在蓝桥杯的考试中，有几道经典的BFS例题，可以先从里面入手

本题可以说是BFS入门题，由于BFS的特性是一层一层的搜，那么我们总可以求出最短路径，按照这个思想，我们可以写出以下代码

public class Main {

    private  static String []d={"D","L","R","U"};
    private static char  [][]grid=new char[30][50];
    private static  boolean [][]vis=new boolean [60][60];
    public static void main(String[] args) throws FileNotFoundException {

        String s = "01010101001011001001010110010110100100001000101010"
                + "00001000100000101010010000100000001001100110100101"
                + "01111011010010001000001101001011100011000000010000"
                + "01000000001010100011010000101000001010101011001011"
                + "00011111000000101000010010100010100000101100000000"
                + "11001000110101000010101100011010011010101011110111"
                + "00011011010101001001001010000001000101001110000000"
                + "10100000101000100110101010111110011000010000111010"
                + "00111000001010100001100010000001000101001100001001"
                + "11000110100001110010001001010101010101010001101000"
                + "00010000100100000101001010101110100010101010000101"
                + "11100100101001001000010000010101010100100100010100"
                + "00000010000000101011001111010001100000101010100011"
                + "10101010011100001000011000010110011110110100001000"
                + "10101010100001101010100101000010100000111011101001"
                + "10000000101100010000101100101101001011100000000100"
                + "10101001000000010100100001000100000100011110101001"
                + "00101001010101101001010100011010101101110000110101"
                + "11001010000100001100000010100101000001000111000010"
                + "00001000110000110101101000000100101001001000011101"
                + "10100101000101000000001110110010110101101010100001"
                + "00101000010000110101010000100010001001000100010101"
                + "10100001000110010001000010101001010101011111010010"
                + "00000100101000000110010100101001000001000000000010"
                + "11010000001001110111001001000011101001011011101000"
                + "00000110100010001000100000001000011101000000110011"
                + "10101000101000100010001111100010101001010000001000"
                + "10000010100101001010110000000100101010001011101000"
                + "00111100001000010000000110111000000001000000001011"
                + "10000001100111010111010001000110111010101101111000";

        //首先我们将其映射为二维矩阵
        for(int i=0;i<30;i++){
            for(int j=0;j<50;j++){
                grid[i][j]=s.charAt(0);
                s=s.substring(1);
            }
        }
        bfs();
    }
    private static void bfs(){
        Queue<State>queue=new LinkedList<>();
        int dx[]={-1,0,1,0};
        int dy[]={0,1,0,-1};
        //首先将入口入队
        queue.add(new State(0,0,0,""));
        vis[0][0]=true;
        while(!queue.isEmpty()){
            State cur=queue.poll();
            //到达终点的条件即为到达右下角
            if(cur.x==29&&cur.y==49){
                System.out.println(cur.path);
                System.out.println(cur.step);
            }
            for(int i=0;i<4;i++){
                int a=cur.x+dx[i],b=cur.y+dy[i];
                if(check(a,b)){
                    queue.add(new State(a,b,cur.step+1,cur.path+d[i]));
                    vis[a][b]=true;
                }
            }
        }

    }
    //表示a，b如何才能入队， 首先不能超过边界，其次没有被访问，最后不是障碍物。
    private static boolean check(int a,int b){
        if(a<0||a>=30||b<0||b>=50||vis[a][b]||grid[a][b]=='1') return false;
        return true;
    }

}
class State{
    int x;
    int y;
    int step;
    String path;

    public State(int x, int y, int step, String path) {
        this.x = x;
        this.y = y;
        this.step = step;
        this.path = path;
    }
}

下面说一下BFS框架

void BFS(){
    Queue<Node>queue=new LinkedList<>();
    //这里用于标记，一般情况下其实set更为常见
    boolean []vis=new boolean[];
     queue.add(start);
    vis[start]=true;
    //记录步数
    int step=0;
    while(!queue.isEmpty()){
        int sz=queue.size();
        //将当前队列中的所有节点向四周扩散
        for(int i=0;i<sz;i++){
            Node cur=queue.poll();
            //判断是否到达终点,此时一定是最短路径
            if(cur==target) return step;
            //将cur相邻的节点加入到队列中
            for(Node node:cur.next()){
                //先判断是否可以进入队列
                if(!vis[node]) queue.add(node);
                vis[node]=true;
            }
        }
        //这里代表搜完了一层，我们应该更新步数
        step++;
    }
}

以上情况适用于图的BFS遍历，但是相对于树来说，应该更为简单，其中vis在大部分时候都是必须的，但是像一般的二叉树结构，因为只有父亲指向儿子，并没有儿子指向父亲的节点，那么一般来说我们不需要对其进行标记。

下面讲一道关于树的经典BFS遍历

Leetcode102、二叉树的层序遍历 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
         List<List<Integer>>res=new ArrayList<>();
        if(root==null) return res;
        Queue<TreeNode> queue=new LinkedList<>();
           queue.add(root);
        while(!queue.isEmpty()){
            List<Integer>list=new ArrayList<>();
            int sz=queue.size();
            for(int i=0;i<sz;i++){
                TreeNode cur=queue.poll();
                list.add(cur.val);
                //这里代表将cur相邻的节点加入到队列中
                if(cur.left!=null) queue.add(cur.left);
                if(cur.right!=null) queue.add(cur.right);
            }
            //这里更新结果，即将list加到答案里
            res.add(new ArrayList<>(list));
        }
        return res;
    }
}

或许通过这一道例题，只是简单的按层进行了遍历，并不能给你直观带来BFS求最短路径的感受，那么接下来通过一道题来求解最短路径

class Solution {
    public int minDepth(TreeNode root) {
            if(root==null) return 0;
           Queue<TreeNode>queue=new LinkedList<>();
          queue.add(root);
        int depth=1;
        while(!queue.isEmpty()){
            int sz=queue.size();
            for(int i=0;i<sz;i++){
                TreeNode cur=queue.poll();
                if(cur.left==null&&cur.right==null) return depth;
                if(cur.left!=null) queue.add(cur.left);
                if(cur.right!=null) queue.add(cur.right);
            }
            depth++;
        }
        return depth;
    }
}

BFS的逻辑就是，depth每增加一次，队列中的所有节点都向前迈一步，这就保证了第一次到达终点时，走的步数是最少的。

即BFS可以借助队列做到一次一步，齐头并进的感觉，相对于DFS来说，可以在不遍历完整棵树的情况下找到最短距离。

青蛙跳杯子

import java.util.*;

public class Main {

    private  static String start;
    private static String target;
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
         start=input.nextLine();
         target=input.nextLine();
        bfs();
    }
    private static void bfs(){
        Queue<State> queue=new LinkedList<>();
        Set<String> set=new HashSet<>();
        queue.add(new State(start,0));
        set.add(start);
        while(!queue.isEmpty()){
            State cur=queue.poll();
            //表示到达终点
            if(cur.path.equals(target)) System.out.println(cur.step);
            String s=cur.path;
            char[]ch=s.toCharArray();
            //寻找*号位置
            int pos=0;
            while(ch[pos]!='*') pos++;
            //青蛙可以跳的范围，根据题意，为[-3,3]
            for(int i=-3;i<=3;i++){
                //不能原地不动，并且移动的范围要在字符串范围内
              if(pos+i>=0&&pos+i<s.length()&&i!=0){
                  swap(ch,pos,pos+i);
                  String newStr=new String(ch);
                  //跳完记得回溯
                  swap(ch,pos,pos+i);
                  if(!set.contains(newStr)){
                      queue.add(new State(newStr,cur.step+1));
                      set.add(newStr);
                  }
              }

            }

        }

    }
    private  static void swap(char c[],int i,int j){
        char temp=c[i];
        c[i]=c[j];
        c[j]=temp;
    }
}
class State{
    String path;
    int step;

    public State(String path, int step) {
        this.path = path;
        this.step = step;
    }
}

九宫重排

public class Main {

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String start=input.nextLine();
        String target=input.nextLine();
        //由于本题数据量特别小，这里运用了一个特别的技巧，将每个位置所能转换的位置枚举出来
        List<Integer>[]list=new List[]{Arrays.asList(1,3),Arrays.asList(0,2,4),Arrays.asList(1,5),
                Arrays.asList(0,4,6),Arrays.asList(1,3,5,7),Arrays.asList(2,4,8),
                Arrays.asList(7,3),Arrays.asList(4,6,8),Arrays.asList(5,7)};
        Queue<String>queue=new LinkedList<>();
        queue.add(start);
        Set<String>set=new HashSet<>();
        set.add(start);
        int step=0;
        while(!queue.isEmpty()){
            int sz=queue.size();
            for(int i=0;i<sz;i++){
                String cur=queue.poll();
                if(cur.equals(target)){
                    System.out.println(step);
                    break;
                }
                char []ch=cur.toCharArray();
                int pos=0;
                while(ch[pos]!='.')pos++;
                for(int index:list[pos]){
                    swap(ch,index,pos);
                    String newStr=new String(ch);
                    swap(ch,index,pos);
                    if(!set.contains(newStr)){
                        queue.add(newStr);
                        set.add(newStr);
                    }
                }
            }
            step++;
        }

    }
    private static void swap(char []c,int i,int j){
        char temp=c[i];
        c[i]=c[j];
        c[j]=temp;
    }
}

以上的青蛙跳杯子以及九宫重排，本质上属于同一类题，但是这里运用了两种不同的写法来进行。

一种是利用面向对象的思想，我们自己定义一个节点类，这样可以将每次的路径和步数传进去。而第二种写法则是利用最开始的模板，每当我们更新完一层，那么就更新结果为步数+1。