BFS

何时应用BFS

• 图的遍历

  • 层级遍历 ---- level order traversal

  • 由点及面 ---- clone graph, number of islands

  • 拓扑排序 --- alien dictionary

• 简单图最短路径

  • word ladder

clone graph

word ladder

number of islands

Clone Graph

• 实际写的时候思路还是不够清晰，基本功需要多练

• BFS遍历每个Cur的neighbors

• 同时用一个Map来存node和CloneNode

• 对每个Cur.neighbor看是否在map里，如果在了就说明已经遍历过，不需要放到queue里

• 如果不在的话就需要新建一个cloneNeighbor并放到map里

• 最后把cloneNeighbor加入到cloneCur的neighbors

    public Node cloneGraph(Node node) {
        if (node == null) return null;

        Queue<Node> nodes = new LinkedList<>();
        nodes.add(node);

        Map<Node, Node> map = new HashMap<>(); //key is node, val is cloneNode
        map.put(node, new Node(node.val, new ArrayList<Node>()));

        while (!nodes.isEmpty()) {
            Node cur = nodes.poll();
            for (Node neighbor : cur.neighbors) {
                if (!map.containsKey(neighbor)) {
                    //add neighbor into map
                    map.put(neighbor, new Node(neighbor.val, new ArrayList<Node>()));
                    nodes.offer(neighbor);
                }
                //add cloneNeighbor into cloneCur
                map.get(cur).neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);
    }

DFS 解法

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> map  = new HashMap<>();
        return cloneNode(node, map);
    }

    private Node cloneNode(Node node, Map<Node, Node> map) {
        if (map.containsKey(node)) {
            return map.get(node);
        }

        Node cloneNode = new Node(node.val, new ArrayList<Node>());
        map.put(node, cloneNode);
        for (Node neighbor : node.neighbors) {
            Node cloneNeighbor = cloneNode(neighbor, map);
            map.put(neighbor, cloneNeighbor);
            cloneNode.neighbors.add(cloneNeighbor);
        }

        return cloneNode;
    }
}

Word Ladder

• 先想简单的BFS解法，寻找隐式图最短路径

• optimize: Bi-BFS

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> visited = new HashSet<>();
        HashSet<String> dict = new HashSet<>();
        for(int i = 0; i< wordList.size(); i++){
            dict.add(wordList.get(i));
        }
        if (!dict.contains(endWord)) return 0;
        Queue<String> q = new LinkedList<>();
        q.add(beginWord); //assume beginWord and endWord are not the same.
        visited.add(beginWord);
        
        int level =1;
        while(!q.isEmpty()){
            level++;
            int size = q.size();  
            for(int j=0; j< size; j++){
               String str = q.poll();
                for(int k = 0; k<str.length();k++){
                    char [] chars = str.toCharArray();
                    for(char c = 'a'; c <= 'z'; c++){   
                    chars [k] = c;
                    String word = new String(chars);
                    if(word.equals(endWord)&& dict.contains(word)){
                        return level;
                    }
                    if(dict.contains(word) && !visited.contains(word)){
                        q.add(word);
                        visited.add(word);
                        }
                    }
                }
            }
        }
        return 0;
    }
}

Number of island

• 矩阵类BFS的基础题，由点及面BFS

• 构建deltaX[ ] = {-1, 0, 0, 1}, deltaY = {0, -1, 1, 0}

• BFS Queue存什么？可以是tuple{x, y}, 也可以是val = x * cols + y。 x = val / cols, y = val % cols

• 还可以DFS, union find解

BFS解法

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        //坐标变换数组
        //x = [-1, 0 , 0 , 1]
        //y = [0, 1, -1, 0]
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] visited = new int[rows][cols];

        int num = 0;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == '1' && visited[row][col] == 0) {
                    bfs(grid, row, col, visited);
                    num++;
                }
            }
        }
        return num;
    }

    private void bfs(char[][] grid, int row, int col, int[][] visited) {
        //what to store into a queue? either a tuple object or x * rows + y
        Queue<Integer> queue = new LinkedList<>();
        int rows = grid.length;
        int cols = grid[0].length;
        queue.offer(row * cols + col);
        visited[row][col] = 1;

        int[] deltaX = {-1, 0 , 0 , 1};
        int[] deltaY = {0, 1, -1, 0};

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int x = cur / cols;
            int y = cur % cols;
            for (int i = 0; i < 4; i++) {
                int nextX = x + deltaX[i];
                int nextY = y + deltaY[i];
                if (isValid(grid, nextX, nextY, visited)) {
                    queue.offer(nextX * cols + nextY);
                    visited[nextX][nextY] = 1;
                }
            }
        }
    }

    private boolean isValid(char[][] grid, int row, int col, int[][] visited) {
        int rows = grid.length;
        int cols = grid[0].length;
        return 0 <= row && row < rows && 0<= col && col < cols && grid[row][col] == '1'&& visited[row][col] != 1;
    }
}

