深度优先搜索，用于遍历或搜索树和图结构的算法。 从起始位置开始，沿着每条可能得路径尽可能深入探索分支，直到不能前进。然后回溯并继续探索其他路径。

应用场景

• 排列组合
• 网络爬虫
• 迷宫求解
• 路径查找
• 连通性检测
• 拓扑排序
• 图遍历
• 文件系统遍历
• 图像处理

示例代码

DFS 递归

public class MazeSolver {
    private static final int[] ROW_MOVES = { -1, 1, 0, 0 };
    private static final int[] COL_MOVES = { 0, 0, -1, 1 };
    private static final char PATH = 'P';
    private static final char VISITED = 'V';
    private static final char WALL = 'W';
    private static final char EXIT = 'E';

    public static boolean solveMaze(char[][] maze, int row, int col) {
        if (!isValidMove(maze, row, col)) return false;

        if (maze[row][col] == EXIT) return true;

        maze[row][col] = VISITED;

        for (int i = 0; i < 4; i++) {
            int newRow = row + ROW_MOVES[i];
            int newCol = col + COL_MOVES[i];
            if (solveMaze(maze, newRow, newCol)) {
                maze[row][col] = PATH;
                return true;
            }
        }

        return false;
    }

    private static boolean isValidMove(char[][] maze, int row, int col) {
        return row >= 0 && row < maze.length && col >= 0 && col < maze[0].length && maze[row][col] != WALL && maze[row][col] != VISITED;
    }

    public static void main(String[] args) {
        char[][] maze = {
            { 'S', ' ', 'W', ' ', ' ' },
            { ' ', 'W', ' ', 'W', ' ' },
            { ' ', ' ', ' ', ' ', ' ' },
            { 'W', 'W', 'W', ' ', 'W' },
            { ' ', ' ', ' ', ' ', 'E' }
        };

        if (solveMaze(maze, 0, 0)) {
            System.out.println("Path found!");
            for (char[] row : maze) {
                System.out.println(Arrays.toString(row));
            }
        } else {
            System.out.println("No path found.");
        }
    }
}