# BFS

### 应用场景

一般用来解决**最短连通路径**问题。

### 基本思路

单源BFS：借助Queue，将源点存进Queue，然后每次从Queue的头取一个元素，将所有 unvisited neighbors加到Queue尾，依次进行，直到Queue空。

### Typical BFS 写法

```
Queue q;
Set visited;
q.add(node);

while(q is not empty) {
    Node cur = q.poll();
    for(Node neighbor: cur.neighbors) {
        if(neighbor is not visited) {
            q.add(neighbor);
        }
    }
}
```



{% hint style="info" %}
多源BFS：单源BFS的升级版。会大大减少时间复杂度。前提是，每个源的地位都是一样的。做法跟单源的类似，只不过要先把所有源存进Queue。
{% endhint %}

## 经典题目

[_323 Number of Connected Components in an Undirected Graph_](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/description/)

{% tabs %}
{% tab title="邻接表 + BFS" %}
```java
// time: O(V + E + V * E) ???
public int countComponents(int n, int[][] edges) {
    List<List<Integer>> graph = buildGraph(n, edges);
    int ans = 0;
    boolean[] visited = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            Deque<Integer> queue = new LinkedList<>();
            queue.offerLast(i);
            while (!queue.isEmpty()) {
                int cur = queue.pollFirst();
                visited[cur] = true;
                List<Integer> list = graph.get(cur);
                if (list != null) {
                    for (Integer nei : list) {
                        if (!visited[nei]) {
                            queue.offerLast(nei);
                        }
                    }
                }
            }
            ans += 1;
        }
    }
    return ans;
}

private List<List<Integer>> buildGraph(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<List<Integer>>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<Integer>());
    }
    for (int[] edge: edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    }
    return graph;
}
```
{% endtab %}

{% tab title="邻接表 + DFS" %}
```java
// time: O(V + E + V * E) ???
public int countComponents(int n, int[][] edges) {
    List<List<Integer>> graph = buildGraph(n, edges);
    int ans = 0;
    boolean[] visited = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(n, i, graph, visited);
            ans += 1;
        }
    }
    return ans;
}

private void dfs(int n, int i, List<List<Integer>> graph, boolean[] visited) {
    if (visited[i]) {
        return;
    }
    visited[i] = true;
    List<Integer> list = graph.get(i);
    for (Integer nei : list) {
        dfs(n, nei, graph, visited);
    }
}
```
{% endtab %}

{% tab title="Union Find" %}
```java
// 一开始有n个节点，想象成有n个独立的graph，每个节点都是各个graph的root。
// 遍历edges，每次找到两个点的root，若不相等，则把root连接起来，此时n = n - 1。
// find() 函数会不断调用，直到找到root，即index = val
// time: O(V + E * V) ???
public int countComponents(int n, int[][] edges) {
    int[] roots = new int[n];
    for (int i = 0; i < n; i++) roots[i] = i;
    int ans = n;
    for (int[] edge: edges) {
        int root1 = find(roots, edge[0]); // Find the root of edge[0]
        int root2 = find(roots, edge[1]); // Find the root of edge[1]
        if (root1 != root2) {
            roots[root2] = root1;
            ans -= 1;
        }
    }
    return ans;
}
private int find(int[] roots, int node) {
    if (roots[node] == node) {
        return node;
    }
    return find(roots, roots[node]);
}
```
{% endtab %}
{% endtabs %}



