基础知识：
常见的BFS用来解决什么问题？(1) 简单图（有向无向皆可）的最短路径长度，注意是长度而不是具体的路径（2）拓扑排序 （3） 遍历一个图（或者树）
BFS基本模板（需要记录层数或者不需要记录层数）
多数情况下时间复杂度空间复杂度都是O（N+M），N为节点个数，M为边的个数

面试推荐题单

https://zhuanlan.zhihu.com/p/349940945

基于树的BFS：不需要专门一个set来记录访问过的节点

leetcode 102 二叉树的层序遍历

原题链接:
https://leetcode.cn/problems/binary-tree-level-order-traversal/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {

        // 队列
        Queue<TreeNode> queue = new ArrayDeque<>();
        List<List<Integer>> ans = new ArrayList<>();

        if(root == null){
            return ans;
        }

        queue.add(root);
        while (queue.isEmpty() == false){
            int s = queue.size();
            var cur = new  ArrayList<Integer>();
            for(int i = 0 ; i < s ; i++){
                var node = queue.poll();
                cur.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }

                if(node.right != null){
                    queue.offer(node.right);
                }
            }

            ans.add(cur);
        }

        return ans;
    }
}

leetcode 103. 二叉树的锯齿形层序遍历

题目思路简单 但要实现很绕

法1 用下一层的层数来判断当前的存储顺序

非常绕 效率也不高 我第一次自己的时候的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>>ans = new ArrayList<>();
        if(root == null){
            return ans;
        }

        Deque<TreeNode>  deque = new ArrayDeque<>();
        deque.offer(root);
        int level = 1;
        while (deque.isEmpty() == false){
            ArrayList<TreeNode> cur = new ArrayList<>(deque);
            ArrayList<Integer> tmp = new ArrayList<>(deque.size());
            deque.clear();
            cur.stream().forEach(s -> tmp.add(s.val));
            ans.add(tmp);
            deque.clear();

            level++;

            // 如果下一层是奇数 那么从左到右加入
            if (level % 2 == 1){
                // 下一层是奇数 那么当前层是偶数 
                // 所以当前层 应该后往前遍历
                for(int i = cur.size() - 1 ; i >= 0 ; i--){
                    var node = cur.get(i);
                    if(node.left != null){
                        deque.add(node.left);
                    }

                    if (node.right != null){
                        deque.add(node.right);
                    }
                }
            }else {
                // 下一层 是偶数 那么当前层是奇数
                // 也应该倒着来 但是加入顺序不一样
                for (int i = cur.size() - 1 ; i >= 0  ; i-- ){
                    var node = cur.get(i);
                    if (node.right != null){
                        deque.add(node.right);
                    }
                    
                    if (node.left != null){
                        deque.add(node.left);
                    }
                }
            }
        }
        
        return ans;
    }
}

法2 符号标记直接判断 该层是否应该顺序输出

内核与法1相同但 优雅很多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null){
            return ans;
        }

        boolean isOrder = true;

        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while (q.isEmpty() == false){
            ArrayList<Integer> tmp = new ArrayList<>();
            ArrayList<TreeNode> cur = new ArrayList<>(q);

            if (!isOrder){
                Collections.reverse(cur);
            }

            for (int i = 0 ; i < cur.size() ; i++){
                tmp.add(cur.get(i).val);
            }

            ans.add(tmp);

            isOrder = !isOrder;

            int m = q.size();

            for (int i = 0 ; i < m ; i++){
                var t = q.poll();
                if (t.left != null){
                    q.offer(t.left);
                }

                if (t.right != null){
                    q.offer(t.right);
                }
            }


        }

        return ans;
    }
}

基于图的BFS：（一般需要一个set来记录访问过的节点）

leetcode133.克隆图

原题链接: https://leetcode.cn/problems/clone-graph/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

/**
 * BFS 不断遍历点 进行建图
 * Hash存储遍历过的点
 */