DFS解法

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] visited = new int[rows][cols];

        int num = 0;
        for (int row = 0; row < rows; row++) {
            for(int col = 0; col < cols; col++) {
                if (grid[row][col] == '1' && visited[row][col] == 0) {
                    dfs(grid, row, col, visited);
                    num++;
                }
            }
        }
        return num;
    }

    private void dfs(char[][] grid, int x, int y, int[][] visited) {
        if (isValid(grid, x, y, visited)) {
            visited[x][y] = 1;
            dfs(grid, x - 1, y, visited);
            dfs(grid, x + 1, y, visited);
            dfs(grid, x, y - 1, visited);
            dfs(grid, x, y + 1, visited);
        }

    }

    private boolean isValid(char[][] grid, int x, int y, int[][] visited) {
        int rows = grid.length;
        int cols = grid[0].length;
        return 0 <= x && x < rows && 0<= y && y < cols && grid[x][y] == '1' && visited[x][y] == 0;
    }
}

Flood Filling Distance Matrix

Walls and Gates

• Multi-end BFS

• 先找0

• 然后bfs

• 每次查看pop出来的坐标的邻居，如果还有INF,就更新距离

public void wallsAndGates(int[][] rooms) {
        if(rooms == null || rooms.length == 0 || rooms[0].length == 0) return;
        int rows = rooms.length;
        int cols = rooms[0].length;
        Queue<Integer> gates = new LinkedList<>();

        for(int i = 0; i < rows; i++){
            for(int j = 0; j< cols; j++){
                if(rooms[i][j] == 0){
                    gates.offer(i * cols + j);//no need to store Tuple
                }
            }
        }

        int[] dir = {0,1,0,-1,0};//little trick

        while(!gates.isEmpty()){
            int gate = gates.poll();
            int x = gate / cols;//extract x and y
            int y = gate % cols;
            for(int i = 0; i < 4; i++){
                int xx = x + dir[i];
                int yy = y + dir[i + 1];
                if(xx >= 0 && xx < rows && yy >= 0 && yy < cols && rooms[xx][yy] == Integer.MAX_VALUE){
                    rooms[xx][yy] = rooms[x][y] + 1;
                    gates.offer(xx * cols + yy);
                }
            }
        }
    }

给一个2D matrix， 0表示路，1表示墙，给个start point和end point，求最短路径。(Twitter)

• 最经典的BFS

public class Solution{
  public static class Point{
    int x;
    int y;
    public Point(int x, int y){
      this.x = x;
      this.y = y;
    }
  }
  public static int getDistance(int[][] matrix, Point src, Point dst){
    int rows = matrix.length;
    int cols = matrix[0].length;

    boolean[][] visited = new boolean[rows][cols];

    int[][] res = new int[rows][cols];

    //4 directions
    int[] x_ways = {0,0,1,-1};
    int[] y_ways = {1,-1,0,0};

    Queue<Point> queue = new LinkedList<>();
    queue.offer(src);

    while(!queue.isEmpty()){
      Point cur = queue.poll();
      visited[cur.x][cur.y] = true;

      if(cur.x == dst.x && cur.y == dst.y){
        break;//find the dst Point
      }

      for(int i = 0; i < 4; i++){
        int x_next = cur.x + x_ways[i];
        int y_next = cur.y + y_ways[i];

        if(x_next >= 0 && x_next < rows && y_next >= 0 && y_next < cols && matrix[x_next][y_next] == 1 && !visited[x_next][y_next]){
          queue.offer(new Point(x_next, y_next));
          res[x_next][y_next] = res[cur.x][cur.y] + 1;//distance + 1
        }
      }
    }

    if(res[dst.x][dst.y] == 0){
      return -1;//no path to dst Point
    }
    return res[dst.x][dst.y];
  }
  public static void main(String[] args){
    int[][] matrix = {{1,1,1,1,1},
                      {0,0,1,1,1},
                      {1,1,1,1,1}
                      };
    int distance = getDistance(matrix, new Point(0,0), new Point(2, 4));
    System.out.println("shortest distance between A and B is: " + distance);  
  }

}