BFS

爱被打了一巴掌 2022-10-01 11:55 187阅读 0赞

### BFS 的使用条件: ###

*  简单图(没有权重)可以找最短路径

### BFS 模板: ###

建一个Queue，先将起点放入Queue中,然后根据题目要求得到下一层的点(可达方向,String的变换)，判断是否已经到达终点(是否inBound) 然后将下一层的点继续放入Queue中

Queue<> queue = new LinkedList<>();
    while (!queue.isEmpty()) {
        node/String/position if (...) {
            
        } else {
            
        }
        queue.add();
    }
    复制代码

### BFS题目分类: ###

*  树上的BFS:
    
     *  Level Order
        
         *  序列化
 *  网格上的BFS: 一般都是向4个不同方向做扩展
    
     *  最短路径
     *  
 *  字符串的BFS
 *  图上的BFS
    
     *  图的遍历
     *  简单图最短路径
 *

### 树上的BFS ###

#### 序列化与反序列化 ####

**297. Serialize and Deserialize Binary Tree**

*  思路: 将所有的节点都按照前序遍历的顺序加入queue中,而不能仅仅加入非空的节点

public class Solution {
        /** * This method will be invoked first, you should design your own algorithm * to serialize a binary tree which denote by a root node to a string which * can be easily deserialized by your own "deserialize" method later. */
        public String serialize(TreeNode root) {
            // write your code here
            if (root == null) {
                return "{}";
            }
            
            Queue<TreeNode> queue = new LinkedList<>();
            StringBuilder sb = new StringBuilder();
            queue.offer(root);
            sb.append("{");
            
            while (!queue.isEmpty()) {
                TreeNode head = queue.poll();
                if (head == null) {
                    sb.append("#");
                } else {
                    sb.append(head.val);
                    queue.offer(head.left);
                    queue.offer(head.right);
                }
                
                if (!queue.isEmpty()) {
                    sb.append(",");
                }
            }
            
            sb.append("}");
            return sb.toString();
        }
    
        /** * This method will be invoked second, the argument data is what exactly * you serialized at method "serialize", that means the data is not given by * system, it's given by your own serialize method. So the format of data is * designed by yourself, and deserialize it here as you serialize it in * "serialize" method. */
        public TreeNode deserialize(String data) {
            // write your code here
            if (data == null || data.equals("{}")) {
                return null;
            }
            
            String[] val = data.substring(1, data.length() - 1).split(",");
            // 这里要使用Integer类将String转为int类型
            TreeNode root = new TreeNode(Integer.parseInt(val[0]));
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            boolean isLeftChild = true;
            
            for (int i = 1; i < val.length; i++) {
                if (!val[i].equals("#")) {
                    TreeNode child = new TreeNode(Integer.parseInt(val[i]));
                    if (isLeftChild) {
                        queue.peek().left = child;
                    } else {
                        queue.peek().right = child;
                    }
                    
                    queue.offer(child);
                }
                
                if (!isLeftChild) {
                    queue.poll();
                }
                isLeftChild = !isLeftChild;
            }
            
            return root;
        }
    }
    复制代码

* Clone Graph: 
        * 知识点: deep copy 与 soft copy: deep copy是拷贝**内容** 而soft copy是拷贝**reference**
        ```java
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = list1; // soft copy -> list1.add() 会同时影响list1 和 list2
        List<Integer> list3 = new ArrayList<>(list1); // deep copy
        ```
        * 图的存储: HashMap< key: old node value: new node > 
    * 拓扑排序 Course Schedule, Topological Sort    
    复制代码

**Clone Graph**

public class Solution {
        /** * @param node: A undirected graph node * @return: A undirected graph node */
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if (node == null) {
                return node;
            }
    
            // use bfs algorithm to traverse the graph and get all nodes.
            ArrayList<UndirectedGraphNode> nodes = getNodes(node);
            
            // copy nodes, store the old->new mapping information in a hash map
            HashMap<UndirectedGraphNode, UndirectedGraphNode> mapping = new HashMap<>();
            for (UndirectedGraphNode n : nodes) {
                mapping.put(n, new UndirectedGraphNode(n.label));
            }
            