class Solution {
    public Node cloneGraph(Node node) {
        if(node == null){
            return node;
        }
        // 用于存储 已经访问过的节点 
        // 不用set 是因为要进行重构图 
        // 所以第一个位置原节点的索引 记录了地址hash值 用于标记
        // 而第二个位置 用于新的该节点的引用 用于后续的重建 
        HashMap<Node,Node> visited = new HashMap<>();
        // 用于BFS
        Queue<Node> queue = new LinkedList<>();
        
        queue.add(node);
        visited.put(node,new Node(node.val,new ArrayList<>()));
        
        while (!queue.isEmpty()){
            var t = queue.poll();
            
            // 遍历所有邻接节点
            for (var neighbor : t.neighbors){
                if (!visited.containsKey(neighbor)){
                    // 先进行标记 
                    visited.put(neighbor,new Node(neighbor.val,new ArrayList<>()));
                    queue.offer(neighbor);
                }
                // 进行拷贝 将原节点的链接关系 复制到新的节点 
                // 链接的节点 也一定要从visited中拿 才是新的节建立的节点关系 否则不是深拷贝
                visited.get(t).neighbors.add(visited.get(neighbor));
            }
        }
        
        // 返回的时 原node  对应的新的节点
        return visited.get(node);
    }
}


leetcode 127 单词接龙

原题链接:
https://leetcode.cn/problems/word-ladder/description/

法1 基础BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Node{
    String s;
    int step;
    Node(String s,int step){
        this.s = s;
        this.step = step;
    }
}

class Solution {
    public boolean cmp(String a,String b){
        int count = 0;
        for(int i = 0 ; i < a.length() ; i++){
            if(a.charAt(i) != b.charAt(i)){
                count++;
            }
        }
        return count == 1;
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {  
        if(beginWord.equals(endWord)){
            return 1;
        }

        Queue<Node>q = new LinkedList<>(); 
        q.offer(new Node(beginWord,1));
        HashSet<String>set = new HashSet<>();
        set.add(beginWord);
        while(!q.isEmpty()){
            var node = q.poll();

            if(node.s.equals(endWord)){
                return node.step;
            }

            for(var w:wordList){
                if(set.contains(w)){
                    continue;
                }
                
                if(cmp(w,node.s)){
                    set.add(w);
                    q.offer(new Node(w,node.step + 1));
                }
            }
        }

        return 0;
    }
}

法2 双向BFS

leetcode 130 被围绕的区域

原题链接:
https://leetcode.cn/problems/surrounded-regions/

法1: 染色

先处理完边界 然后按照题意遍历一次进行处理即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    public static int [] dx = new int [] {-1,0,1,0};
    public static int [] dy = new int [] {0,-1,0,1};
    public static char [][] g; 
    public static int n,m;

    public void solve(char[][] board) {
        g = board;
        n = board.length;
        m = board[0].length;

        // 先把边界上的'O' 都先做处理
        for(int i = 0 ; i < n  ; i++){
            if(g[i][0] == 'O'){
                dfs1(i,0);
            }

            if(g[i][m - 1] == 'O'){
                dfs1(i,m - 1);
            }
        }

        for(int i = 0 ; i < m ; i++){
            if(g[0][i] == 'O'){
                dfs1(0,i);
            }

            if(g[n - 1][i] == 'O'){
                dfs1(n - 1,i);
            }
        }

   

        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                if(g[i][j] == '1'){
                    g[i][j] = 'O';
                }
                else if(g[i][j] == 'O'){
                    g[i][j] = 'X';
                }
            }
        }

        board = g;
    }

    public void dfs1(int x,int y){
        g[x][y] = '1';
        for(int i = 0 ; i < 4 ; i++){
            int tx = x + dx[i];
            int ty = y + dy[i];

            if(tx < 0 || tx >= n || ty < 0 || ty >= m || g[tx][ty] != 'O'){
                continue;
            }

            dfs1(tx,ty);
        }
    }
}

leetcode 752 打开转盘锁

原题链接:
https://leetcode.cn/problems/open-the-lock/description/

