深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜BFS)是圖論相關(guān)算法的基礎(chǔ)，先學(xué)習(xí)這兩個(gè)思想（工具）為后續(xù)學(xué)習(xí)更多算法做準(zhǔn)備型檀。
迷宮式搜索
學(xué)習(xí)深搜通常用走迷宮這一問(wèn)題來(lái)入門。
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）售睹。
問(wèn)總共有多少條不同的路徑？
例如可训，上圖是一個(gè)7 x 3 的網(wǎng)格昌妹。有多少可能的路徑生真？
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-paths
首先創(chuàng)建一個(gè)二維數(shù)組，作為地圖int[3][7] map;（int[3][7]或者int[7][3]都行并不影響捺宗，就按照?qǐng)D上定義3行7列）定義i為行數(shù)，j為列數(shù)川蒙，初始點(diǎn)為（0,0）蚜厉，終點(diǎn)為（2,6）。
據(jù)DFS的思想畜眨，我們先設(shè)定一個(gè)初始方向→昼牛，即j+1。
模擬下走路過(guò)程
（0,0）->（0,1）->（0,2）->（0,3）->（0,4）->（0,5）->（0,6）
當(dāng)橫向走到頭時(shí)康聂，按照第二方向↓贰健，即i+1繼續(xù)移動(dòng)
（0,6）->（1,6）
繼續(xù)往→不通，向下移動(dòng)
（1,6）->（2,6）
走到了終點(diǎn)處恬汁，計(jì)有一條路徑從（0,0）->...（2,6）
接著是一個(gè)回溯的過(guò)程伶椿，因?yàn)闂l件中只允許往右和往下走，執(zhí)行完兩個(gè)情況后即退出遞歸氓侧，從
（2,6）->（1,6）->（0,6）->（0,5）
繼續(xù)執(zhí)行從（0,5）點(diǎn)往下走到（1,5）->(1,6)->(2,6),又走到了終點(diǎn)脊另。
接下來(lái)看代碼實(shí)現(xiàn)
private static int count;
public static void main(String[] args) {
count = 0;
dfs(0, 0, 3, 7);
System.out.println(count);
}
/**
* @param x 當(dāng)前所在行
* @param y 當(dāng)前所在列
* @param m 總行數(shù)
* @param n 總列數(shù)
*/
public static void dfs(int x, int y, int m, int n) {
//在地圖外不能走直接返回
if (x >= m || y >= n) {
return;
}
//到達(dá)終點(diǎn)，記一條路徑
if (x == m - 1 && y == n - 1) {
count++;
System.out.println("到達(dá)終點(diǎn)累計(jì):"+count);
return;
}
//向右走
System.out.println("(" + x + "," + y + ")向右走到" + "(" + x + "," + (y + 1) + ")");
dfs(x, y + 1, m, n);
System.out.println("(" + x + "," + (y + 1) + ")退回" + "(" + x + "," + y + ")");
//向下走
System.out.println("(" + x + "," + y + ")-向下走到" + "(" + (x + 1) + "," + y + ")");
dfs(x + 1, y, m, n);
System.out.println("(" + (x + 1) + "," + y + ")退回" + "(" + x + 1 + "," + y + ")");
}
通過(guò)打印日志和調(diào)試代碼的方式能夠了解深搜的過(guò)程约巷。（leetcode上這題用深搜決定超時(shí)的偎痛，原題是直接動(dòng)態(tài)規(guī)劃或者排列組合，只是題目比較形象來(lái)演示這個(gè)例子独郎。根據(jù)經(jīng)驗(yàn)?zāi)苁褂蒙钏训念}的數(shù)據(jù)大概60以下踩麦，太深的層數(shù)直接棧溢出了）
63. 不同路徑 II
這題是包含障礙不能走的情況，可以自己試試氓癌。
二叉樹搜索
在數(shù)據(jù)結(jié)構(gòu)的題目中谓谦，經(jīng)常有一些如打印中序遍歷、先序遍歷顽铸、后序遍歷茁计，最深層級(jí)之類的題。這些題都是通過(guò)深搜去查找谓松，去遍歷星压。
二叉樹的結(jié)構(gòu)與上面迷宮比較類似，先早左節(jié)點(diǎn)再找右節(jié)點(diǎn)（反之也隨意看題目需要）鬼譬。
private void dfs(TreeNode root) {
dfs(root.left);
dfs(root.right);
}
一個(gè)簡(jiǎn)單的二叉樹搜索的框架就搭好了娜膘。
除了向下搜索的過(guò)程，還有必要的返回條件优质】⑻埃總不能一直往死里搜军洼，搜他個(gè)棧溢出吧。
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
dfs(root.right);
}
有了以上二叉樹搜索的模板演怎，同上面一樣拿個(gè)題做一下匕争。
給定一個(gè)二叉樹，找出其最大深度爷耀。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)甘桑。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例：
給定二叉樹 [3,9,20,null,null,15,7]歹叮，
3
/
9 20
/
15 7
返回它的最大深度 3 跑杭。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
求的是樹的最大深度，我們需要知道當(dāng)前節(jié)點(diǎn)的深度咆耿，往下搜則深度+1德谅，取左節(jié)點(diǎn)與右節(jié)點(diǎn)中較大的數(shù)，即為最終結(jié)果萨螺。
代碼實(shí)現(xiàn)窄做。
/**
* @param root 當(dāng)前節(jié)點(diǎn)
* @param cur 當(dāng)前深度
* @return
*/
private int dfs(TreeNode root, int cur) {
if (root == null) {
return cur;
}
cur++;
int lh = dfs(root.left, cur);
int rh = dfs(root.right, cur);
return Math.max(lh, rh);
}
抽象型搜索
以上兩個(gè)例子是比較具體化的深搜例子，可以明確搜的方向（步驟）⌒加兀現(xiàn)在來(lái)解決一個(gè)常見的趣味題浸策。
有兩個(gè)容量分別為 x升 和 y升 的水壺以及無(wú)限多的水。請(qǐng)判斷能否通過(guò)使用這兩個(gè)水壺惹盼，從而可以得到恰好 z升 的水庸汗？
如果可以，最后請(qǐng)用以上水壺中的一或兩個(gè)來(lái)盛放取得的 z升 水手报。
你允許：
裝滿任意一個(gè)水壺
清空任意一個(gè)水壺
從一個(gè)水壺向另外一個(gè)水壺倒水蚯舱，直到裝滿或者倒空
示例 1: (From the famous "Die Hard" example)
輸入: x = 3, y = 5, z = 4
輸出: True
示例 2:
輸入: x = 2, y = 6, z = 5
輸出: False
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/water-and-jug-problem
本題就沒(méi)有上面走迷宮和二叉樹那么直觀的具體的搜索路徑，且方法不止深搜掩蛤，但是我們?nèi)钥梢园凑丈钏训乃枷雵L試解決枉昏。
首先，列出所有可能的操作行為
- 給x水壺中倒水
- 給y水壺中倒水
- 將x水壺中的水倒到y(tǒng)水壺
- 將y水壺中的水倒到x水壺
- 將x水壺中的水倒掉
- 將y水壺中的水倒掉
根據(jù)搜索狀態(tài)寫出遞歸代碼
/**
* @param i 當(dāng)前x水壺中的水量
* @param j 當(dāng)前y水壺中的水量
* @param x x水壺的容量
* @param y y水壺的容量
* @param z 目標(biāo)水量
*/
private void dfs(int i, int j, int x, int y, int z) {
// 1.給x水壺中倒水
dfs(x, j, x, y, z);
// 2.給y水壺中倒水
dfs(i, y, x, y, z);
//3.將x水壺中的水倒到y(tǒng)水壺,這里分倒不滿和倒不下的情況
if (j + i <= y) {
//倒不滿y水壺(剛好)
dfs(0, j + i, x, y, z);
} else {
//倒?jié)My水壺剩下的水保留在x水壺中
dfs(i + j - y, y, x, y, z);
}
//4.將y水壺中的水倒到x水壺,同樣分倒不滿和倒不下的情況
if (j + i < x) {
dfs(j + i, 0, x, y, z);
} else {
dfs(x, i + j - x, x, y, z);
}
//5.將x水壺中的水倒掉
dfs(0, j, x, y, z);
//6.將y水壺中的水倒掉
dfs(i, 0, x, y, z);
}
接著寫遞歸邊界揍鸟，當(dāng)x或y中的水與目標(biāo)水量z相同時(shí)兄裂，或兩個(gè)水壺中的水加起來(lái)與z相同時(shí)，即得到了結(jié)果阳藻。
private boolean dfs(int i, int j, int x, int y, int z) {
if (i == z || j == z || (i + j == z)) {
return true;
}
......
}
加上打印當(dāng)年?duì)顟B(tài)方法一運(yùn)行
System.out.println("x水壺水量:" + i + " y水壺水量:" + j);
......
x水壺水量:5 y水壺水量:0
x水壺水量:5 y水壺水量:0
x水壺水量:5 y水壺水量:0
Exception in thread "main" java.lang.StackOverflowError
想到水滿的情況不需要再加水和水空的時(shí)候不需再倒水的情況晰奖，于是加上遞歸條件，優(yōu)化了下代碼腥泥。
private boolean dfs(int i, int j, int x, int y, int z) {
......
// 1.給x水壺中倒水
if (i != x) {
if (dfs(x, j, x, y, z)) {
return true;
}
}
// 2.給y水壺中倒水
if (j != y) {
if (dfs(i, y, x, y, z)) {
return true;
}
}
// y水壺滿了不能倒
if (j != y) {
//3.將x水壺中的水倒到y(tǒng)水壺,這里分倒不滿和倒不下的情況
if (j + i <= y) {
//倒不滿y水壺(剛好)
if (dfs(0, j + i, x, y, z)) {
return true;
}
} else {
//倒?jié)My水壺剩下的水保留在x水壺中
if (dfs(i + j - y, y, x, y, z)) {
return true;
}
}
}
// x水壺滿了不能倒
if (i != x) {
//4.將y水壺中的水倒到x水壺,同樣分倒不滿和倒不下的情況
if (j + i < x) {
if (dfs(j + i, 0, x, y, z)) {
return true;
}
} else {
if (dfs(x, i + j - x, x, y, z)) {
return true;
}
}
}
//5.將x水壺中的水倒掉
if (i != 0) {
if (dfs(0, j, x, y, z)) {
return true;
}
}
//6.將y水壺中的水倒掉
if (j != 0) {
if (dfs(i, 0, x, y, z)) {
return true;
}
}
return false;
}
仍然匾南。。蛔外。
x水壺水量:0 y水壺水量:3
x水壺水量:5 y水壺水量:3
x水壺水量:0 y水壺水量:3
x水壺水量:5 y水壺水量:3
Exception in thread "main" java.lang.StackOverflowError
實(shí)際問(wèn)題與上面一樣蛆楞，出現(xiàn)了重復(fù)的狀態(tài)溯乒。于是我們尋求一種方法去記錄已經(jīng)出現(xiàn)過(guò)的(i,j)狀態(tài)。這里我采用的是二維數(shù)組記錄的方式豹爹，類似x裆悄、y已經(jīng)走過(guò)，就標(biāo)記為1臂聋，下次變成這個(gè)狀態(tài)的時(shí)候就直接返回不往下遞歸灯帮。
private boolean[][] map;
public boolean canMeasureWater(int x, int y, int z) {
map = new boolean[x + 1][y + 1];
return dfs(0, 0, x, y, z);
}
private boolean dfs(int i, int j, int x, int y, int z) {
//已經(jīng)走過(guò)該狀態(tài)，直接返回
if (map[i][j]) {
return false;
}
//標(biāo)位已走
map[i][j] = true;
......
}
提交代碼完事關(guān)機(jī)逻住。 結(jié)果。迎献。瞎访。。
20 / 34 個(gè)通過(guò)測(cè)試用例
狀態(tài)：超出內(nèi)存限制
最后執(zhí)行的輸入：
22003
31237
1
其實(shí)到這里吁恍，深搜部分要講的已經(jīng)講完了扒秸，但是題目還是要A掉。（map這種方式超內(nèi)存冀瓦。用String hash = String.format("%09d%09d", i, j)拼接成hash值極其費(fèi)時(shí)伴奥。用遞歸深搜的方式又java.lang.StackOverflowError，最后勉強(qiáng)卡掉）
總結(jié)
通過(guò)上面幾個(gè)例題翼闽，可以總結(jié)出寫深搜題的一些套路拾徙。
- 狀態(tài)如何改變，通過(guò)遞歸去遍歷（dfs（x,x,x））感局；
- 設(shè)置邊界條件尼啡，搜到頭了需要回溯，不可能無(wú)邊界的遞歸下去（return）询微；
- 通過(guò)一些條件的判斷進(jìn)行剪枝崖瞭，減少遞歸的層級(jí)和次數(shù)。(if（xxx）)
搜索的題目還是蠻有意思的撑毛，一個(gè)題目如果問(wèn)有沒(méi)有結(jié)果书聚，能不能到達(dá)，或者有幾種方式（基本超時(shí)）藻雌，都能夠用深搜的方式去解決雌续，不一定能解決題目，但可能可以從答案中反推規(guī)律蹦疑。
比較經(jīng)典的還有 八皇后 Sticks等西雀，有興趣的可以自行嘗試。
