深度优先搜索★★★

DFS

解决哪类问题

:::success 在树/图中搜索 :::

代码模板

判出口（终点、越界）->剪枝->扩展->标记->递归->还原

/*
 * Return true if there is a path from cur to target.
 */
boolean dfs(Node cur, Node target, Set<Node> visited) {
    if (cur == target) // 退出条件
        return true;
    for (Node next: cur.nexts) { // 尝试每一种可能性
        if (!visited.contains(next)) { // 未访问
            visited.add(next); // 标记访问
            if (dfs(next, target, visited)) // 更新结果
                return true
            // 部分可能有回溯
        }
    }
    return false;
}

复杂度

O(所有节点的规模)

运用思想

递归、迭代、枚举、贪心、回溯、剪枝

例题

树

图