双向BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Solution {
    // 全局目标 方便后续在update中的判定
    public static String tg;
    public static HashSet<String> dead;
    public int openLock(String[] deadends, String target) {
        var start = "0000";
        if(start.equals(target)){
            return 0;
        }

        tg = target;

        dead = new HashSet<>(Arrays.asList(deadends));

        if(dead.contains(start)){
            return -1;
        }

        HashMap<String,Integer> h1 = new HashMap<>();
        HashMap<String,Integer> h2 = new HashMap<>();

        Queue<String> d1 = new LinkedList<>();
        Queue<String> d2 = new LinkedList<>();

        

        d1.offer(start);
        h1.put(start,0);
        d2.offer(target);
        h2.put(target,0);

        while (!d1.isEmpty() && !d2.isEmpty()){
            int t = -1;
            if (d1.size() <= d2.size()){
                t = update(d1,h1,h2);
            }else {
                t = update(d2,h2,h1);
            }

            if (t != -1){
                return  t;
            }
        }
        return -1;
    }

    public int update(Queue<String> queue, HashMap<String,Integer> cur, HashMap<String,Integer>other){
        // 双端BFS 要求 每次扩展按层进行扩展
        int n = queue.size();
        while (n-- > 0){
            var t = queue.poll();
            var tca = t.toCharArray();
            int step = cur.get(t);
            // 一共4位 遍历每一位
            for (int i = 0 ; i < 4 ; i++){
                for (int j = - 1 ; j < 2 ; j++){
                    if (j == 0){
                        continue;
                    }
                    int ori = tca[i] - '0';
                    int next = (ori + j) % 10;
                    if (next == -1){
                        next = 9;
                    }
                    var clone = tca.clone();
                    clone[i] = (char) (next + '0');
                    var ct = String.valueOf(clone);

                    if (dead.contains(ct) || cur.containsKey(ct)){
                        continue;
                    }

                    // 如果再另一方向上找到 说明找到了 最短路径
                    if (other.containsKey(ct)){
                        return  step + 1 + other.get(ct);
                    }else {
                        cur.put(ct,step + 1);
                        queue.offer(ct);
                    }
                }
            }
        }

        return -1;
    }

}

多源BFS

leetcode 541 01 矩阵

原题链接:
https://leetcode.cn/problems/01-matrix/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    public int [] dx = new int[]{-1,0,1,0};
    public int [] dy = new int[]{0,-1,0,1};


    // 多源BFS
    public int[][] updateMatrix(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int [][] res = new int[n][m];
        Queue<int []> q = new LinkedList<>();

        // 将所有0 入队 
        // 是将要访问的点 标记为-1 记录为未访问过 
        for (int i = 0 ; i < n ; i++){
            for (int j = 0 ; j < m; j++){
                if (mat[i][j] == 0){
                    q.offer(new int[] {i,j});
                }else {
                    res[i][j] = -1;
                }
            }
        }

        while (!q.isEmpty()){
            var t = q.poll();
            int x = t[0] , y = t[1];

            for (int i = 0 ; i < 4 ; i++){
                int tx = x + dx[i];
                int ty = y + dy[i];

                if (tx < 0 || tx >= n || ty < 0 || ty >= m || res[tx][ty] != -1){
                    continue;
                }

                res[tx][ty] = res[x][y] + 1;
                q.offer(new int[] {tx , ty});
            }
        }

        return res;
    }
}

leetcode 1162 地图分析

原题链接:
https://leetcode.cn/problems/as-far-from-land-as-possible/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public static int [] dx = new int[] {-1,0,1,0};
    public static int [] dy = new int[] {0,-1,0,1};

    // 0 是海洋 1是陆地
    // 要找的是海洋
    // 多源BFS 把所有陆地入队 找到距离陆地最远的海洋
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int [][] res = new int[n][m];

        Queue<int []> q = new LinkedList<>();

        for (int i = 0 ; i < n ; i++){
            for (int j = 0 ; j < m ; j++){
                if (grid[i][j] == 1){
                    q.offer(new int[]{i,j});
                }else {
                    res[i][j] = -1;
                }
            }
        }

        int ans = -1;

        while (!q.isEmpty()){
            var t = q.poll();
            int x = t[0];
            int y = t[1];
            for (int i = 0 ; i < 4 ;i++){
                int tx = x + dx[i];
                int ty = y + dy[i];

                if (tx < 0 || tx >= n || ty < 0 || ty >= m || res[tx][ty] != -1){
                    continue;
                }

                res[tx][ty] = res[x][y] + 1;
                ans = Math.max(ans,res[tx][ty]);
                q.offer(new int[]{tx,ty});
            }
        }
        return  ans;
    }
}

