前言

本章将从洛谷中最基础的DFS例题开始进行讲解，第二个例题，从dfs优化至非递归dfs最后使用bfs再优化完成，如果能理解第二个例题，那就能理解染色模型和递归and非递归dfs的优化过程。本章的前置知识需要：递归，读入优化，栈

DFS —— 深度优先搜索

所谓深度优先，就是先选定一条路径一直走到头，直到碰到边界或障碍，此时进行回溯，回溯到上一步，然后从上一步的地方，检查是否有其他路径，如果没有，继续回溯。但是，DFS所找到的路径，不一定是最短路径。

• 递归型DFS的思路
  1.先检查是否越界 / 障碍 / 已访问 → 如果是，直接 return 0
  2.再标记为已访问
  3.再递归
  4.最后回溯（撤销标记）

BFS —— 广度优先搜索

BFS可以看作像是水波纹，一圈圈扩散，直到碰到障碍或者边界就停止，这种搜索的好处是，我们可以轻易的找到该图或者树中的最短路径。

例题（FROM 洛谷 P1605）

基础递归型深度优先搜索

代码实现

import java.util.*;
public class Main{
    static int n,m;
    static int fx,fy;//终点坐标
    public static void main(String []args){
        Scanner input = new Scanner (System.in);
        n = input.nextInt();
        m = input.nextInt();
        int t = input.nextInt();
        boolean [][] board = new boolean[n][m];
        for(int i=0;i<n;i++)
           Arrays.fill(board[i],true);//先将棋盘所有位置标记为“可走”
           
        //数组下标是0开始，棋盘坐标是1开始，所以将棋盘坐标转化为数组下标
        int sx = input.nextInt()-1;
        int sy = input.nextInt()-1;
        fx = input.nextInt()-1;
        fy = input.nextInt()-1;
        
        for(int i=0;i<t;i++){//读入障碍
            int nox = input.nextInt()-1;
            int noy = input.nextInt()-1;
            board[nox][noy] = false;
        }
        boolean [][] visited = new boolean [n][m];//默认初始为false
        int ans = dfs(sx,sy,board,visited);
        System.out.print(ans);
    }
    
    //核心函数
    static int dfs(int x,int y,boolean[][]board,boolean[][] visited){
        if(x<0||x>=n||y<0||y>=m)//检查边界
            return 0;
        if(!board[x][y] || visited[x][y])//检查障碍and有没有被访问过
            return 0;
         if(x==fx && y==fy)//如果到达终点，证明有一条路径，返回1
            return 1;
        visited[x][y] = true;
        int right  = dfs(x+1,y,board,visited);//right 
        int left = dfs(x-1,y,board,visited);//left
        int up = dfs(x,y+1,board,visited);//up
        int down = dfs(x,y-1,board,visited);//down
        visited[x][y] = false;//回溯
        return right + left + up + down;
    }
}

例题（FROM 洛谷P1141）

本题给出三种解法：递归dfs，非递归dfs，bfs，其中递归dfs会爆栈，其他两个均可AC

思路

1.一个格子和他可达的所有格子，我们可以将其看作一个整体，其中有多少个小格子，就是从整体的某一格开始，能移动多少格子（题意要求的）
2.所以我们用color数组进行染色，如果判断出，当下检查的格子，和某格子是一个整体（可达），我们就将其染上同一个颜色。

代码实现 - 基础版（递归DFS）

这里为保证不会受Scanner 读入的缓存影响，统一使用next函数优化读入，该解法结果是 9/12 的AC，和 3/12 的RE，如果你执意使用Scanner，将会多一个MLE。会爆栈，着重理解递归dfs原理

import java.util.*;
import java.io.BufferedReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n;
    static int [][] color;//染色数组
    static char [][] board;//棋盘
    static List<Integer>sizes = new ArrayList<>();//储存“整体”的大小
    static int [] dx = {0,-1,0,1};//上左下右，方向数组，优化代码可读性
    static int [] dy = {1,0,-1,0};
    
    public static void main(String[]args)throws IOException{
        n = Integer.parseInt(next());
        int m = Integer.parseInt(next());
        board = new char [n][n];
        color = new int [n][n];
        for(int i=0;i<n;i++){//读入棋盘并将其转换为字符数组
            String str = bf.readLine();
            for(int j=0;j<n;j++){
                board [i][j] = str.charAt(j);
                color [i][j] = -1;//初始化颜色数组，-1代表未染色
            }
        }
        int ID = 0;//ID就是这时候的“颜色”
        
        for(int i=0;i<n;i++){//遍历每一个格子，并使用dfs染色
            for(int j=0;j<n;j++){
                if(color[i][j] == -1){//如果该格子未染色，进去染色
                    int size = dfs(i,j,ID);
                    sizes.add(size);//储存该整体的大小
                    ID++;//换个颜色
                }
            }
        }
        for(int i=0;i<m;i++){//遍历m个起点，并输出该起点对应的结果
            int x = Integer.parseInt(next())-1;
            int y = Integer.parseInt(next())-1;
            System.out.println(sizes.get(color[x][y]));
        }
    }
 	//核心函数
    static int dfs (int x ,int y ,int id){
        color[x][y] = id;//先染色起点
        int count  = 1;//数该整体格子的个数
        for(int d =0;d<4;d++){//用方向数组递归检查该点的邻居
            int nx = x+dx[d];
            int ny = y+dy[d];
            if(nx>=0 && nx<n && ny>=0 && ny<n //检查边界
            && color[nx][ny]==-1 //检查是否染色，如果已经染色则跳过
            && board[nx][ny] != board[x][y])//检查是否可达：该点和邻居点是不是10关系
            count += dfs(nx,ny,id);//累和递归得到的染色整体大小
        }
        return count;//返回该整体的大小
    }
}

    static String next() throws IOException{
        while(st == null || !st.hasMoreTokens()){
            String str = bf.readLine();
            if(str == null) return null;
            st = new StringTokenizer(str);
        }
        return st.nextToken();
    }

