深度优先搜索理论基础
两者大概的区别：
dfs是朝一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
dfs搜索过程
如图一，是一个无向图，我们要搜索从节点1到节点6的所有路径。
那么dfs搜索的第一条路径是这样的： （假设第一次延默认方向，就找到了节点6），图二
此时我们找到了节点6，（遇到黄河了，是不是应该回头了），那么应该再去搜索其他方向了。 如图三：
路径2撤销了，改变了方向，走路径3（红色线）， 接着也找到终点6。 那么撤销路径2，改为路径3，在dfs中其实就是回溯的过程（这一点很重要，很多录友不理解dfs代码中回溯是用来干什么的）
又找到了一条从节点1到节点6的路径，又到黄河了，此时再回头，下图图四中，路径4撤销（回溯的过程），改为路径5。
又找到了一条从节点1到节点6的路径，又到黄河了，此时再回头，下图图五，路径6撤销（回溯的过程），改为路径7，路径8 和 路径7，路径9， 结果发现死路一条，都走到了自己走过的节点。
那么节点2所连接路径和节点3所链接的路径 都走过了，撤销路径只能向上回退，去选择撤销当初节点4的选择，也就是撤销路径5，改为路径10 。 如图图六：
上图演示中，其实我并没有把 所有的 从节点1 到节点6的dfs（深度优先搜索）的过程都画出来，那样太冗余了，但 已经把dfs 关键的地方都涉及到了，关键就两点：
- 搜索方向，是认准一个方向搜，直到碰壁之后再换方向
- 换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。
代码框架
二叉树的递归法其实就是dfs，而二叉树的迭代法，就是bfs（广度优先搜索）
所以dfs，bfs其实是基础搜索算法，也广泛应用与其他数据结构与算法中。
回溯法代码框架:
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
回溯算法，其实就是dfs的过程
dfs算法框架:
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
}
深搜三部曲
1.确认递归函数，参数
一般情况，深搜需要 二维数组数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，我们可以定义一个全局变量，避免让我们的函数参数过多。
如:
ArrayList<ArrayList<int>> result; // 保存符合条件的所有路径
ArrayList<int> path; // 起点到终点的路径
void dfs (图，目前搜索的节点)
2.确认终止条件
if (终止条件) {
存放结果;
return;
}
终止添加不仅是结束本层递归，同时也是我们收获结果的时候。
3.处理目前搜索节点出发的路径
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
广度优先搜索理论基础
广搜的应用场景
广搜的搜索方式就适合于解决两个点之间的最短路径问题。
因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。
当然，也有一些问题是广搜 和 深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。
广搜的过程
我们用一个方格地图，假如每次搜索的方向为 上下左右（不包含斜上方），那么给出一个start起始位置，那么BFS就是从四个方向走出第一步。
如果加上一个end终止位置，那么使用BFS的搜索过程如图所示：
我们从图中可以看出，从start起点开始，是一圈一圈，向外搜索，方格编号1为第一步遍历的节点，方格编号2为第二步遍历的节点，第四步的时候我们找到终止点end。
正是因为BFS一圈一圈的遍历方式，所以一旦遇到终止点，那么一定是一条最短路径。
而且地图还可以有障碍，如图所示:
从图中可以看出，如果添加了障碍，我们是第六步才能走到end终点。
只要BFS只要搜到终点一定是一条最短路径
代码框架
需要一个容器，能保存我们要遍历过的元素就可以，那么用队列，还是用栈，甚至用数组，都是可以的。
用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。
因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。
如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。
因为栈是先进后出，加入元素和弹出元素的顺序改变了。
那么广搜需要注意 转圈搜索的顺序吗？ 不需要！
// 表示四个方向：右、下、左、上
private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// grid 是地图，visited 用来标记访问过的节点
public static void bfs(char[][] grid, boolean[][] visited, int x, int y) {
Queue<int[]> queue = new LinkedList<>(); // 定义队列
queue.offer(new int[]{x, y}); // 起始节点加入队列
visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
while (!queue.isEmpty()) { // 开始遍历队列里的元素
int[] cur = queue.poll(); // 从队列取出元素
int curx = cur[0];
int cury = cur[1]; // 当前节点坐标
// 开始想当前节点的四个方向（右、下、左、上）去遍历
for (int i = 0; i < 4; i++) {
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
// 坐标越界了，直接跳过
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) {
continue;
}
// 如果节点没被访问过
if (!visited[nextx][nexty]) {
queue.offer(new int[]{nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点
visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
}
}
}
}
说些什么吧！