leetcode 1293 网格中的最短路径

原题链接:
https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public static int [] dx = new int[]{-1,0,1,0};
    public static int [] dy = new int[]{0,-1,0,1};
    public int shortestPath(int[][] grid, int k) {
        int n = grid.length;
        int m = grid[0].length;
        Queue<int []> q = new LinkedList<>();
        var start = new int [] {0,0,grid[0][0],0};
        q.offer(start);
        var visited = new boolean [n][m][k + 1];
        visited[0][0][grid[0][0]] = true;

        while (!q.isEmpty()){
            var t = q.poll();
            int x = t[0] , y = t[1] , curk = t[2];
            int step = t[3];
            for(int i = 0 ; i < 4 ; i++){
                int tx = x + dx[i];
                int ty = y + dy[i];

                if (tx < 0 || tx >= n || ty < 0 || ty >= m ){
                    continue;
                }

                if (grid[tx][ty] == 1 && curk == k){
                    continue;
                }

                if (tx == n - 1 && ty == m - 1){
                    return step + 1;
                }

                int tk = curk + grid[tx][ty];

                if (visited[tx][ty][tk]){
                    continue;
                }

                visited[tx][ty][tk] = true;
                q.offer(new int[]{tx,ty,tk,step + 1});

            }
        }
        return  -1;
    }
}

leetcode 417 太平洋大西洋水流问题

原题链接:
https://leetcode.cn/problems/pacific-atlantic-water-flow/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
    public static int [] dx = new int[] {-1,0,1,0};
    public static int [] dy = new int[] {0,-1,0,1};
    public int [][] g;
    public  int n,m;
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        g = heights;
        n = heights.length;
        m = heights[0].length;
        boolean [][] res1 = new boolean[n][m];
        boolean [][] res2 = new boolean[n][m];
        // 太平洋
        Queue<int[]> q1 = new LinkedList<>();
        // 大西洋
        Queue<int[]> q2 = new LinkedList<>();

        for (int i = 0; i < n ; i++){
            q1.offer(new int[]{i,0});
            res1[i][0] = true;

            q2.offer(new int[]{i,m - 1});
            res2[i][m - 1] = true;
        }

        for (int i = 0; i < m ; i++){
            q1.offer(new int[]{0,i});
            res1[0][i] = true;

            q2.offer(new int[]{n - 1,i});
            res2[n - 1][i] = true;
        }

        bfs(q1,res1);
        bfs(q2,res2);

        List<List<Integer>> ans = new ArrayList<>();

        for (int i = 0; i < n ; i++){
            for (int j = 0; j < m ; j++){
                if(res1[i][j] && res2[i][j]){
                    ans.add(Arrays.asList(i,j));
                }
            }
        }

        return ans;
    }

    public void bfs(Queue<int[]>q, boolean [][] res){
        while (!q.isEmpty()){
            var t = q.poll();
            for (int i = 0; i < 4 ; i++){
                int x = t[0] + dx[i];
                int y = t[1] + dy[i];

                if (x < 0 || x >= n || y < 0 || y >= m){
                    continue;
                }

                if (g[x][y] <  g[t[0]][t[1]] || res[x][y]){
                    continue;
                }

                res[x][y] = true;
                q.offer(new int[] {x,y});
            }
        }
    }
}

拓扑排序

原题链接:
https://leetcode.cn/problems/course-schedule/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int n = prerequisites.length;
        // 存图
        HashMap<Integer,ArrayList<Integer>> g = new HashMap<>();
        // 存度
        int [] in = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            int a = prerequisite[0], b = prerequisite[1];
            var arr = g.getOrDefault(b, new ArrayList<>());
            arr.add(a);
            in[a]++;
            g.put(b, arr);
        }

        Queue<Integer>  q = new LinkedList<>();

        for (int i = 0; i < numCourses ; i++){
            if (in[i] == 0){
                q.offer(i);
            }
        }

        int ans = 0;

        while (!q.isEmpty()){
            var t = q.poll();
            ans++;

            if (g.get(t) == null){
                continue;
            }

            for (var next : g.get(t)){
                in[next]--;
                if (in[next] == 0){
                    q.offer(next);
                }
            }
        }

        return ans == numCourses;
    }
}