算法刷题系列（二十九）：DFS——沿路径深入并维护访问状态

算法刷题系列（二十九）：DFS——沿路径深入并维护访问状态

深度优先搜索（DFS）沿一条分支尽可能深入，再回退尝试其他分支。树的结构没有环，递归访问左右孩子即可；一般图可能有环或多条路径到达同一节点，必须区分“当前路径上的节点”和“已经全局处理过的节点”。

一、树路径与图访问的差别

在树里求是否存在根到叶的目标和，路径状态可通过递归参数传递。离开递归调用时，局部变量随栈帧返回，不需要全局 visited。

在图 0—1—2—0 中，若沿邻接边递归却不标记访问状态，搜索会无限绕圈。若目标是判断可达性或遍历连通分量，全局访问集合通常应在进入节点时标记。若任务是枚举所有简单路径，则节点可在回溯时撤销“当前路径访问”标记，以允许它出现在另一条候选路径中；这与全局去重不是同一个语义。

二、树：根到叶路径和

public class Main {
    static final class Node {
        final int value;
        Node left;
        Node right;
        Node(int value) { this.value = value; }
    }

    static boolean hasPathSum(Node node, long remaining) {
        if (node == null) return false;
        long afterNode = remaining - node.value;
        if (node.left == null && node.right == null) {
            return afterNode == 0;
        }
        return hasPathSum(node.left, afterNode)
                || hasPathSum(node.right, afterNode);
    }

    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(4);
        root.right = new Node(8);
        root.left.left = new Node(11);
        root.left.left.left = new Node(7);
        root.left.left.right = new Node(2);
        root.right.right = new Node(4);
        assert hasPathSum(root, 22);
        assert !hasPathSum(root, 18);
        assert !hasPathSum(null, 0);
    }
}

remaining 表示从当前节点开始还需要凑出的和；只有到达叶子且恰好归零才成功。节点值可以为负数，因此不能仅因当前和超过目标就剪枝。

三、图：可达节点 DFS

def reachable_count(graph: list[list[int]], start: int) -> int:
    if not 0 <= start < len(graph):
        raise ValueError("start vertex is out of range")
    visited = {start}
    stack = [start]
    while stack:
        vertex = stack.pop()
        for neighbor in graph[vertex]:
            if not 0 <= neighbor < len(graph):
                raise ValueError("neighbor vertex is out of range")
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    return len(visited)

graph = [[1, 2], [0, 2], [0, 1, 3], [2], []]
assert reachable_count(graph, 0) == 4
assert reachable_count(graph, 4) == 1

四、Java 图实现：迭代栈与状态

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class Main {
    static int reachableCount(List<List<Integer>> graph, int start) {
        int n = graph.size();
        if (start < 0 || start >= n) {
            throw new IllegalArgumentException("start vertex is out of range");
        }
        boolean[] visited = new boolean[n];
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        visited[start] = true;
        stack.push(start);
        int count = 0;
        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            count++;
            for (int neighbor : graph.get(vertex)) {
                if (neighbor < 0 || neighbor >= n) {
                    throw new IllegalArgumentException("neighbor is out of range");
                }
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        List<List<Integer>> graph = new ArrayList<>();
        graph.add(List.of(1, 2));
        graph.add(List.of(0, 2));
        graph.add(List.of(0, 1, 3));
        graph.add(List.of(2));
        graph.add(List.of());
        assert reachableCount(graph, 0) == 4;
        assert reachableCount(graph, 4) == 1;
    }
}

五、正确性、复杂度与误区

图 DFS 的不变式是：已访问集合中的每个节点都从起点可达；每次仅把尚未标记的邻居压栈，并在压栈时立即标记，从而保证每个顶点最多入栈一次。邻接表实现的时间复杂度为 O(V + E)，空间复杂度为 O(V)。有向图只沿出边访问；若要找弱连通分量，需按问题定义将边视为无向或构建反向关系。

• 树的递归搜索不要机械地添加全局 visited，除非输入可能共享节点或不是树。
• 图搜索不要只靠递归深度限制来避免环；需要正确的 visited 语义。
• 枚举所有简单路径时，结果数可能是指数级，不能把复杂度简单说成 O(V+E)。
• 若只找一条可达路径，可额外记录父节点；若需最少边数，下一篇的 BFS 更合适。

小结与衔接

DFS 的本质是沿分支深入，访问状态的生命周期取决于问题：遍历图时全局保留，枚举路径时可能在回溯中撤销，树递归中通常不需要。需要无权图最短路径时，下一篇将用 BFS 按层扩展，首次发现节点就能确定最少边数。