深入理解 Java 中的深度优先搜索（DFS）

简介

深度优先搜索（Depth-First Search，简称 DFS）是一种用于遍历或搜索图或树结构的算法。在 Java 编程中，DFS 有着广泛的应用，从简单的迷宫求解到复杂的人工智能问题。理解并掌握 DFS 在 Java 中的实现和应用，对于提升算法设计和编程能力至关重要。

DFS 基础概念

深度优先搜索的核心思想是尽可能深地探索一个分支，直到无法继续，然后回溯到前一步，继续探索其他分支。在图或树结构中，从一个起始节点开始，沿着一条路径一直向下访问节点，直到遇到叶子节点或者已经访问过的节点，然后返回上一层，继续探索其他未访问的路径。

与广度优先搜索（BFS）不同，BFS 是一层一层地扩展节点，而 DFS 更侧重于深入探索单个分支。

DFS 在 Java 中的使用方法

递归实现

递归是实现 DFS 最直观的方式。以树结构为例：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class DFSRecursive {
    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        // 访问节点
        System.out.println(node.val);
        // 递归访问左子树
        dfs(node.left);
        // 递归访问右子树
        dfs(node.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        DFSRecursive dfsRecursive = new DFSRecursive();
        dfsRecursive.dfs(root);
    }
}

迭代实现

使用栈（Stack）可以将 DFS 实现为迭代形式。同样以树结构为例：

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class DFSIterative {
    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);

        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            System.out.println(current.val);
            if (current.right!= null) {
                stack.push(current.right);
            }
            if (current.left!= null) {
                stack.push(current.left);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        DFSIterative dfsIterative = new DFSIterative();
        dfsIterative.dfs(root);
    }
}

常见实践

迷宫问题

假设迷宫是一个二维数组，0 表示通路，1 表示墙壁。我们可以使用 DFS 来寻找从起点到终点的路径。

public class Maze {
    public boolean dfs(int[][] maze, int startRow, int startCol, int endRow, int endCol) {
        if (startRow < 0 || startRow >= maze.length || startCol < 0 || startCol >= maze[0].length || maze[startRow][startCol] == 1) {
            return false;
        }
        if (startRow == endRow && startCol == endCol) {
            return true;
        }
        // 标记当前位置已访问
        maze[startRow][startCol] = 1;

        boolean result = dfs(maze, startRow + 1, startCol, endRow, endCol)
                || dfs(maze, startRow - 1, startCol, endRow, endCol)
                || dfs(maze, startRow, startCol + 1, endRow, endCol)
                || dfs(maze, startRow, startCol - 1, endRow, endCol);

        // 回溯时恢复原状态
        maze[startRow][startCol] = 0;
        return result;
    }

    public static void main(String[] args) {
        int[][] maze = {
                {0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0},
                {1, 1, 0, 1, 1},
                {0, 0, 0, 0, 0}
        };
        Maze mazeSolver = new Maze();
        boolean hasPath = mazeSolver.dfs(maze, 0, 0, 4, 4);
        System.out.println("是否存在路径: " + hasPath);
    }
}

图的连通性检测

给定一个图的邻接矩阵表示，检测图是否连通。

public class GraphConnectivity {
    public void dfs(int[][] graph, int start, boolean[] visited) {
        visited[start] = true;
        for (int i = 0; i < graph.length; i++) {
            if (graph[start][i] == 1 &&!visited[i]) {
                dfs(graph, i, visited);
            }
        }
    }

    public boolean isConnected(int[][] graph) {
        boolean[] visited = new boolean[graph.length];
        dfs(graph, 0, visited);
        for (boolean v : visited) {
            if (!v) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 1},
                {1, 0, 1},
                {1, 1, 0}
        };
        GraphConnectivity graphConnectivity = new GraphConnectivity();
        boolean isConnected = graphConnectivity.isConnected(graph);
        System.out.println("图是否连通: " + isConnected);
    }
}

最佳实践

优化递归深度

递归实现的 DFS 可能会因为递归深度过大导致栈溢出。可以通过设置递归深度限制或者使用迭代实现来避免这个问题。

避免无限循环

在处理图结构时，要确保节点被正确标记为已访问，以避免无限循环。例如，在图的 DFS 实现中，使用一个布尔数组来记录节点是否被访问过。

小结

深度优先搜索是一种强大的算法，在 Java 中有多种实现方式。通过递归和迭代实现，我们可以解决许多实际问题，如迷宫求解和图的连通性检测。在实践中，遵循最佳实践可以提高算法的效率和稳定性。掌握 DFS 不仅有助于解决算法问题，还能提升对复杂数据结构和算法的理解。

参考资料

《算法导论》
LeetCode 算法练习平台
GeeksforGeeks 相关教程