            // copy neighbors(edges)
            for (UndirectedGraphNode n : nodes) {
                UndirectedGraphNode newNode = mapping.get(n);
                for (UndirectedGraphNode neighbor : n.neighbors) {
                    UndirectedGraphNode newNeighbor = mapping.get(neighbor);
                    newNode.neighbors.add(newNeighbor);
                }
            }
            
            return mapping.get(node);
        }
        
        private ArrayList<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {
            Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
            HashSet<UndirectedGraphNode> set = new HashSet<>();
            
            queue.offer(node);
            set.add(node);
            while (!queue.isEmpty()) {
                UndirectedGraphNode head = queue.poll();
                for (UndirectedGraphNode neighbor : head.neighbors) {
                    if(!set.contains(neighbor)){
                        set.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
            }
            
            return new ArrayList<UndirectedGraphNode>(set);
        }
    }
    
    复制代码

**The Maze**

public class Solution {
        int[] deltaX = new int[] {
        0, 0, -1, 1};
        int[] deltaY = new int[] {
        1, -1, 0, 0};
        
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            if(maze == null || maze.length == 0 || maze[0].length == 0 || start == null || start.length == 0 || destination == null || destination.length == 0){
                return false;
            }
            
            Queue<int[]> queue = new LinkedList<>();
            boolean[][] visited = new boolean[maze.length][maze[0].length];
            queue.offer(start);
            visited[start[0]][start[1]] = true;
            
            while(!queue.isEmpty()){
                int[] curPoint = queue.poll();
                int x = curPoint[0], y = curPoint[1];
                for(int j = 0; j < 4; j++){
                    int xx = x;
                    int yy = y;
                    
                    while(isValid(xx + deltaX[j], yy + deltaY[j], maze)){
                        xx += deltaX[j];
                        yy += deltaY[j];
                    }
                    if(xx == destination[0] && yy == destination[1]){
                        return true;
                    }
                    if(!visited[xx][yy]){
                        queue.offer(new int[]{xx, yy});
                        visited[xx][yy] = true;
                    }
                }
            }
            return false;
        }
        
        private boolean isValid(int x, int y, int[][] maze){
            return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0;
        }
    }
    
    复制代码

**The Maze II**

*  问题: 二维矩阵上找出从起点到达终点的最短的路径
 *

public class Solution {
        class Point {
            int x,
            int y,
            int len;
            public Point(int x, int y, int len) {
                this.x = x;
                this.y = y;
                this.len = len;
            }
        }
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            int m = maze.length;
            int n = maze[0].length;
            int[][] length=new int[m][n]; // record length
            for (int i = 0;i < m*n; i++) {
                length[i / n][i % n]=Integer.MAX_VALUE;
            }
            int[][] dir=new int[][] {
        {-1,0},{
        0,1},{
        1,0},{
        0,-1}};
            PriorityQueue<Point> list=new PriorityQueue<>((o1,o2)->o1.len - o2.len); // using priority queue
            list.offer(new Point(start[0], start[1], 0));
            while (!list.isEmpty()) {
                Point p=list.poll();
                if (length[p.x][p.y]<=p.l) continue; // if we have already found a route shorter
                length[p.x][p.y]=p.l;
                for (int i=0;i<4;i++) {
                    int xx=p.x, yy=p.y, l=p.l;
                    while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0) {
                        xx+=dir[i][0];
                        yy+=dir[i][1];
                        l++;
                    }
                    xx-=dir[i][0];
                    yy-=dir[i][1];
                    l--;
                    list.offer(new Point(xx, yy, l));
                }
            }
            return length[destination[0]][destination[1]]==Integer.MAX_VALUE?-1:length[destination[0]][destination[1]];
        }
    }
    
    // 不使用PriorityQueue的解法
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        // directions to top, bottom, left and right
        int[][] dirs={
        {-1,0},{
        1,0},{
        0,-1},{
        0,1}};
        // record shotest distance
        int[][] distance=new int[maze.length][maze[0].length];
        // Set all cell as -1
        for(int[] a:distance){
            Arrays.fill(a,-1);
        }
        // Initialize start distance to 0
        distance[start[0]][start[1]]=0;
        Queue<int[]> q=new LinkedList<>();
        q.add(start);
        while(!q.isEmpty()){
            int[] c = q.poll();
            for(int[] dir:dirs){
                int count=distance[c[0]][c[1]];
                int x = c[0];
                int y = c[1];
                while(x+dir[0] >= 0 && x+dir[0] < maze.length && 
                      y+dir[1] >=0 && y + dir[1] < maze[0].length && 
                      maze[x+dir[0]][y+dir[1]] != 1){
                    x += dir[0];
                    y += dir[1];
                    count++;
                }
                // If this cell is first time to reach or the distance to this cell is shorter
                // add it to queue and update distance
                if(distance[x][y]==-1 || distance[x][y] > count){
                    q.add(new int[]{x,y});
                    distance[x][y]=count;
                }
            }
        }
        return distance[destination[0]][destination[1]];
    }
    复制代码

