Java中的DFS算法详解：深度优先搜索

深度优先搜索（DFS，Depth First Search）是一种常用的搜索与遍历算法，它是在一棵树或图中总是先走到最深处，再回退到上一个节点继续走。在Java中，DFS算法可以采用递归或栈的形式实现。

DFS的基本思想是：从某个节点出发，一次访问一个相邻节点，并递归地访问该节点的相邻节点，直到没有未被访问的节点为止。若还存在其他未被访问的节点，则选择另一个未被访问的节点作为起点，继续进行DFS搜索，直到所有节点都被访问。

递归实现DFS：

public void dfs(int v) {
    visited[v] = true; // 标记该节点
    System.out.print(v+" "); // 输出当前节点
    for (int i = 0; i < adj[v].size(); i++) { // 遍历当前节点的邻接节点
        int w = adj[v].get(i);
        if (!visited[w]) { // 若邻接节点未被访问，则递归访问该节点
            dfs(w);
        }
    }
}

在递归实现中，我们需要一个visited数组来记录每个节点是否已被访问过。在访问一个节点时将其标记为已访问，并通过遍历邻接表中与该节点相邻的节点递归访问未被访问的邻接节点。该算法的时间复杂度为O(n+m)，其中n为节点数，m为边数。

非递归实现DFS：

public void dfs(int s) {
    Stack<Integer> stack = new Stack<>();
    stack.push(s); // 将起点入栈
    visited[s] = true;
    while (!stack.empty()) {
        int v = stack.pop(); // 弹出栈顶节点
        System.out.print(v+" "); // 输出当前节点
        for (int i = 0; i < adj[v].size(); i++) { // 遍历当前节点的邻接节点
            int w = adj[v].get(i);
            if (!visited[w]) { // 若邻接节点未被访问，则将其入栈并标记为已访问
                visited[w] = true;
                stack.push(w);
            }
        }
    }
}

在非递归实现中，我们需要借助一个栈来实现节点的访问顺序。首先将起点入栈，并标记为已访问，然后不断弹出栈顶节点，并输出当前节点。对于每个栈顶节点，遍历其邻接表中未被访问的节点，依次将这些节点入栈，并标记为已访问。由于该算法在访问每个节点时都会加入栈，所以其空间复杂度为O(n)。在图较大或搜索深度较深时，可能会产生栈溢出的问题。

综上所述，Java中的DFS算法可以通过递归或栈的形式实现，可以对树或图进行深度优先搜索，并可以通过标记数组或颜色标记法进行节点的访问标记，算法时间复杂度为O(n+m)，空间复杂度为O(n)。