上一篇
在Java中实现深度优先搜索(DFS)通常采用递归或显式栈结构，递归方法代码简洁但可能栈溢出；显式栈通过Stack/LinkedList类维护节点，手动压栈出栈处理遍历逻辑，适用于深度大的场景。
深度优先搜索（DFS）在Java中的实现与解决方案
深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树、图结构的经典算法，其核心思想是尽可能深地探索分支，直到尽头再回溯，在Java中，DFS常用于解决路径查找、连通性检测、拓扑排序等问题，以下是详细实现方法和常见问题的解决方案。
DFS的核心实现方式
Java中实现DFS主要有两种方式：递归法和迭代法（栈实现）。
递归实现（简洁直观）
// 以二叉树为例
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public void dfsRecursive(TreeNode node) {
if (node == null) return;
// 处理当前节点（前序遍历）
System.out.print(node.val + " ");
// 递归探索左子树
dfsRecursive(node.left);
// 递归探索右子树（中序/后序调整位置即可）
dfsRecursive(node.right);
}
特点：
- 代码简洁,符合DFS的自然逻辑。
- 隐式使用系统调用栈,无需显式数据结构。
- 注意栈溢出风险（深度过大时需优化）。
迭代实现（手动维护栈）
public void dfsIterative(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " "); // 处理当前节点
// 右子树先入栈（保证左子树先处理）
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
}
特点：
- 避免递归的栈溢出问题。
- 显式控制栈,适合深度极大的场景。
- 可通过调整入栈顺序实现前序/中序/后序遍历。
图的DFS实现（处理环路）
图结构中需记录访问状态,避免环路导致的无限递归：
// 邻接表表示图：Map<Integer, List<Integer>> graph
public void dfsGraph(int start, Map<Integer, List<Integer>> graph) {
Set<Integer> visited = new HashSet<>();
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited.contains(node)) continue;
visited.add(node);
System.out.print(node + " "); // 处理节点
// 邻接节点入栈（未访问过）
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
常见问题与解决方案
| 问题类型 | 原因 | 解决方案 |
|---|---|---|
| 栈溢出（StackOverflowError） | 递归深度过大 | 改用迭代法；增加JVM栈空间（-Xss参数）；尾递归优化（Java有限支持） |
| 环路导致死循环 | 未记录访问状态 | 使用HashSet或boolean[]标记已访问节点 |
| 性能瓶颈 | 重复访问 | 剪枝优化（如记忆化搜索）；限制最大深度 |
| 非连通图遍历不全 | 未处理多个连通分量 | 外层循环遍历所有节点，对未访问节点启动DFS |
DFS优化技巧
-
剪枝（Pruning）
在回溯算法中提前终止无效分支（如路径和超过目标值时停止递归）。 -
记忆化搜索（Memoization）
存储已计算子问题的结果，避免重复计算（常用于动态规划结合DFS）。
Map<TreeNode, Integer> memo = new HashMap<>(); public int dfsWithMemo(TreeNode node) { if (node == null) return 0; if (memo.containsKey(node)) return memo.get(node); // 查缓存 int left = dfsWithMemo(node.left); int right = dfsWithMemo(node.right); int result = Math.max(left, right) + 1; memo.put(node, result); // 存储结果 return result; } -
迭代深化搜索（IDS）
结合BFS层级控制，逐层增加深度限制，平衡DFS与BFS优势。
DFS与BFS的选择场景
| 场景 | 推荐算法 | 原因 |
|---|---|---|
| 查找所有解（如全排列） | DFS | 回溯天然适合深度遍历 |
| 最短路径（无权图） | BFS | DFS可能绕远路，BFS按层推进保证最短 |
| 树/图的连通性检测 | DFS | 代码简洁，快速探索连通分量 |
| 拓扑排序 | DFS | 后序遍历逆序即拓扑序 |
在Java中实现DFS时：
- 优先选择递归法：代码简洁，适合逻辑清晰的场景（如树遍历）。
- 图结构务必记录访问状态：防止环路导致的无限循环。
- 警惕栈溢出：深度超过1000+时改用迭代法。
- 结合优化技巧：剪枝和记忆化可显著提升性能。
通过合理选择实现方式和优化策略,DFS能高效解决复杂的搜索问题，尤其在路径探索、状态空间遍历等场景中不可替代。
引用说明参考自《算法导论》（Thomas H. Cormen）、Oracle官方Java文档以及LeetCode经典题库的解题实践，代码示例遵循MIT开源协议，可自由使用。
