Breadth First Search (Java) - ShuweiLeung/Thinking GitHub Wiki
1.（429:Easy）N-ary Tree Level Order Traversal
- 简单的一个BFS广度优先搜索的应用。
2.（310:Medium）（非常非常经典题）Minimum Height Trees
- 常规方法可以使用BFS或者DFS，对每个点都遍历一遍，求出所有点组成的树的高度，然后找出哪些高度最小的节点，可以通过不断更新最低高度来进行剪枝。实际上BFS和DFS的程序均出现超时。
- 正确的解题思路采用了不断删除叶子节点，逐渐逼近根节点的方法，在删除叶子节点的同时，会有一些新的节点成为叶子节点，于是继续循环删除，直至不能删除为止，那么剩下的节点就是高度最小的根。因为具有最短树高的树根一定位于最长路径的"中间位置"而不是边界位置。而在实现时，叶子结点的相邻结点数量应为1，即叶子结点的父节点。
该题除了不断删除叶子结点的思路外，还有寻找最短路径的思想，下次复习时再研究
3.（127:Medium）（非常非常经典题）Word Ladder
- 这道题目首先想到的是DFS，或曰backtracking，也就是每次都找到一个可能的路径，最后比较所有路径中最小的就是题目所求。这样做显然需要较多的时间，因为我们遍历了所有的可能性。那么，有没有更加快捷的方案呢？
- 答案是显然的，那就是BFS。首先，虽然题目中没有一个“图”的概念，但是我们可以假想构建一个图，其中图中的每个顶点都是我们的元素，点和点是如何联系起来的呢？如果一个单词通过改变一次字母，能够变成另外一个单词，我们称之为1 edit distance 距离（是不是想起了leetcode中edit distance那道题目了？）所以，图中的所有相邻元素都是edit distance 距离为1的元素。那么，我们只需要做BFS，哪里最先遇到我们的target word，那么我们的距离就是多少。如果遍历完所有的元素都没有找到target word，那么我们就返回0。
- 另外一个需要注意的地方就是，如果我们曾经遍历过某个元素，我会将其从字典中删除，以防以后再次遍历到这个元素。这里有几种情况：
- 以后再也遍历不到这个元素，那么我们删除它当然没有任何问题。
- 我们以后会遍历到该元素，又分为两种情况：
- 在本层我们就能遍历到该元素。也就是说，我们到达这个元素有两条路径，而且它们都是最短路径。举一个例子应该比较容易理解：比如hot->hog->dog->dig和hot->dot->dog->dig，那么在第一次遍历距离hot为1的元素时，我们找到了hog和dot。对hog遍历时，我们找到了dog，并且将其从字典中删除。那么在遍历距离dot为1的元素时，我们实际上是找不到dog的，因为已经被删除了。对于本题来说，是没有什么影响的，因为到dog距离都是3，到dig距离都是4。但是后面我们做word ladder 2的时候，如果没有考虑这个情况，将是非常致命的，因为题目要求输出最短路径的所有情况。
- 在更下层我们才能够遍历到该元素。比如hot->dot->dog->dig和hot->hat->dat->dag->dog->dig，如果第一次我们找到了dog并且将其删除，那么第二次我们实际上是找不到这个元素的。这样对于本题来说，没有任何影响。对于word ladder 2来说，因为也是要输出最短路径，所以也不会有任何影响。但是倘若我们要输出从起点到终点的所有路径，那么我们就要小心这种情况了。
- 那么在实现过程中，我们如何通过改变当前单词的一个字母来构成另外一个单词呢？请参看下面的代码：
for (int i = 0; i < curWord.length(); i++) {
char[] chars = curWord.toCharArray();
//下面的策略类似于BFS
for (char ch = 'a'; ch <= 'z'; ch++) {//改变当前字符串每一位的字符，查看改变一个字符后是否存在匹配的字符也在wordDict中出现
chars[i] = ch;
String newWord = new String(chars);
if (wordSet.contains(newWord)) {
toAdd.add(newWord);
wordSet.remove(newWord);
}
}
}
- 为了在上述代码中加速newWord的查找效率，我们将题目中的wordList改为Set集合，这样直接通过Hash值即可"快速"判断某个元素是否存在于集合中，大大加速查找效率。如果使用List集合进行查找，本质是对List进行逐个元素的遍历，则会超时。
- 参考链接：花花中文讲解(我没看)
4.（675:Hard）（非常非常经典题）Cut Off Trees for Golf Event
- 因为该题要求从低到高来砍树，所以我们首先将有树的结点按树高从小到大排序，并且记录树的位置。之后我们按照树高来砍树，即从当前位置走到下一个该砍树的位置，这个距离就利用BFS来算出。即给定起始位置和终点位置，通过向上下左右四个方向试探前进，BFS求出两点之间的最短距离。具体细节可以参看代码注释及参考视频。
- 参考链接：花花中文讲解视频
5.（126:Hard）（非常非常经典题）Word Ladder II
该题是Word Ladder I的升级版，没有做，下次复习时再研究学习。需要用到BFS来求最短路径，然后用DFS来回溯尝试该路径长度的所有组合
6.（317:Hard）（非常非常经典题）Shortest Distance from All Buildings
- 该题需要用到这么几个变量：distance[i][j]代表各个building到点grid[i][j]的最短距离之和，该距离是由building出发BFS得到的，其中BFS来求最短路径，从Building出发计算到各个点的距离是一个反向思维；reach[i][j]来代表grid[i][j]能到达的building个数；buildingNum来记录总的building数量。在以上变量都求出的基础上，遍历一次distance数组取到最小值，且对应的reach数量与buildingNum相等则为答案，否则返回-1。
- 具体思路可以参看代码实现及备注。
The main idea is the following:
Traverse the matrix. For each building, use BFS to compute the shortest distance from each '0' to this building. After we do this for all the buildings, we can get the sum of shortest distance from every '0' to all reachable buildings. This value is stored in 'distance[][]'. For example, if grid[2][2] == 0, distance[2][2] is the sum of shortest distance from this block to all reachable buildings.
Time complexity: O(number of 1)O(number of 0) ~ O(m^2n^2)
We also count how many building each '0' can be reached. It is stored in reach[][]. This can be done during the BFS. We also need to count how many total buildings are there in the matrix, which is stored in 'buildingNum'.
Finally, we can traverse the distance[][] matrix to get the point having shortest distance to all buildings. O(m*n)
The total time complexity will be O(m^2*n^2), which is quite high!
7.（752:Medium）（非常经典题）Open the Lock
- 计算最大最小值，一般有两种思路：DP和BFS，因为该题感觉更像是图，所以下面应用BFS进行求解
public int openLock(String[] deadends, String target) {
Queue<String> q = new LinkedList<>(); //有效的字符串，图中的中间结点
Set<String> deads = new HashSet<>(Arrays.asList(deadends)); //死胡同集合
Set<String> visited = new HashSet<>(); // BFS也算是递归的一种，所以也需要visited集合
q.offer("0000");
visited.add("0000");
int level = 0;
while(!q.isEmpty()) {
int n = q.size(); //当前层的有效字符串个数
while(n > 0) {
String s = q.poll();
if(deads.contains(s)) { //如果是无效字符串，将遍历过的数量减一
n --;
continue;
}
if(s.equals(target)) return level;
StringBuilder sb = new StringBuilder(s);
for(int i = 0; i < 4; i ++) { //修改每一个位置上的字符
char c = sb.charAt(i);
//因为密码锁转动的方向有两个
String s1 = sb.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + sb.substring(i + 1); //向前转动密码锁
String s2 = sb.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + sb.substring(i + 1); //向后转动密码锁
if(!visited.contains(s1) && !deads.contains(s1)) {
q.offer(s1);
visited.add(s1);
}
if(!visited.contains(s2) && !deads.contains(s2)) {
q.offer(s2);
visited.add(s2);
}
}
n --;
}
level ++; //进行下一层的BFS遍历
}
return -1;
}
8.（994:Easy）（非常经典题）Rotting Oranges
- 一个用BFS求最短路径的典型例子
public int orangesRotting(int[][] grid) {
if(grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int count_fresh = 0;
//Put the position of all rotten oranges in queue
//count the number of fresh oranges
for(int i = 0 ; i < rows ; i++) {
for(int j = 0 ; j < cols ; j++) {
if(grid[i][j] == 2) {
queue.offer(new int[]{i , j});
}
else if(grid[i][j] == 1) {
count_fresh++;
}
}
}
//if count of fresh oranges is zero --> return 0
if(count_fresh == 0) return 0;
int count = 0;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
//bfs starting from initially rotten oranges
while(!queue.isEmpty()) {
++count;
int size = queue.size();
for(int i = 0 ; i < size ; i++) {
int[] point = queue.poll();
for(int dir[] : dirs) {
int x = point[0] + dir[0];
int y = point[1] + dir[1];
//if x or y is out of bound
//or the orange at (x , y) is already rotten
//or the cell at (x , y) is empty
//we do nothing
if(x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] == 0 || grid[x][y] == 2) continue;
//mark the orange at (x , y) as rotten
grid[x][y] = 2;
//put the new rotten orange at (x , y) in queue
queue.offer(new int[]{x , y});
//decrease the count of fresh oranges by 1
count_fresh--;
}
}
}
return count_fresh == 0 ? count-1 : -1;
}
9.（1091:Easy）（非常非常经典题）Shortest Path in Binary Matrix
- 使用BFS求最短路径，只需要把过去BFS搜索时的4个方向扩充为8个方向即可
private int dir[][] = new int[][]{{0,1},{0,-1},{1,0},{-1,0},{1,-1},{-1,1},{-1,-1},{1,1}};
public int shortestPathBinaryMatrix(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
if(grid[0][0]==1 || grid[m-1][n-1]==1) {
return -1;
}
boolean[][] visited = new boolean[m][n];
visited[0][0] = true;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0,0});
int ans=0;
while (!queue.isEmpty()) {
int size = queue.size();
for(int i=0;i<size;i++) {
int[] pop = queue.remove();
if(pop[0]==m-1 && pop[1]==n-1) {
return ans+1;
}
for (int k=0;k<8;k++) {
int nextX = dir[k][0]+pop[0];
int nextY = dir[k][1]+pop[1];
if(nextX>=0 && nextX<m && nextY>=0 && nextY<n && !visited[nextX][nextY] && grid[nextX][nextY]==0) {
queue.add(new int[]{nextX,nextY});
visited[nextX][nextY]=true;
}
}
}
ans++;
}
return -1;
}
10.（773:Hard）（非常非常经典题）Sliding Puzzle
- 该题本质上就是一道BFS的题目，在每一次循环时，我们找到0的位置，然后将其与上下左右的相邻cell进行交换，然后判断是否达到终点。为了便于状态的比较，我们将二维数组转化成一位字符串，这样可以迅速比较状态是否已经达到最终的状态，具体代码如下：
public int slidingPuzzle(int[][] board) {
String target = "123450";
String start = "";
//为了方便状态的比较，将二维数组转化成一维字符串
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
start += board[i][j];
}
}
HashSet<String> visited = new HashSet<>();
// all the positions 0 can be swapped to
// dirs[i]表示当0在索引i上时，它能进行交换的相邻元素索引位置(棋盘已经转化成一维)
int[][] dirs = new int[][] { { 1, 3 }, { 0, 2, 4 },
{ 1, 5 }, { 0, 4 }, { 1, 3, 5 }, { 2, 4 } };
Queue<String> queue = new LinkedList<>();
queue.offer(start);
visited.add(start);
int res = 0;
while (!queue.isEmpty()) {
// level count, has to use size control here, otherwise not needed
int size = queue.size();
for (int i = 0; i < size; i++) {
String cur = queue.poll();
if (cur.equals(target)) {
return res;
}
int zero = cur.indexOf('0');
// swap if possible
for (int dir : dirs[zero]) {
String next = swap(cur, zero, dir);
if (visited.contains(next)) {
continue;
}
visited.add(next);
queue.offer(next);
}
}
res++;
}
return -1;
}
private String swap(String str, int i, int j) {
StringBuilder sb = new StringBuilder(str);
sb.setCharAt(i, str.charAt(j));
sb.setCharAt(j, str.charAt(i));
return sb.toString();
}
11.（909:Medium）（非常经典题）Snakes and Ladders
- 该题的难点有两个：1. 给定一个number，如何找到其在board中的行列坐标 2. 理解题意。该题描述的是从当前位置出发走一步，如果当前位置的
board[row][col] != -1，那么直接走到board[row][col]指定的位置，否则从number+1、number+2、number+3、number+4、number+5、number+6任选其一走到其位置上。 - 基于以上分析，我们应该使用BFS寻找从
number 1到number n*n的最短距离，并且使用visited数组去防止环。
public int snakesAndLadders(int[][] board) {
if(board == null || board.length == 0) return 0;
int n = board.length;
boolean[] visited = new boolean[n * n + 1];
int res = n * n;
Queue<Integer> q = new LinkedList<>();
q.offer(1);
int moves = 0;
while(!q.isEmpty()){
int size = q.size();
for(int i = 0; i < size; i++){
int cur = q.poll();
if(cur == n * n){
res = Math.min(res, moves);
}
for(int j = 1; j <= 6; j++){
int num = cur + j;
if(num > n * n) break;
//根据题目行方向交替的规律计算当前num的index
int row = n - (num - 1) / n - 1;
int col = (n - row) % 2 != 0 ? (num - 1) % n : n - (num - 1) % n - 1;
if(!visited[num]){
visited[num] = true;
if(board[row][col] == -1)
q.offer(num);
else {
//if(board[row][col] == cur) //如果有环直接跳过，因为有环的话，之前一定已经访问过，所以不需要额外进行判断
// continue;
q.offer(board[row][col]);
}
}
}
}
moves++;
}
return res == n * n ? -1 : res;
}
12.（815:Hard）（非常非常经典题）Bus Routes
- For each of the bus stop, we maintain all the buses (bus routes) that go through it. To do that, we use a HashMap, where bus stop number is the key and all the buses (bus routes) that go through it are added to an ArrayList.
- We use BFS, where we process elements in a level-wise manner. We add the Start bus stop in the queue. Next, when we enter the while loop, we add all the bus stops that are reachable by all the bus routes that go via the Start. Thus, if we have the input as
[[1, 2, 7], [3, 6, 7]]and Start as 6, then upon processing bus stop 6, we would add bus stops 3 and 7. With this approach, all the bus stops at a given level, are "equal distance" from the start node, in terms of number of buses that need to be changed. - To avoid loops, we also maintain a HashSet that stores the buses that we have already visited.
- Note that while in this approach, we use each stop for doing BFS, one could also consider each bus (route) also for BFS.
- 这里需要注意一点，visited set中应该存储的是已经乘坐的bus，而不是已经访问过的stop，因为bus的数量通常是远小于stop的数量，如果visited集合中存储的是stop的话，会超时，最后几个test case无法通过。具体的思路请参看代码实现及备注。