?1.?深度优先搜索算法：
????????深度优先搜索属于图算法的一种，英文缩写为DFS（Depth First Search.）其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
DFS适合题目：给定初始状态跟目标状态，要求判断从初始状态到目标状态是否有解。
????????解决必须走到?最深处（例如对于树，须走到它的叶子节点）?才能得到一个解的问题
????????通常利用递归实现，所以 每次递归开始的时候要判断是否达到收敛条件，若达到了则得到一个可行解，若没达到，则对当前状态进行扩展（扩展的时候通常会根据实际情况过滤掉一些非法的状态，这个过程叫 剪枝，适当的剪枝有时能极大地提高搜索的速度），如果要求输出具体解，则此时应该保存该状态，当扩展结束后，需要释放这个保存的状态。
深度优先搜索（DFS)有两个重要的点：第一是当前怎么做，第二是下一步怎么做；模板如下：
public static void dfs (int step) {
? ? ? ? //判断边界，递归出口????????if (可以剪枝) return;
? ? ? ? //遍历每一种可能，经进行递归
? ? ? ? for (int i = 1; i < n; i++) {? ? ? ? ? ? ? ? 执行动作，修改中间结果
? ? ? ? ? ? dfs(step + 1);? ? ? ? ? ? ? ? 恢复中间结果
? ? ? ? }
? ? }
如何剪枝？
剪枝，顾名思义，就是通过一些判断，砍掉搜索树上不必要的子树。我们来看看几种不同的剪枝
可行性剪枝
有时候，我们会发现某个节点对应的子树的状态都不是我们想要的结果，那么我们其实没必要对每个分支都进行搜索，砍掉这个子树。
最优性剪枝
对于求最优解的一类问题，通常可以用最优性剪枝，比如在求迷宫最短路的时候，如果发现当前的步数已经超过了当前最优解，那么从当前状态开始的搜索都是多余的，因为这样搜索下去也找不到最优解了。通过剪枝，可以省去大量冗余的计算。
此外，对于可行性的问题，如前面例题中木棍拼三角形。一旦我们找到了一组可行解，就不再继续进行，这也算最优性剪枝。
重复性剪枝
对于某些特定的搜索方式，一些方案可能会被搜索很多次，这样是没必要的。
2，广度优先搜索算法
常用模板：
- 定义Queue
- 加入初始条件
- 队列不为空的while循环
3.0 业务处理
3.1 for循环将队列元素逐一取出进行处理
3.2 将下一条件放入队列中
3.3 将符合条件的一种结果放入结果集中 - 返回结果集
eg:二叉树的层序遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null){
return res;
}
// 1. 定义队列
Queue<TreeNode> queue = new LinkedList<>();
// 2.加入初始条件
queue.offer(root);
// 3. 队列不为空的while循环
while(!queue.isEmpty()){
List<Integer> oneRes = new ArrayList<>();
int n = queue.size();
// 3.1 for循环将队列元素逐一取出进行处理
for(int i = 0;i < n;++i){
TreeNode temp = queue.poll();
// 3.0 业务处理
oneRes.add(temp.val);
// 3.2 将下一条件放入队列中
if(temp.left!=null){
queue.offer(temp.left);
}
if(temp.right!=null){
queue.offer(temp.right);
}
}
// 3.3 将符合条件的一种结果放入结果集中
res.add(oneRes);
}
// 4. 返回结果集
return res;
}
}
3.在二维矩阵中搜索，什么时候用BFS，什么时候用DFS？
1.如果只是要找到某一个结果是否存在，那么DFS会更高效。因为DFS会首先把一种可能的情况尝试到底，才会回溯去尝试下一种情况，只要找到一种情况，就可以返回了。但是BFS必须所有可能的情况同时尝试，在找到一种满足条件的结果的同时，也尝试了很多不必要的路径；
2.如果是要找所有可能结果中最短的，那么BFS回更高效。因为DFS是一种一种的尝试，在把所有可能情况尝试完之前，无法确定哪个是最短，所以DFS必须把所有情况都找一遍，才能确定最终答案（DFS的优化就是剪枝，不剪枝很容易超时）。而BFS从一开始就是尝试所有情况，所以只要找到第一个达到的那个点，那就是最短的路径，可以直接返回了，其他情况都可以省略了，所以这种情况下，BFS更高效。
BFS解法中的visited为什么可以全局使用？
BFS是在尝试所有的可能路径，哪个最快到达终点，哪个就是最短。那么每一条路径走过的路不同，visited（也就是这条路径上走过的点）也应该不同，那么为什么visited可以全局使用呢？
因为我们要找的是最短路径，那么如果在此之前某个点已经在visited中，也就是说有其他路径在小于或等于当前步数的情况下，到达过这个点，证明到达这个点的最短路径已经被找到。那么显然这个点没必要再尝试了，因为即便去尝试了，最终的结果也不会是最短路径了，所以直接放弃这个点即可。
BFS最短路径问题：
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
int[][] dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,1},{1,-1}};
int m = grid.length;
int n = m;
boolean[][] vis = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
int dis = 1;
if (grid[0][0] != 0){
return -1;
}
if (m == 1){
return 1;
}
queue.offer(new int[]{0,0});
while (!queue.isEmpty()){
int size = queue.size();
for (int c = 0; c < size; ++c) {
int[] poll = queue.poll();
int i = poll[0];
int j = poll[1];
for (int k = 0; k < 8; ++k) {
int ni = i + dir[k][0];
int nj = j + dir[k][1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 0 && !vis[ni][nj]) {
if (ni == m - 1 && nj == n - 1) {
return dis + 1;
}
queue.offer(new int[]{ni, nj});
vis[ni][nj] = true;
}
}
}
//这一圈都加1
dis += 1;
}
return -1;
}
} public static int shortestPathBinaryMatrix(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return -1;
}
// 如果起点就阻塞那就玩完啦
if (grid[0][0]==1){
return -1;
}
//定义 8个方向
int[][] dir = {{1, -1}, {1, 0}, {1, 1}, {0,-1},{0,1},{-1,-1},{-1,0},{-1,1}};
int m = grid.length;
int n = grid[0].length;
//bfs的老套路 来个队列
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0,0}); //把起点扔进去
grid[0][0] = 1; // 把起点标记为阻塞
int path = 1; // 层数
while (!queue.isEmpty()){
int size = queue.size();
while(size-- > 0){
int[] cur = queue.poll();
int x = cur[0];
int y = cur[1];
//能放进队列里的都是为0可以走的（这一点在后面保证了）
// 如果等于终点则返回
if (x == m-1 && y == n-1){ //
return path;
}
//开始八个方向的判断
for (int[] d : dir){
int x1 = x + d[0];
int y1 = y + d[1];
//这里开始过滤
if (x1 < 0 || x1 >= m || y1 < 0||y1>=m || grid[x1][y1]==1){
continue;
}
//把在数组范围内 并且为0不阻塞的放入队列中
queue.add(new int[]{x1,y1});
grid[x1][y1] = 1; // 标记
}
}
path++; //遍历完一层 这时候要 ++啦
}
return -1;
}?
dfs解法：
class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 从边缘o开始搜索
boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
if (isEdge && board[i][j] == 'O') {
dfs(board, i, j);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
}
public void dfs(char[][] board, int i, int j) {
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
// board[i][j] == '#' 说明已经搜索过了.
return;
}
board[i][j] = '#';
dfs(board, i - 1, j); // 上
dfs(board, i + 1, j); // 下
dfs(board, i, j - 1); // 左
dfs(board, i, j + 1); // 右
}
}?
bfs解法：?
class Solution {
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private static class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) return;
int row = board.length;
int col = board[0].length;
for (int j = 0; j < col; j++) {
// 第一行
if (board[0][j] == 'O') bfs(0, j, board, row, col);
// 最后一行
if (board[row - 1][j] == 'O') bfs(row - 1, j, board, row, col);
}
for (int i = 0; i < row; i++) {
// 第一列
if (board[i][0] == 'O') bfs(i, 0, board, row, col);
// 最后一列
if (board[i][col - 1] == 'O') bfs(i, col - 1, board, row, col);
}
// 转变
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == 'B') board[i][j] = 'O';
}
}
}
private void bfs(int i, int j, char[][] board, int row, int col) {
Deque<Point> queue = new LinkedList<>();
queue.offer(new Point(i, j));
while (!queue.isEmpty()) {
Point tmp = queue.poll();
if (tmp.x >= 0 && tmp.x < row && tmp.y >= 0 && tmp.y < col && board[tmp.x][tmp.y] == 'O') {
board[tmp.x][tmp.y] = 'B';
for (int[] dir : dirs) queue.offer(new Point(tmp.x + dir[0], tmp.y + dir[1]));
}
}
}
}