**Word Ladder**

public class Solution {
        public int ladderLength(String start, String end, List<String> wordList) {
            Set<String> dict = new HashSet<>();
            for (String word : wordList) {
                dict.add(word);
            }
            
            if (start.equals(end)) {
                return 1;
            }
            
            HashSet<String> hash = new HashSet<String>();
            Queue<String> queue = new LinkedList<String>();
            queue.offer(start);
            hash.add(start);
            
            int length = 1;
            while (!queue.isEmpty()) {
                length++;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    String word = queue.poll();
                    for (String nextWord: getNextWords(word, dict)) {
                        if (hash.contains(nextWord)) {
                            continue;
                        }
                        if (nextWord.equals(end)) {
                            return length;
                        }
                        
                        hash.add(nextWord);
                        queue.offer(nextWord);
                    }
                }
            }
            
            return 0;
        }
    
        // replace character of a string at given index to a given character
        // return a new string
        private String replace(String s, int index, char c) {
            char[] chars = s.toCharArray();
            chars[index] = c;
            return new String(chars);
        }
        
        // get connections with given word.
        // for example, given word = 'hot', dict = {'hot', 'hit', 'hog'}
        // it will return ['hit', 'hog']
        private ArrayList<String> getNextWords(String word, Set<String> dict) {
            ArrayList<String> nextWords = new ArrayList<String>();
            for (char c = 'a'; c <= 'z'; c++) {
                for (int i = 0; i < word.length(); i++) {
                    if (c == word.charAt(i)) {
                        continue;
                    }
                    String nextWord = replace(word, i, c);
                    if (dict.contains(nextWord)) {
                        nextWords.add(nextWord);
                    }
                }
            }
            return nextWords;
        }
    }
    复制代码

**Word Ladders II**

*  问题: 给出两个单词和一个字段,找出所有的从start 到 end的最短转换序列, 每次只能改变一个字母,变换过程中的字母必须在字典中出现
 *  思路: BFS + DFS结合

public class Solution {
        public List<List<String>> findLadders(String start, String end,
                Set<String> dict) {
            List<List<String>> ladders = new ArrayList<List<String>>();
            Map<String, List<String>> map = new HashMap<String, List<String>>();
            Map<String, Integer> distance = new HashMap<String, Integer>();
    
            dict.add(start);
            dict.add(end);
     
            bfs(map, distance, start, end, dict);
            
            List<String> path = new ArrayList<String>();
            
            dfs(ladders, path, end, start, distance, map);
    
            return ladders;
        }
    
        void dfs(List<List<String>> ladders, List<String> path, String crt, String start, Map<String, Integer> distance, Map<String, List<String>> map) {
            path.add(crt);
            if (crt.equals(start)) {
                Collections.reverse(path);
                ladders.add(new ArrayList<String>(path));
                Collections.reverse(path);
            } else {
                for (String next : map.get(crt)) {
                    if (distance.containsKey(next) && distance.get(crt) == distance.get(next) + 1) { 
                        dfs(ladders, path, next, start, distance, map);
                    }
                }           
            }
            path.remove(path.size() - 1);
        }
    
        void bfs(Map<String, List<String>> map, Map<String, Integer> distance, String start, String end, Set<String> dict) {
            Queue<String> q = new LinkedList<String>();
            q.offer(start);
            distance.put(start, 0);
            for (String s : dict) {
                map.put(s, new ArrayList<String>());
            }
            
            while (!q.isEmpty()) {
                String crt = q.poll();
    
                List<String> nextList = expand(crt, dict);
                for (String next : nextList) {
                    map.get(next).add(crt);
                    if (!distance.containsKey(next)) {
                        distance.put(next, distance.get(crt) + 1);
                        q.offer(next);
                    }
                }
            }
        }
    
