# 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);  
  }

}
```

##


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://syjohnson11.gitbook.io/leetcode/bfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.