深度优先搜索算法（英语：Depth-First-Search，缩写为DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

实现方法：

1. 首先将根节点放入stack中。

2. 从stack中取出第一个节点，并检验它是否为目标。

   如果找到目标，则结束搜寻并回传结果。

   否则将它某一个尚未检验过的直接子节点加入stack中。

3. 重复步骤2。

4. 如果不存在未检测过的直接子节点。

   将上一级节点加入stack中。

   重复步骤2。

5. 重复步骤4。

6. 若stack为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

代码可以用递归和栈来实现。

​​1. 递归DFS模板

(1) 基本递归DFS（无返回值）​

public void dfs(Node node, Set<Node> visited) {
    // 终止条件（节点为空或已访问）
    if (node == null || visited.contains(node)) {
        return;
    }
    
    // 标记当前节点为已访问
    visited.add(node);
    
    // 处理当前节点（前序遍历）
    processNode(node);
    
    // 递归访问所有邻居
    for (Node neighbor : getNeighbors(node)) {
        dfs(neighbor, visited);
    }
    
    // 如果需要后序遍历，可以在这里处理
    // postProcessNode(node);
}

​​(2) 带返回值的递归DFS（如求最大深度）​

public int dfs(Node node, Set<Node> visited) {
    if (node == null || visited.contains(node)) {
        return 0;
    }
    
    visited.add(node);
    
    int maxDepth = 0;
    for (Node neighbor : getNeighbors(node)) {
        maxDepth = Math.max(maxDepth, dfs(neighbor, visited));
    }
    
    return maxDepth + 1; // 当前层深度 + 子层最大深度
}

2. 迭代DFS（栈实现）

public void dfsIterative(Node start) {
    if (start == null) return;
    
    Stack<Node> stack = new Stack<>();
    Set<Node> visited = new HashSet<>();
    
    stack.push(start);
    visited.add(start);
    
    while (!stack.isEmpty()) {
        Node current = stack.pop();
        
        // 处理当前节点
        processNode(current);
        
        // 遍历邻居（注意顺序，栈是后进先出）
        for (Node neighbor : getNeighbors(current)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                stack.push(neighbor);
            }
        }
    }
}