算法模板：秒杀BFS算法以及相关例题

小鱼儿 2022-11-06 01:50 120阅读 0赞

### 性价比最高的算法-BFS ###

*   *  1.适用场景
     *  2.算法模板
     *  3.相关例题
     *   *  3.1 克隆图 Clone Graph
         *  3.2 词语接龙 Word Ladder
         *  3.3 岛屿数量 Number of Islands
     *  总结

> 宽度优先搜索，又称BFS，在面试中出现频率仅次于双指针，由于其上手快，难度较低，性价比很高！推荐各位同学们优先掌握。

## 1.适用场景 ##

BFS的使用场景可分为三种：

1.  连通块问题

*  通过一个点找到图中连通的所有点
 *  非递归的方式找所有方案

1.  分层遍历

*  图的层次遍历
 *  简单图最短路径（复杂图:Floyd, Dijkstra, Bellman-ford, SPFA) --> 面试中一般不考复杂图最短路径问题）

1.  拓扑排序

*  求任意拓扑序
 *  求是否有拓扑序
 *  求字典序的最小拓扑序

## 2.算法模板 ##

/* // Definition for a Node. class Node { public int val; public List<Node> neighbors; public Node() { val = 0; neighbors = new ArrayList<Node>(); } } */
    
    //由于链表比数组慢，因此推荐使用new ArrayDeque不建议new LinkedList
    Queue<Node> queue = new ArrayDeque<>();
    HashMap<Node,Integer> distance = new HashMap<>();
    
    //1.初始化：
    //2.把初始节点放到queue中，如果有多个就都放进去；
    //3.标记初始节点的distance为0，记录在distance的hashmap中；
    //4.distacne有两个作用，一是判断是否遍历过，二是记录离起点的位置。
    queue.offer(node);
    distance.put(node,0);
    
    //2.不断访问队列：
    //while 循环 + 每次pop 队列中的一个点出来。
    while(!queue.isEmpty()){ 
    	Node node = queue.pop();
    	//3.扩展相邻节点
    	//pop 出的节点的相邻节点，加入队列并在distance中存储距离
    	for(Node neighbour : node.neighbours()){ 
    		if(distance.containsKey(neighbour)){ 
    		continue;
    		}
    		
    		queue.offer(neighbour);
    		distance.put(neighbour, distance.get(node) + 1);
    	}
    }

## 3.相关例题 ##

接下来，让我们拿几道LeetCode上的题目练练手，运用以上的模板。

### 3.1 克隆图 Clone Graph ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70]

[LeetCode 133.克隆图][LeetCode 133.]

class Solution { 
        public Node cloneGraph(Node node) { 
            if(node == null){ 
                return null;
            }
            //step1: find nodes
            List<Node> nodes = findNodesByBFS(node);
            //step2: copy nodes
            Map<Node,Node> mapping = copyNodes(nodes);
            //step3: copy edges
            copyEdges(nodes,mapping);
            return mapping.get(node);
        }
    
        private List<Node> findNodesByBFS(Node node){ 
            Queue<Node> queue = new ArrayDeque<>();
            Set<Node> visited = new HashSet<>();
            queue.offer(node);
            visited.add(node);
            while(!queue.isEmpty()){ 
                Node curNode = queue.poll();
                for(Node neighbor : curNode.neighbors){ 
                    if(visited.contains(neighbor)){ 
                        continue;
                    }
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
            return new LinkedList<>(visited);
        }
    
        private Map<Node,Node>copyNodes(List<Node> nodes){ 
            Map<Node, Node> mapping = new HashMap<>();
            for(Node node : nodes){ 
                mapping.put(node, new Node(node.val));
            }
            return mapping;
        }
    
        private void copyEdges(List<Node> nodes, Map<Node,Node> mapping){ 
            for(Node node : nodes){ 
                Node newNode = mapping.get(node);   
                for(Node neighbor : node.neighbors){ 
                    Node newNeighbor = mapping.get(neighbor);
                    newNode.neighbors.add(newNeighbor);
                }
            }
        }
    }

### 3.2 词语接龙 Word Ladder ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70 1]

[LeetCode 127.单词接龙][LeetCode 127.]

public class Solution { 
        public int ladderLength(String start, String end, List<String> wordList) { 
            Set<String> dict = new HashSet<>();
            for (String word : wordList) {     
            //将wordList中的单词加入dict, 有一个test case里面wordlist很长，会超时。所以要转成set，因为list的contains操作是O(n)，set的contains操作是O(1)
                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()) { 			//开始bfs
                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)) { 				//如果dict中包含新单词，存入nextWords
                        nextWords.add(nextWord);
                    }
                }
            }
            return nextWords;									//构造当前单词的全部下一步方案
        }
    }

