深度优先搜索（DFS）——算法详解与Java实例

2024-10-26 14:50:06

在之前的剑指offer系列大数问题中遇到了深度优先搜索（DFS）的问题，此处特做出详细讲解与说明。

什么是 DFS（深度优先搜索）？

深度优先搜索（DFS, Depth-First Search）是一种算法，它用来遍历或搜索树、图或其他数据结构。它的核心思想是沿着某条路径尽可能地向前探索，直到不能再继续为止，然后回溯到上一个节点，继续探索其他路径。

想象一下你在迷宫里走路，你会选择一条路尽量往前走，走到尽头发现无法继续时，你就回头，尝试另一条路，直到探索完所有的可能路线。DFS 就像这样的一个过程。

深度优先搜索的工作流程

从起始点开始：选择一个节点作为起点（比如第一位数字）。
探索深度：从这个节点开始，尝试一直往下走，直到到达某个终点或条件不再允许继续。
回溯：如果某条路径走不通，回退到上一个节点，继续尝试其他的可能路径。
重复以上步骤：直到所有路径都被探索完。

DFS 的递归实现

DFS 通常使用递归来实现，因为递归函数天然地支持“深入”一条路径然后“回溯”。每次递归调用函数时，就像进入了下一层迷宫，每当递归结束时，就回到上一层迷宫继续走其他路线。

DFS 的应用举例：生成数字组合

我们以这道题目为例来详细讲解 DFS 如何应用。

题目要求我们生成长度从 1 到 n 的所有数字组合，且数字不能以 0 开头。可以通过 DFS 递归的方式来逐位生成这些数字。

1. 核心 DFS 函数

这个 DFS 函数负责生成长度为 len 的数字组合，它的每次调用负责确定某一位数字。比如，第一层递归生成第一位数字，第二层递归生成第二位数字，直到生成完整的长度为 len 的数字。

void dfs(int x, int len) {
    if (x == len) {  // 递归终止条件：所有位数已经确定
        res.add(cur.toString());  // 将当前生成的数字加入结果集
        return;  // 停止当前递归
    }
    int start = (x == 0) ? 1 : 0;  // 如果是第一位数字，不能为 '0'
    for (int i = start; i < 10; i++) {  // 从 '1' 到 '9'（第一位），从 '0' 到 '9'（后续位）
        cur.append(NUM[i]);  // 添加当前位的数字
        dfs(x + 1, len);  // 递归调用，继续生成下一位
        cur.deleteCharAt(cur.length() - 1);  // 回溯，删除刚刚添加的数字
    }
}

2. 递归终止条件

if (x == len) {
    res.add(cur.toString());
    return;
}

这里 x == len 是递归的终止条件，也就是当已经生成了 len 位数字时，当前递归停止，将生成的数字存储到结果集中。终止递归就意味着到达了我们想要的目标，没必要继续深入下去。

3. 回溯

cur.deleteCharAt(cur.length() - 1);

在递归结束后，回退一步，也就是删除刚才加入的数字。这样可以尝试其他可能的组合。回溯是 DFS 的重要特性，通过回溯可以探索所有可能的路径，而不遗漏任何情况。

4. 循环探索数字

for (int i = start; i < 10; i++) {
    cur.append(NUM[i]);
    dfs(x + 1, len);
    cur.deleteCharAt(cur.length() - 1);
}

这个循环负责尝试每一个可能的数字，从 start 到 9。对于第一位数字（x == 0），起点是 1，因为数字不能以 0 开头；对于后续位数，起点可以是 0。

5. 总控函数

for (int i = start; i < 10; i++) {
    cur.append(NUM[i]);
    dfs(x + 1, len);
    cur.deleteCharAt(cur.length() - 1);
}

这个函数遍历所有可能的数字长度，从 1 到 n，然后调用 dfs(0, i) 生成长度为 i 的所有数字组合。

DFS 的特点

优先深度：DFS 总是尽量先沿着一条路径深入到底，直到不能继续，再回溯探索其他路径。
递归和回溯：每次深入到一个新状态（递归），并通过回溯来返回上一个状态。回溯后可以尝试其他选项（比如删除刚添加的数字，试下一个数字）。
时间复杂度：DFS 的时间复杂度取决于递归深度和每次递归尝试的可能分支数。在这个问题中，最多需要生成从 1 到 n 位的数字，分支数是 10（因为数字是从 0 到 9）。

例子

假设 n = 2，DFS 将生成所有长度为 1 和 2 的数字组合：

长度为 1：生成 1, 2, 3, ..., 9。
长度为 2：从 1 开头，生成 10, 11, 12, ..., 99。

通过回溯，DFS 可以生成每一位数字的所有可能性，保证不会遗漏任何组合。

总结

DFS 是一种递归搜索算法，擅长处理组合生成、路径搜索等问题。它通过递归深入每一条路径，在遇到终止条件后回溯到上一步继续搜索其他路径。通过这种方式，它可以遍历所有可能的结果。本题中，DFS 用于生成长度从 1 到 n 的所有数字组合，是一个典型的 DFS 应用场景。

码农公寓