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
- 序列化
- 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 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 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 Listlist1 = new ArrayList<>(); List list2 = list1; // soft copy -> list1.add() 会同时影响list1 和 list2 List 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 nodes = getNodes(node); // copy nodes, store the old->new mapping information in a hash map HashMap 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 getNodes(UndirectedGraphNode node) { Queue queue = new LinkedList (); HashSet 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 (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 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 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 =0 && yy 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 wordList) { Set dict = new HashSet<>(); for (String word : wordList) { dict.add(word); } if (start.equals(end)) { return 1; } HashSet hash = new HashSet (); Queue queue = new LinkedList (); 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 getNextWords(String word, Set dict) { ArrayList nextWords = new ArrayList (); 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 > findLadders(String start, String end, Set dict) { List > ladders = new ArrayList >(); Map > map = new HashMap >(); Map distance = new HashMap (); dict.add(start); dict.add(end); bfs(map, distance, start, end, dict); List path = new ArrayList (); dfs(ladders, path, end, start, distance, map); return ladders; } void dfs(List > ladders, List path, String crt, String start, Map distance, Map > map) { path.add(crt); if (crt.equals(start)) { Collections.reverse(path); ladders.add(new ArrayList (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 > map, Map distance, String start, String end, Set dict) { Queue q = new LinkedList (); q.offer(start); distance.put(start, 0); for (String s : dict) { map.put(s, new ArrayList ()); } while (!q.isEmpty()) { String crt = q.poll(); List 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 expand(String crt, Set dict) { List expansion = new ArrayList (); 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 qx = new LinkedList<>(); Queue 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 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 (); } for (int[] pre : prerequisites) { indegree[pre[0]]++; edges[pre[1]].add(pre[0]); } int count = 0; Queue 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 deadSet = new HashSet (); String start = "0000"; for(String dead : deadends){ if(dead.equals(start)) { return -1; } deadSet.add(dead); } Queue queue = new LinkedList (); 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 visited = new HashSet<>(); Queue q = new LinkedList<>(); HashMap > 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 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 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 > 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 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 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存当前点
复制代码