代码实现 - 进阶版（非递归dfs）

由于递归版的dfs使用时，计算机内部会储存大量待回溯的内存，导致爆栈。于是非递归dfs使用显式栈，手动完成该过程，所以称之为非递归dfs。

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char[][] board;
    static int n;
    static int[][] color;
    static List<Integer> sizes = new ArrayList<>();
    static int[] dx = {0, -1, 0, 1}; // right, up, left, down
    static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(next());
        int m = Integer.parseInt(next());
        board = new char[n][n];
        color = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            String str = bf.readLine(); 
            for (int j = 0; j < n; j++) {
                board[i][j] = str.charAt(j);
                color[i][j] = -1;
            }
        }

        int ID = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (color[i][j] == -1) {
                    int size = NO_dfs(i, j, ID);
                    sizes.add(size);
                    ID++;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            int x = Integer.parseInt(next()) - 1;
            int y = Integer.parseInt(next()) - 1;
            System.out.println(sizes.get(color[x][y]));
        }
    }
//核心函数
    static int NO_dfs(int x, int y, int ID) {
        Stack<int[]> stack = new Stack<>();//显式栈
        color[x][y] = ID;//染色
        stack.push(new int[]{x, y});//入栈
        int count = 0;

        while (!stack.isEmpty()) {//如果栈非空，继续处理
            int[] now = stack.pop();//弹出栈顶，处理
            int nowx = now[0];
            int nowy = now[1];
            count++;

            for (int d = 0; d < 4; d++) {//用方向数组遍历该点的邻居
                int nx = nowx + dx[d];
                int ny = nowy + dy[d];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n
                    && color[nx][ny] == -1
                    && board[nx][ny] != board[nowx][nowy]) {
                    color[nx][ny] = ID;//染色
                    stack.push(new int[]{nx, ny});//邻居入栈
                }
            }
        }
        return count;
    }
    
    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
}

注意：
1.要先染色后入栈，起点可以随便。非起点的点将染色和入栈搞反会导致该点多次被访问
2.count计数，一定要在处理该点的时候进行，不可以在压栈的时候进行，该点被处理的时候，才是这个点进入整体的时候。如果压栈则计数，会导致该点就算不在该整体内，但是仍然被计数。

代码实现 - 进阶版（BFS）

这其中被注释掉的代码是之前非递归dfs的代码，bfs在其基础上略微改动。其次，该版本将储存size的动态数组改为了数字数组，不改动也可以AC，但是这也是一种优化方式。
该方式储存了第i个入队点的坐标，然后用两个指针，模拟栈的弹出，但是他的搜索方式是bfs，这是他和之前方式的区别。

import java.util.*;
import java.io.*;

public class Main{
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char [][] board;
    static int n;
    static int [][] color;
    //static List<Integer>sizes = new ArrayList<>();
    //太多的Integer可能会导致MLE，改为int[]
    static int [] sizes;
    static int [] dx = {0,-1,0,1};
    static int [] dy = {1,0,-1,0};
    static int [] qx;//增加的数组，储存第i个入队点的坐标
    static int [] qy;
    
    public static void main(String [] args)throws IOException{
        n = Integer.parseInt(next());
        int m = Integer.parseInt(next());
        board = new char[n][n];
        color = new int [n][n];
        qx = new int [n*n];//初始化
        qy = new int [n*n];
        sizes = new int[n*n];
        for(int i=0;i<n;i++){
            String str = bf.readLine();
            for(int j=0;j<n;j++){
                board[i][j] = str.charAt(j);
                color[i][j] = -1;//未染色
            }
        }
        int ID = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(color[i][j]==-1){//no color
                    //int size = NO_dfs(i,j,ID);//原来的代码
                    int size = bfs(i,j,ID);
                    sizes[ID] = size;
                    ID++;
                }
            }
        }
        for(int i=0;i<m;i++){
            int x = Integer.parseInt(next())-1;
            int y = Integer.parseInt(next())-1;
            System.out.println(sizes[color[x][y]]);
        }
    }
    static String next() throws IOException{
        while(st == null || !st.hasMoreTokens()){
            String str = bf.readLine();
            if(str == null) return null;
            st = new StringTokenizer(str);
        }
        return st.nextToken();
    }
    static int bfs(int x,int y,int ID){
        //Stack<int[]>stack = new Stack<>();
        int front = 0;//下一个要处理的元素下标
        int rear = 0;//下一个要插入的元素位置
        color[x][y] = ID;
        //stack.push(new int []{x,y});
        qx[rear] = x;
        qy[rear] = y;
        rear++;
        int count = 0;
        while(front<rear){
            int nowx = qx[front];
            int nowy = qy[front];
            front ++;
            count++;
            for(int d=0;d<4;d++){
                int nx = nowx+dx[d];
                int ny = nowy+dy[d];
                if(nx >= 0 && nx < n && ny >= 0 && ny < n 
                   && color[nx][ny] == -1 
                   && board[nx][ny] != board[nowx][nowy]){
                    color[nx][ny] = ID;
                    qx[rear] = nx;
                    qy[rear] = ny;
                    rear++;
                    //stack.push(new int []{nx,ny});
                }
            }
        }
        return count;
    }
}

总结

这两个例题是DFS里很经典很基础的问题，尤其是第二个问题中的染色思想，大家可以学习过后多敲几遍代码，将他的代码结构牢牢地记在脑子中，这样之后遇到类似的DFS题的时候，可以类比该题进行解题。