### 3.3 岛屿数量 Number of Islands ###

[LeetCode 200. 岛屿数量][LeetCode 200.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70 2]

class Coordinate { 
        int x, y;
        public Coordinate(int x, int y) { 
            this.x = x;
            this.y = y;
        }
    }
    
    public class Solution { 
        /** * @param grid a boolean 2D matrix * @return an integer */
        int[] deltaX = { 0, 1, -1, 0};
        int[] deltaY = { 1, 0, 0, -1};
    
        public int numIslands(char[][] grid) { 
            
            
            if (grid == null || grid.length == 0) { 
                return 0;
            }
            if (grid[0] == null || grid[0].length == 0) { 
                return 0;
            }
            
            int islands = 0;
            int n = grid.length, m = grid[0].length;
            boolean[][] grids = new boolean[n][m];
            for (int i = 0; i < n; i++) { 
                for (int j = 0; j < m; j++) { 
                    if (grid[i][j] == '1') { 
                        grids[i][j] = true;
                    }else{ 
                        grids[i][j] = false;
                    }
                }
            }
    
            boolean[][] visited = new boolean[n][m];
            for (int i = 0; i < n; i++) { 
                for (int j = 0; j < m; j++) { 
                    if (grids[i][j] && !visited[i][j]) { 
                        bfs(grids, i, j, visited);
                        islands++;
                    }
                }
            }
            
            return islands;
        }
        
        private void bfs(boolean[][] grid, int x, int y, boolean[][] visited) { 
            Queue<Coordinate> queue = new ArrayDeque<>();
            queue.offer(new Coordinate(x, y));
            visited[x][y] = true;
            
            while (!queue.isEmpty()) { 
                Coordinate coor = queue.poll();
                for (int direction = 0; direction < 4; direction++) { 
                    int newX = coor.x + deltaX[direction];
                    int newY = coor.y + deltaY[direction];
                    if (!isVaild(grid, newX, newY, visited)) { 
                        continue;
                    }
                    queue.offer(new Coordinate(newX, newY));
                    visited[newX][newY] = true;
                }
            }
        }
        
        private boolean isVaild(boolean[][] grid, int x, int y, boolean[][] visited) { 
            int n = grid.length, m = grid[0].length;
            if (x < 0 || x >= n || y < 0 || y >= m) { 
                return false;
            }
            if (visited[x][y]) { 
                return false;
            }
            return grid[x][y];
        }
    }

## 总结 ##

能够用 BFS 解决的问题，一定不要用 DFS 去做! 因为用 Recursion 实现的 DFS 可能造成 StackOverflow!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70]: /images/20221023/597761d497f84d2e8ebace454e5037b7.png
[LeetCode 133.]: https://leetcode-cn.com/problems/clone-graph/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70 1]: /images/20221023/860dce79dc2646d795a1a5250f967b06.png
[LeetCode 127.]: https://leetcode-cn.com/problems/word-ladder/
[LeetCode 200.]: https://leetcode-cn.com/problems/number-of-islands/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70 2]: /images/20221023/d3de4bb2384948d48123f7cff4a933b4.png