深度优先搜索（DFS）和广度优先搜BFS)是图论相关算法的基础，先学习这两个思想（工具）为后续学习更多算法做准备。
迷宫式搜索
学习深搜通常用走迷宫这一问题来入门。
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
image.png
例如，上图是一个7 x 3 的网格。有多少可能的路径？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
首先创建一个二维数组，作为地图int[3][7] map;（int[3][7]或者int[7][3]都行并不影响，就按照图上定义3行7列）定义i为行数，j为列数，初始点为（0,0），终点为（2,6）。
据DFS的思想，我们先设定一个初始方向→，即j+1。
模拟下走路过程
（0,0）->（0,1）->（0,2）->（0,3）->（0,4）->（0,5）->（0,6）
当横向走到头时，按照第二方向↓，即i+1继续移动
（0,6）->（1,6）
继续往→不通，向下移动
（1,6）->（2,6）
走到了终点处，计有一条路径从（0,0）->...（2,6）
接着是一个回溯的过程，因为条件中只允许往右和往下走，执行完两个情况后即退出递归，从
（2,6）->（1,6）->（0,6）->（0,5）
继续执行从（0,5）点往下走到（1,5）->(1,6)->(2,6),又走到了终点。
接下来看代码实现
private static int count;
public static void main(String[] args) {
count = 0;
dfs(0, 0, 3, 7);
System.out.println(count);
}
/**
* @param x 当前所在行
* @param y 当前所在列
* @param m 总行数
* @param n 总列数
*/
public static void dfs(int x, int y, int m, int n) {
//在地图外不能走直接返回
if (x >= m || y >= n) {
return;
}
//到达终点，记一条路径
if (x == m - 1 && y == n - 1) {
count++;
System.out.println("到达终点累计:"+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 + ")");
}
通过打印日志和调试代码的方式能够了解深搜的过程。（leetcode上这题用深搜决定超时的，原题是直接动态规划或者排列组合，只是题目比较形象来演示这个例子。根据经验能使用深搜的题的数据大概60以下，太深的层数直接栈溢出了）
63. 不同路径 II
这题是包含障碍不能走的情况，可以自己试试。
二叉树搜索
在数据结构的题目中，经常有一些如打印中序遍历、先序遍历、后序遍历，最深层级之类的题。这些题都是通过深搜去查找，去遍历。
二叉树的结构与上面迷宫比较类似，先早左节点再找右节点（反之也随意看题目需要）。
private void dfs(TreeNode root) {
dfs(root.left);
dfs(root.right);
}
一个简单的二叉树搜索的框架就搭好了。
除了向下搜索的过程，还有必要的返回条件。总不能一直往死里搜，搜他个栈溢出吧。
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
dfs(root.right);
}
有了以上二叉树搜索的模板，同上面一样拿个题做一下。
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
求的是树的最大深度，我们需要知道当前节点的深度，往下搜则深度+1，取左节点与右节点中较大的数，即为最终结果。
代码实现。
/**
* @param root 当前节点
* @param cur 当前深度
* @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);
}
抽象型搜索
以上两个例子是比较具体化的深搜例子，可以明确搜的方向（步骤）。现在来解决一个常见的趣味题。
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许：
装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous "Die Hard" example)
输入: x = 3, y = 5, z = 4
输出: True
示例 2:
输入: x = 2, y = 6, z = 5
输出: False
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/water-and-jug-problem
本题就没有上面走迷宫和二叉树那么直观的具体的搜索路径，且方法不止深搜，但是我们仍可以按照深搜的思想尝试解决。
首先，列出所有可能的操作行为
- 给x水壶中倒水
- 给y水壶中倒水
- 将x水壶中的水倒到y水壶
- 将y水壶中的水倒到x水壶
- 将x水壶中的水倒掉
- 将y水壶中的水倒掉
根据搜索状态写出递归代码
/**
* @param i 当前x水壶中的水量
* @param j 当前y水壶中的水量
* @param x x水壶的容量
* @param y y水壶的容量
* @param z 目标水量
*/
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水壶,这里分倒不满和倒不下的情况
if (j + i <= y) {
//倒不满y水壶(刚好)
dfs(0, j + i, x, y, z);
} else {
//倒满y水壶剩下的水保留在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);
}
接着写递归边界，当x或y中的水与目标水量z相同时，或两个水壶中的水加起来与z相同时，即得到了结果。
private boolean dfs(int i, int j, int x, int y, int z) {
if (i == z || j == z || (i + j == z)) {
return true;
}
......
}
加上打印当年状态方法一运行
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
想到水满的情况不需要再加水和水空的时候不需再倒水的情况，于是加上递归条件，优化了下代码。
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水壶,这里分倒不满和倒不下的情况
if (j + i <= y) {
//倒不满y水壶(刚好)
if (dfs(0, j + i, x, y, z)) {
return true;
}
} else {
//倒满y水壶剩下的水保留在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
实际问题与上面一样，出现了重复的状态。于是我们寻求一种方法去记录已经出现过的(i,j)状态。这里我采用的是二维数组记录的方式，类似x、y已经走过，就标记为1，下次变成这个状态的时候就直接返回不往下递归。
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) {
//已经走过该状态，直接返回
if (map[i][j]) {
return false;
}
//标位已走
map[i][j] = true;
......
}
提交代码完事关机。 结果。。。。
20 / 34 个通过测试用例
状态：超出内存限制
最后执行的输入：
22003
31237
1
其实到这里，深搜部分要讲的已经讲完了，但是题目还是要A掉。（map这种方式超内存。用String hash = String.format("%09d%09d", i, j)拼接成hash值极其费时。用递归深搜的方式又java.lang.StackOverflowError，最后勉强卡掉）
总结
通过上面几个例题，可以总结出写深搜题的一些套路。
- 状态如何改变，通过递归去遍历（dfs（x,x,x））；
- 设置边界条件，搜到头了需要回溯，不可能无边界的递归下去（return）；
- 通过一些条件的判断进行剪枝，减少递归的层级和次数。(if（xxx）)
搜索的题目还是蛮有意思的，一个题目如果问有没有结果，能不能到达，或者有几种方式（基本超时），都能够用深搜的方式去解决，不一定能解决题目，但可能可以从答案中反推规律。
比较经典的还有 八皇后 Sticks等，有兴趣的可以自行尝试。
网友评论