深度优先搜索（DFS）详解

深度优先搜索（DFS, Depth-First Search）是一种常见的图或树的搜索算法，它尝试从起点开始，一直沿着一个方向搜索到尽可能深的位置，然后回溯，尝试其他路径，直到找到目标或访问所有可能的节点。

在 Java 中，DFS 通常以递归或显式栈的方式实现。

---

DFS 的基本特性

1. 搜索方式：

   • 沿着一个分支一直深入，直到无法继续，再回溯到上一级，探索其他分支。
   • 访问顺序是“先深后广”。

2. 实现方式：

   • 递归实现：利用系统栈存储递归状态。
   • 显式栈实现：通过手动管理栈，模拟递归过程。

3. 适用场景：

   • 图或树的遍历（如查找路径、连通性问题）。
   • 搜索问题（如迷宫、数独）。
   • 解决组合问题（如全排列、子集生成）。

4. 时间复杂度：

   • 一般为 $O(V+E)$，其中 $V$ 是节点数，$E$ 是边数。

5. 空间复杂度：

   • 递归实现：受递归深度限制，为 $O(H)$，其中 $H$ 是递归深度。
   • 显式栈实现：栈的最大深度为 $O(H)$。

---

DFS 的核心步骤

1. 访问当前节点。
2. 标记节点为已访问（如果是图）。
3. 递归或循环访问邻接节点。

---

DFS 的实现（递归）

示例1：遍历一棵二叉树

java">class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}
}public class DFSExample {public void dfs(TreeNode root) {if (root == null) {return;}System.out.println(root.val); // 访问当前节点dfs(root.left); // 遍历左子树dfs(root.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);new DFSExample().dfs(root); // 输出：1, 2, 4, 5, 3}
}

---

示例2：遍历一个无向图

java">import java.util.*;public class GraphDFS {private Map<Integer, List<Integer>> graph = new HashMap<>();private Set<Integer> visited = new HashSet<>();// 添加边public void addEdge(int u, int v) {graph.putIfAbsent(u, new ArrayList<>());graph.putIfAbsent(v, new ArrayList<>());graph.get(u).add(v);graph.get(v).add(u); // 无向图，双向边}// DFS 方法public void dfs(int node) {if (visited.contains(node)) {return;}visited.add(node);System.out.println(node); // 访问节点for (int neighbor : graph.get(node)) {dfs(neighbor);}}public static void main(String[] args) {GraphDFS g = new GraphDFS();g.addEdge(1, 2);g.addEdge(1, 3);g.addEdge(2, 4);g.addEdge(2, 5);g.addEdge(3, 6);g.dfs(1); // 输出：1, 2, 4, 5, 3, 6（可能顺序不同）}
}

---

DFS 的实现（显式栈）

示例3：栈实现图的 DFS

java">import java.util.*;public class StackDFS {private Map<Integer, List<Integer>> graph = new HashMap<>();// 添加边public void addEdge(int u, int v) {graph.putIfAbsent(u, new ArrayList<>());graph.putIfAbsent(v, new ArrayList<>());graph.get(u).add(v);graph.get(v).add(u); // 无向图，双向边}// 栈实现 DFSpublic void dfs(int start) {Stack<Integer> stack = new Stack<>();Set<Integer> visited = new HashSet<>();stack.push(start);while (!stack.isEmpty()) {int node = stack.pop();if (!visited.contains(node)) {visited.add(node);System.out.println(node); // 访问节点// 将邻居节点压入栈for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {if (!visited.contains(neighbor)) {stack.push(neighbor);}}}}}public static void main(String[] args) {StackDFS g = new StackDFS();g.addEdge(1, 2);g.addEdge(1, 3);g.addEdge(2, 4);g.addEdge(2, 5);g.addEdge(3, 6);g.dfs(1); // 输出：1, 3, 6, 2, 5, 4（可能顺序不同）}
}

---

DFS 的应用场景

1. 全排列与组合

java">import java.util.*;public class Permutations {public void dfs(List<Integer> nums, List<Integer> path, boolean[] visited) {if (path.size() == nums.size()) {System.out.println(path); // 输出当前排列return;}for (int i = 0; i < nums.size(); i++) {if (visited[i]) {continue;}visited[i] = true;path.add(nums.get(i));dfs(nums, path, visited);path.remove(path.size() - 1); // 回溯visited[i] = false;}}public static void main(String[] args) {List<Integer> nums = Arrays.asList(1, 2, 3);new Permutations().dfs(nums, new ArrayList<>(), new boolean[nums.size()]);// 输出：[1, 2, 3], [1, 3, 2], [2, 1, 3], ...}
}

---

2. 寻找岛屿数量（二维矩阵中的连通分量）

java">public class NumberOfIslands {private void dfs(char[][] grid, int i, int j) {if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {return;}grid[i][j] = '0'; // 标记已访问dfs(grid, i - 1, j); // 上dfs(grid, i + 1, j); // 下dfs(grid, i, j - 1); // 左dfs(grid, i, j + 1); // 右}public int numIslands(char[][] grid) {int count = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == '1') {count++;dfs(grid, i, j);}}}return count;}public static void main(String[] args) {char[][] grid = {{'1', '1', '0', '0'},{'1', '0', '0', '1'},{'0', '0', '1', '1'}};System.out.println(new NumberOfIslands().numIslands(grid)); // 输出：3}
}

---

DFS 的优缺点

优点

1. 内存占用低（如果递归深度不高）。
2. 适合用于搜索特定路径和解决分支问题。
3. 实现简单，代码结构清晰。

缺点

1. 对递归深度敏感，容易导致栈溢出。
2. 无法保证最短路径的优先级（对于路径问题，应使用 BFS）。

---

总结

DFS 是一种强大的算法，适用于多种场景，包括树和图的遍历、路径查找、连通分量等问题。通过递归和显式栈两种方式实现，DFS 既直观又灵活，但需要注意递归深度和路径记录问题。在复杂应用中，可结合回溯、记忆化等技术提升效率。