DFS和BFS講解及Leetcode刷題小結（2）（JAVA）
上一篇文章解決了DFS的問題，這次來解決BFS的問題就簡單多了
DFS實現重要依賴於堆疊/遞迴 ，較為簡單的解決了如何遍歷所有元素，以及尋求“終點”的問題。
但是，DFS雖然可以查詢到到達路徑，但是卻找不到最短的路徑，針對這一問題，給出了BFS(廣度優先遍歷)的演算法。
首先，先給出BFS的基本過程：
與DFS不同的是，這次不再是每個分叉路口一個一個走了，而是全部，同時遍歷，直到找到終點，所對應的“層數”便是最短路徑所需要的步數，BFS像是在剝洋蔥，一層一層的撥開，最後到達終點。
如何實現呢？
我們利用佇列來實現BFS，虛擬碼如下：
int BFS(Node root, Node target) {
Queue<Node> queue;// 建立佇列
int step = 0;// 建立行動步數
// initialize
add root to queue;
// BFS
while (queue is not empty) {
step = step + 1;
// 記錄此時的佇列大小
int size = queue.size();
for (int i = 0; i < size; ++i) { //遍歷佇列中的元素，並將新元素加入到佇列中
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
add next to queue;//加入查詢的方向
}
remove the first node from queue;
}
}
return -1;// 沒有找到目標返回-1
}
佇列整體由兩個迴圈構成：外層迴圈檢視佇列是否為空（為空表示元素已經遍歷完畢），內層迴圈用於對當前節點的遍歷，以及加入新節點，這裡要注意：內層迴圈的次數size應為queue.size()賦予，而不能直接使用queue.size()，因為在內迴圈中會對佇列進行操作，從而使得佇列的長度不停變化。
內層迴圈代表著一層遍歷“一層洋蔥皮”，所以在外層遍歷與內層遍歷直接需要加入步數的記錄，最後演算法結束時對應步數就是最短路徑。
下面來看幾道例題：
#1 Number of Islands
Given a 2d grid map of '1' s (land) and '0' s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
<strong>Input:</strong> 11110 11010 11000 00000 <strong>Output:</strong> 1
Example 2:
Input: 11000 11000 00100 00011 Output: 3
仍然是那道找小島的題目，下面來用BFS來進行求解：
public int numIslands(char[][] grid) {
Queue<Integer> queue = new LinkedList<>(); //建立佇列
int num = 0 ;
for(int i = 0 ; i < grid.length ; i ++)
{
for(int j = 0 ; j < grid[0].length ; j ++)
{
if(grid[i][j] == '1')
{
bfs(i,j,queue,grid) ; //使用BFS來進行遍歷
num ++ ;
}
}
}
return num ;
}
public void bfs(int p , int q , Queue<Integer> queue,char[][] grid)
{
int m = grid.length ;
int n = grid[0].length ;
int t = Math.max(m,n) ; //這裡要使用一維佇列來表示二維的陣列，對原來的陣列進行重新編碼，為了避免譯碼的錯誤，
// 這裡求出二維陣列行列的最大值
int w = p*t + q ; //對陣列進行編碼
queue.offer(w) ;
grid[p][q] = '0' ;
while(!queue.isEmpty())
{
int s = queue.poll() ; //由於所需要解決的問題不在於求最短路徑，而在於遍歷，使用沒有記錄步數
int i = s/t ; //對行進行譯碼
int j = s%t ; //對列進行譯碼
if(i + 1 < m && grid[i+1][j] != '0') //上
{
queue.offer((i+1)*t + j);
grid[i+1][j] = '0';
}
if(i - 1 >= 0&& grid[i-1][j] != '0') //下
{
queue.offer((i-1)*t + j);
grid[i-1][j] = '0';
}
if(j - 1 >= 0&& grid[i][j-1] != '0') //左
{
queue.offer(i*t + j-1);
grid[i][j-1] = '0';
}
if(j + 1 < n && grid[i][j+1] != '0') //右
{
queue.offer(i*t + j+1);
grid[i][j+1] = '0';
}
}
}
}
可以看到在遍歷的問題上，BFS相對於DFS並沒有什麼優勢，編寫起來反而比較麻煩，因此，在遍歷元素的問題上使用DFS比較好
#2 Open the Lock
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' . The wheels can rotate freely and wrap around: for example we can turn '9' to be '0' , or '0' to be '9' . Each move consists of turning one wheel one slot.
The lock initially starts at '0000' , a string representing the state of the 4 wheels.
You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
Example 1:
<strong>Input:</strong> deadends = ["0201","0101","0102","1212","2002"], target = "0202" <strong>Output:</strong> 6 <strong>Explanation:</strong> A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202". Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid, because the wheels of the lock become stuck after the display becomes the dead end "0102".
Example 2:
<strong>Input:</strong> deadends = ["8888"], target = "0009" <strong>Output:</strong> 1 <strong>Explanation:</strong> We can turn the last wheel in reverse to move from "0000" -> "0009".
Example 3:
<strong>Input:</strong> deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" <strong>Output:</strong> -1 <strong>Explanation:</strong> We can't reach the target without getting stuck.
Example 4:
<strong>Input:</strong> deadends = ["0000"], target = "8888" <strong>Output:</strong> -1
Note:
- The length of
deadendswill be in the range[1, 500]. -
targetwill not be in the listdeadends. - Every string in
deadendsand the stringtargetwill be a string of 4 digits from the 10,000 possibilities'0000'to'9999'.
這道問題要求找到最短的搜尋路徑，顯然使用BFS比較好，程式碼如下：
class Solution {
public int openLock(String[] deadends, String target) {
if(target == null) return -1 ;
Queue<String> queue = new LinkedList<>();
HashSet<String> set = new HashSet<String>(Arrays.asList(deadends)); //建立hashset來儲存deadends和訪問過的節點
int times = -1 ;
queue.offer("0000") ; //將初始起點入隊
while(!queue.isEmpty()) //開始遍歷相鄰的各個節點
{
times ++ ;
int size = queue.size() ;
for(int t = 0 ; t < size ; t ++)
{
String cur = queue.poll();
if(set.contains(cur)) continue ;
if(cur.compareTo(target) == 0) return times;
set.add(cur) ;
for(int i = 0 ; i < 4 ; i++)
{
for(int j = -1 ; j < 2 ; j += 2) //4個數位進行+，- 1運算，共有8個方向
{
char[] temp = cur.toCharArray();
temp[i] = (char)((temp[i] - '0' + j + 10)%10 + '0'); // 將字元轉化為數字
queue.offer(new String(temp));
}
}
}
}
return -1;
}
}
#3 Perfect Squares
Given a positive integer n , find the least number of perfect square numbers (for example, 1, 4, 9, 16, ... ) which sum to n .
Example 1:
<strong>Input:</strong> <em>n</em> = <code>12</code> <strong>Output:</strong> 3 <strong>Explanation: </strong><code>12 = 4 + 4 + 4.</code>
Example 2:
Input: n =13Output: 2 Explanation:13 = 4 + 9.
程式碼如下：
class Solution {
public int numSquares(int n) {
Queue<Integer> queue = new LinkedList<>();
HashSet<Integer> set = new HashSet<>();
int res = 0 ;
queue.offer(0) ;
while(!queue.isEmpty())
{
res ++;
int size = queue.size();
for(int i = 0 ; i < size ; i ++)
{
int cur = queue.poll() ;
int j = 1 ;
while(cur + j*j <= n) //平方和小於目標數字的都是節點的相鄰節點
{
int temp = cur + j*j ;
if(temp == n) return res ;
j ++ ;
if(set.contains(temp)) continue ;
queue.offer(temp) ;
set.add(temp) ; //set用作記錄路徑
}
}
}
return -1 ;
}
}