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

DFS 的应用场景

• 图的连通性检测
• 拓扑排序
• 寻找路径或所有路径
• 解决迷宫问题
• 检测环（Cycle Detection）

用 Java 实现 DFS（递归方式）

下面我们用邻接表表示图，并使用递归实现 DFS算法教程中最经典的遍历逻辑。

import java.util.*;public class DFSExample {    // 使用邻接表存储图    private List<List<Integer>> graph;    private boolean[] visited;    public DFSExample(int vertices) {        graph = new ArrayList<>();        for (int i = 0; i < vertices; i++) {            graph.add(new ArrayList<>());        }        visited = new boolean[vertices];    }    public void addEdge(int u, int v) {        graph.get(u).add(v);        graph.get(v).add(u); // 无向图    }    public void dfs(int start) {        Arrays.fill(visited, false);        dfsRecursive(start);    }    private void dfsRecursive(int node) {        visited[node] = true;        System.out.print(node + " ");        for (int neighbor : graph.get(node)) {            if (!visited[neighbor]) {                dfsRecursive(neighbor);            }        }    }    public static void main(String[] args) {        DFSExample g = new DFSExample(5);        g.addEdge(0, 1);        g.addEdge(0, 2);        g.addEdge(1, 3);        g.addEdge(1, 4);        System.out.println("DFS遍历结果（从节点0开始）：");        g.dfs(0); // 输出：0 1 3 4 2    }}

代码解析

上面的代码展示了如何用 Java 实现一个简单的 DFS 遍历：

1. graph 是一个邻接表，用 List<List<Integer>> 表示。
2. visited 数组用于记录哪些节点已被访问，避免重复访问。
3. dfsRecursive 方法是核心：先标记当前节点为已访问，打印它，然后递归访问所有未访问的邻居。

非递归实现（使用栈）

除了递归，我们也可以用显式栈来实现 DFS，这在处理深层递归时可以避免栈溢出：

public void dfsIterative(int start) {    Arrays.fill(visited, false);    Stack<Integer> stack = new Stack<>();    stack.push(start);    while (!stack.isEmpty()) {        int node = stack.pop();        if (!visited[node]) {            visited[node] = true;            System.out.print(node + " ");            // 注意：为了保持与递归相同的输出顺序，需逆序压栈            for (int i = graph.get(node).size() - 1; i >= 0; i--) {                int neighbor = graph.get(node).get(i);                if (!visited[neighbor]) {                    stack.push(neighbor);                }            }        }    }}

时间与空间复杂度

- 时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。
- 空间复杂度：O(V)，用于存储 visited 数组和递归调用栈（或显式栈）。

总结

通过本教程，你已经掌握了 图的遍历Java 中最基础也最重要的 DFS 算法。无论是用递归还是栈，核心思想都是“深入探索 + 回溯”。建议你动手编写代码，修改图结构，观察输出变化，从而真正理解 递归实现DFS 的过程。

现在，你已经具备了使用 Java 解决 DFS 相关问题的能力！继续练习，你将在算法竞赛或面试中游刃有余。