* [286 Walls and Gates](https://leetcode.com/problems/walls-and-gates/description/)

```java
class Solution {
    private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0].length == 0) return;
        int n = rooms.length;
        int m = rooms[0].length;
        Deque<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (rooms[i][j] == 0) {
                    //bfs(i, j, n, m, rooms);
                    queue.offerLast(new int[] {i, j});
                    visited[i][j] = true;
                }
            }
        }
        bfs(n, m, queue, visited, rooms);
    }
    
    private void bfs(int n, int m, Deque<int[]> queue, boolean[][] visited, int[][] rooms) {
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0) {
                int[] cur = queue.pollFirst();
                for (int i = 0; i < dirs.length; i++) {
                    int nextRow = cur[0] + dirs[i][0];
                    int nextCol = cur[1] + dirs[i][1];
                    if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < m && !visited[nextRow][nextCol] && rooms[nextRow][nextCol] > 0) {
                        visited[nextRow][nextCol] = true;
                        queue.offerLast(new int[] {nextRow, nextCol});
                    }
                }
                rooms[cur[0]][cur[1]] = step;
            }
            step++;
        }
    }
}
```



[ 675. Cut Off Trees for Golf Event](https://leetcode.com/problems/cut-off-trees-for-golf-event/description/)

```java
// 有几个陷阱要注意：1. (0, 0)是需要进栈的，因为有可能不是先砍(0, 0)
// 2. 如果(0, 0)点是最小点，则直接砍，也就是说BFS的时候，得预先判断一下。
// 3. BFS的时候，判断neighbor是不是valid，只需要看能不能走就行。

class Solution {
    private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int cutOffTree(List<List<Integer>> forest) {
        List<int[]> trees = new ArrayList<>();
        for (int i = 0; i < forest.size(); i++) {
            List<Integer> row = forest.get(i);
            for (int j = 0; j < row.size(); j++) {
                int val = row.get(j);
                if (val > 1) {
                    trees.add(new int[] {i, j, val});
                }
            }
        }
        Collections.sort(trees, (int[] a, int[] b) -> (a[2] - b[2]));
        int sr = 0, sc = 0;
        int ans = 0;
        for (int[] tree: trees) {
            int dist = getDistance(sr, sc, tree[0], tree[1], forest);
            //System.out.println(dist);
            if (dist == -1) return -1;
            ans += dist;
            sr = tree[0];
            sc = tree[1];
        }
        return ans;
    }
    
    // BFS to find shortest path
    private int getDistance(int sr, int sc, int dr, int dc, List<List<Integer>> forest) {
        if (sr == dr && sc == dc) {
            return 0;
        }
        int n = forest.size();
        int m = forest.get(0).size();
        Deque<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        queue.offerLast(new int[] {sr, sc});
        visited[sr][sc] = true;
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] cur = queue.pollFirst();
                for (int i = 0; i < dirs.length; i++) {
                    int nextRow = cur[0] + dirs[i][0];
                    int nextCol = cur[1] + dirs[i][1];
                    if (nextRow == dr && nextCol == dc) {
                        return step;
                    }
                    if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < m && !visited[nextRow][nextCol] && forest.get(nextRow).get(nextCol) > 0) {
                        visited[nextRow][nextCol] = true;
                        queue.offerLast(new int[] {nextRow, nextCol});
                    }
                }
            }
            step++;
        }
        return -1;
    }
}
```



[ 863. All Nodes Distance K in Binary Tree](https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/)

```java
// 类似于 KNN，以 target 为中心，做BFS

class Solution {
    class MyNode {
        int val;
        MyNode left, right, parent;
        public MyNode(int x) {
            val = x;
        }
    }
    
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        List<Integer> ans = new ArrayList<>();
        
		// Rebuild a binary tree with the parent property
        MyNode[] array = new MyNode[] {null};
        MyNode myNode = rebuild(root, null, target, array);
        // New Target Node
		MyNode targetNode = array[0];
        
		// Start from New Target Node, do BFS
		// Stop at distance K
        Deque<MyNode> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offerLast(targetNode);
        visited.add(targetNode.val);
        
        while (K-- > 0) {
            int size = queue.size();
            while (size-- > 0) {
                MyNode cur = queue.pollFirst();
                if (cur.left != null && !visited.contains(cur.left.val)) {
                    visited.add(cur.left.val);
                    queue.offerLast(cur.left);
                }
                if (cur.right != null && !visited.contains(cur.right.val)) {
                    visited.add(cur.right.val);
                    queue.offerLast(cur.right);
                }
                if (cur.parent != null && !visited.contains(cur.parent.val)) {
                    visited.add(cur.parent.val);
                    queue.offerLast(cur.parent);
                }
            }
        }
        
		// Remaining Nodes in queue are all distance K from New Target Node
        while (!queue.isEmpty()) {
            ans.add(queue.pollFirst().val);
        }
        
        return ans;
    }
    
    private MyNode rebuild(TreeNode node, MyNode parent, TreeNode target, MyNode[] array) {
        if (node == null) return null;
        
        MyNode myNode = new MyNode(node.val);
        myNode.left = rebuild(node.left, myNode, target, array);
        myNode.right = rebuild(node.right, myNode, target, array);
        myNode.parent = parent;
        
        if (target.val == node.val) {
            array[0] = myNode;
        }
        
        return myNode;
    }
}
```