        List<String> expand(String crt, Set<String> dict) {
            List<String> expansion = new ArrayList<String>();
    
            for (int i = 0; i < crt.length(); i++) {
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch != crt.charAt(i)) {
                        String expanded = crt.substring(0, i) + ch
                                + crt.substring(i + 1);
                        if (dict.contains(expanded)) {
                            expansion.add(expanded);
                        }
                    }
                }
            }
    
            return expansion;
        }
    }
    复制代码

**Walls and Gates**

*  问题: 给出一个二维矩阵,`0`是门的位置，`-1`是墙的位置, `INF`是空房间的位置,求每个空房间到最近的门的距离
 *  思路: 将所有的门先push到队列当中,然后进行BFS

public class Solution {
        /** * @param rooms m x n 2D grid * @return nothing */
    
        public void wallsAndGates(int[][] rooms) {
            // Write your code here
            int n = rooms.length;
            if (n == 0) {
                return;
            }
            int m = rooms[0].length;
    
            int dx[] = {
        0, 1, 0, -1};
            int dy[] = {
        1, 0, -1, 0};
    
            Queue<Integer> qx = new LinkedList<>();
            Queue<Integer> qy = new LinkedList<>();
    
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (rooms[i][j] == 0) {
                        qx.offer(i);
                        qy.offer(j);
                    }
                }
            }
    
            while (!qx.isEmpty()) {
                int cx = qx.poll();
                int cy = qy.poll();
    
                for (int i = 0; i < 4; i++) {
                    int nx = cx + dx[i];
                    int ny = cy + dy[i];
                    if (0 <= nx && nx < n && 0 <= ny && ny < m
                            && rooms[nx][ny] == Integer.MAX_VALUE) {
                        qx.offer(nx);
                        qy.offer(ny);
                        rooms[nx][ny] = rooms[cx][cy] + 1;
                    }
                }
            }
        }
    }
    复制代码

**Course Schedule**

*  问题: 所有的课程编号是0到n-1,输入一个二维数组和一个num Courses表示课程总数,二维数组中存的是每门课程的先修课程,如果0是1的先修课程，写为\[1,0\],
 *  思路: 因为没有保存edges信息,每次都要遍历整个indegree数组,会超时, 使用ArrayList存每门课程的后继课程

public class Solution {
        /* * @param numCourses: a total of n courses * @param prerequisites: a list of prerequisite pairs * @return: true if can finish all courses or false */
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            // write your code here
            int[] indegree = new int[numCourses];
            
            for (int[] pre : prerequisites) {
                indegree[pre[0]]++;
            }
            int count = 0;
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < indegree.length; i++) {
                if (indegree[i] == 0) {
                    queue.add(i);
                    indegree[i] = -1;
                }
            }
            while (!queue.isEmpty()) {
                int course = queue.poll();
                for (int[] pre : prerequisites) {
                    if (pre[1] == course) {
                        indegree[pre[0]]--;
                    }
                }
                for (int i = 0; i < indegree.length; i++) {
                    if (indegree[i] == 0) {
                        queue.add(i);
                        indegree[i] = -1;
                    }
                }
                count++;
            }
            
            return count == numCourses;
        }
    }
    复制代码

public class Solution {
        /* * @param numCourses: a total of n courses * @param prerequisites: a list of prerequisite pairs * @return: true if can finish all courses or false */
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            // write your code here
            int[] indegree = new int[numCourses];
            List[] edges = new ArrayList[numCourses];
            for (int i = 0; i < numCourses; i++) {
                edges[i] = new ArrayList<Integer>();
            }
            
            for (int[] pre : prerequisites) {
                indegree[pre[0]]++;
                edges[pre[1]].add(pre[0]);
            }
            int count = 0;
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < indegree.length; i++) {
                if (indegree[i] == 0) {
                    queue.add(i);
                }
            }
            while (!queue.isEmpty()) {
                int course = queue.poll();
                int n = edges[course].size();
                for (int i = 0; i < n; i++) {
                    int pointer = (int)edges[course].get(i);
                    indegree[pointer]--;
                    if (indegree[pointer] == 0) {
                        queue.add(pointer);
                    }
                }
                count++;
            }
            
            return count == numCourses;
        }
    }
    复制代码

### String BFS ###

**Open the Lock**

*  问题: 给出一个String表示锁的目标位置,以及一个list表示无法打开的位置,起始位置为'0000',求将锁打开的最短步数
 *  思路: 每一个位置扭动一次算作一步操作 '0' -> '9' '9' -> '0' `c[i] = (char)((c[i]-'0'+ j + 10) % 10 + '0')`

class Solution {
        public int openLock(String[] deadends, String target) {
            HashSet<String> deadSet = new HashSet<String>();
            String start = "0000";
            for(String dead : deadends){
                if(dead.equals(start)) {
                    return -1;
                }
                deadSet.add(dead);
            }
            
            Queue<String> queue = new LinkedList<String>();
            int step = 0;
            queue.offer(start);
            while(!queue.isEmpty()){
                int size = queue.size();
                while (size-- != 0) {
                    String curr = queue.poll();
                    if (curr.equals(target)) {
                        return step;
                    }
                    for(int i = 0; i < 4; i++) {
                        for(int j = -1; j <= 1; j = j + 2) {
                            char[] c = curr.toCharArray();
                            c[i] = (char)((c[i]-'0'+ j + 10) % 10 + '0'); //这里有一个
                            String next = new String(c);
                            if(deadSet.contains(next))
                                continue;
                            queue.offer(next);
                            deadSet.add(next); // 因为起始位置确定了,每一个数字第一次出现的时候一定是最短的step,之后出现的时候可能已经不是最短了,所以加到deadSet之中
                        }
                    }                       
                }
                step++;
            }
            return -1;
        }
    }
    复制代码

### 其它类型BFS ###

**815. Bus Routes**

*  问题: 求一个起始位置到终止位置的乘坐公交车的最小换乘数量
 *  思路: 从终点向起点倒推,找出终点所在的数组,将所在数组中的其它数字加入到queue中 感觉就是一个拓扑排序?
 *  难点在于数据结构的组织上面需要用到HashMap<Integer, ArrayList<>()>来辅助存储相关的信息

class Solution {
        public int numBusesToDestination(int[][] routes, int S, int T) {
           HashSet<Integer> visited = new HashSet<>();
           Queue<Integer> q = new LinkedList<>();
           HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
           int ret = 0; 
            
           if (S==T) return 0; 
            
           for(int i = 0; i < routes.length; i++){
                for(int j = 0; j < routes[i].length; j++){
                    ArrayList<Integer> buses = map.getOrDefault(routes[i][j], new ArrayList<>());
                    buses.add(i);
                    map.put(routes[i][j], buses);                
                }       
            }
                    
           q.offer(S); 
           while (!q.isEmpty()) {
               int len = q.size();
               ret++;
               for (int i = 0; i < len; i++) {
                   int cur = q.poll();
                   ArrayList<Integer> buses = map.get(cur);
                   for (int bus: buses) {
                        if (visited.contains(bus)) continue;
                        visited.add(bus);
                        for (int j = 0; j < routes[bus].length; j++) {
                            if (routes[bus][j] == T) return ret;
                            q.offer(routes[bus][j]);  
                       }
                   }
               }
            }
            return -1;
        }
    }
    复制代码

**787. Cheapest Flights Within K Stops**

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
            Map<Integer, Map<Integer, Integer>> prices = new HashMap<>();
            for (int[] f : flights) {
                if (!prices.containsKey(f[0])) prices.put(f[0], new HashMap<>());
                prices.get(f[0]).put(f[1], f[2]);
            }
            Queue<int[]> pq = new PriorityQueue<>((a, b) -> (Integer.compare(a[0], b[0])));
            pq.add(new int[] {
        0, src, k + 1});
            while (!pq.isEmpty()) {
                int[] top = pq.remove();
                int price = top[0];
                int city = top[1];
                int stops = top[2];
                if (city == dst) return price;
                if (stops > 0) {
                    Map<Integer, Integer> adj = prices.getOrDefault(city, new HashMap<>());
                    for (int a : adj.keySet()) {
                        pq.add(new int[] {price + adj.get(a), a, stops - 1});
                    }
                }
            }
            return -1;
        }
    复制代码

**323. Number of Connected Components in an Undirected Graph**

*  问题: 给出nodes的总数以及一个edges二维数组,求连通分量的数量,遍历数组，用HashMap存当前点

复制代码

转载于:https://juejin.im/post/5c8277fc518825106a62afaa