深度优先搜索 (DFS) 算法原理与实例讲解

一、DFS 算法的基本思想与原理

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。顾名思义，“深度优先”指的是每次尽可能先往更深层的节点探索，直到无法继续为止，再回溯(backtrack)到上一级节点，继续探索未访问的分支。这个过程利用栈的思想实现：要么使用显式的栈结构，要么通过递归隐式地使用函数调用栈。在搜索过程中，需要标记已访问节点以避免重复遍历。

DFS算法流程图：从起始节点开始，将其标记为已访问并入栈，然后循环执行：查看栈顶节点的邻接节点，若存在未访问节点则访问并入栈；若不存在未访问邻接节点，则将栈顶节点出栈（回溯）；重复上述过程直至栈为空。该流程图展示了DFS算法递归搜索和回溯的过程。

DFS算法常用于穷举所有可能的解空间路径。在遍历图或树时，DFS会记录路径上的节点，并在走到“死胡同”时回溯到最近的分叉点继续搜索其他路径。相比广度优先搜索(BFS)，DFS更适合于搜索解空间深处的解，但不保证首先找到最短路径。下面通过一个简单图例说明 DFS 遍历的顺序和回溯过程。

如图所示：对无向图执行 DFS，从节点 A 开始，访问顺序为 A -> C -> B -> D -> F -> G -> E。红色箭头表示递归深入的路径，蓝色箭头表示在某节点无未访问邻接点时的回溯过程。可以看到，DFS 会先一路向下走到节点 B（无进一步可走），然后回溯到 C 继续访问其下一个邻接点 D；再回溯到 A，转向访问未探索的邻接点 F，依次类推，直到所有节点都被访问。通过这种“深追踪、遇死路后回退”的策略，DFS 能遍历连通图的所有节点。

二、经典入门例题：全排列生成 (C++ 实现)

题目描述：给定一个整数 n，将数字 1~n 排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。

输入格式：共一行，包含一个整数 n。

输出格式：按字典序输出所有排列方案，每个方案占一行。

数据范围：1 ≤ n ≤ 7

样例输入：

3

样例输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

解题思路：这是一道经典的 DFS 回溯问题，用于生成 1~n 的全排列。我们可以使用递归遍历搜索每一种可能的排列构造。在递归过程中，用一个布尔数组记录哪些数字已经被选过，逐步构建排列。当排列长度达到 n 时，将其输出。递归返回时需要撤销选择（回溯），以便尝试其他可能性。

以下提供 C++ 实现的全排列生成代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 15;
int n;
int perm[N];    // 当前排列
bool used[N];   // 标记每个数字是否已被使用

void dfs(int idx) {
    if (idx == n) {
        // 输出当前排列
        for (int i = 0; i < n; ++i) {
            cout << perm[i];
            if (i < n - 1) cout << " ";
        }
        cout << endl;
        return;
    }
    // 尝试放入下一个位置的数字
    for (int num = 1; num <= n; ++num) {
        if (!used[num]) {
            perm[idx] = num;
            used[num] = true;
            dfs(idx + 1);    // 递归构造下一个位置
            used[num] = false;  // 回溯：撤销选择
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n)) {
        return 0;
    }
    dfs(0);
    return 0;
}

代码解析：上述代码中，dfs(idx) 函数用于递归地在第 idx 个位置放置数字。我们维护数组 perm[] 来存储当前构造的排列，布尔数组 used[] 标记某个数字是否已被使用。初始时所有数字未使用，然后从第0位开始递归选数。在递归过程中，每当我们选择一个数字放入当前位后，就标记其已使用并继续递归选下一位；如果当前排列已选满 n 个数字（即 idx == n），则输出这个排列。递归函数返回时，通过 used[num] = false 将该数字重置为未使用状态（回溯），然后尝试下一个可能的数字。这样，DFS 会枚举出所有可能的排列方案且保证按字典序输出（因为我们按数字从小到大尝试）。由于 n 最大为7，最多生成 7! = 5040 种排列，DFS 完全可以在瞬间遍历输出所有结果。

三、蓝桥杯真题分析：《路径之谜》 (DFS 搜索+回溯)

题目链接：蓝桥杯练习系统 Problem 89 - 路径之谜。题目大意如下：有一个 n * n 的方格棋盘，骑士需要从西北角起点走到东南角终点。骑士每次只能向上下左右移动一格（不能斜走或跳跃），且不能重复经过同一个格子。奇特的是，每到达一个新的格子时，骑士都会向正北和正西两个方向各射出一支箭，射中城堡北墙和西墙内对应位置的箭靶。城堡北墙内有 n 个靶子（对应每一列），西墙内有 n 个靶子（对应每一行）。给出北墙和西墙上的箭靶所中的箭数，我们需要还原骑士行走的路径。题目保证了在输入所给的箭数下，骑士的路径唯一。

输入：第一行是整数 n (<= 20)，表示棋盘大小。第二行是 n 个整数，表示北侧墙上从西到东的每个箭靶中的箭数（对应各列被射中的次数）；第三行是 n 个整数，表示西侧墙上从北到南每个箭靶中的箭数（对应各行被射中的次数）。
输出：输出骑士经过的格子编号序列（从起点到终点），一行输出。格子按从北到南、从西到东编号，起点（西北角）编号为0，每行有 n 个格子的编号依次增大，如下所示：

0   1   2  ... 
n   n+1 ...  
...        n*n-1

比如，上图中的方块编号为：

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15
一个 4 * 4 示例中，北墙箭靶数字为 2 4 3 4，西墙箭靶数字为 4 3 3 3。黑线标出了骑士从入口(0)到出口(15)的唯一路径。每经过一个格子，就对应减掉该格子所在行和列各1点箭靶计数，最终所有靶子的箭正好被用尽。该路径按顺序输出其格子编号：0 → 4 → 5 → 1 → 2 → 3 → 7 → 11 → 10 → 9 → 13 → 14 → 15。

解题思路：我们可以用 DFS 来搜索满足箭靶约束的路径。这个问题本质是要求在网格中找到一条从起点到终点的不重复路径，使得每行经过的格子数和每列经过的格子数分别恰好等于给定的箭靶数。DFS 搜索时需要实时跟踪这些约束：每走到一个新格子，就减少该格子所在的那一行和那一列对应的剩余箭数。如果某一步出现某行或某列箭数减为负，说明走不通，需要立即回溯剪枝。此外，终点处还需检查所有行列的箭数是否正好用完（都为0）。搜索过程中用 vis[][] 数组标记已经走过的格子，确保路径不访问重复格。

下面给出该问题的 C++ 实现代码，并确保可以通过所有测试数据：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
int n;
int rowTarget[MAXN], colTarget[MAXN];  // 每行、每列箭靶剩余箭数
bool vis[MAXN][MAXN];                 // 访问标记
vector<int> path;                     // 路径序列（格子编号）
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};  // 四个方向移动

bool dfs(int x, int y) {
    // 如果到达终点，检查所有箭靶是否都用完
    if (x == n-1 && y == n-1) {
        bool success = true;
        for (int i = 0; i < n; ++i) {
            if (rowTarget[i] != 0 || colTarget[i] != 0) {
                success = false;
                break;
            }
        }
        return success;
    }
    // 尝试向四个方向走
    for (auto &d : dirs) {
        int nx = x + d[0], ny = y + d[1];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;    // 边界检查
        if (vis[nx][ny]) continue;                               // 不能走已访问格子
        // 准备走到新格子 (nx, ny)
        // 减少对应行列靶子的箭数
        rowTarget[nx]--;
        colTarget[ny]--;
        vis[nx][ny] = true;
        path.push_back(nx * n + ny);
        // 剪枝：如果削减后某行或某列箭数变为负，则此路径不可能正确
        if (rowTarget[nx] >= 0 && colTarget[ny] >= 0) {
            if (dfs(nx, ny)) {
                return true;  // 找到正确路径，提前返回
            }
        }
        // 回溯：恢复现场
        path.pop_back();
        vis[nx][ny] = false;
        rowTarget[nx]++; 
        colTarget[ny]++; 
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n)) {
        return 0;
    }
    for (int j = 0; j < n; ++j) cin >> colTarget[j];
    for (int i = 0; i < n; ++i) cin >> rowTarget[i];
    // 初始化起点
    memset(vis, 0, sizeof(vis));
    vis[0][0] = true;
    path.clear();
    path.push_back(0);
    // 起点也算走过一个格子，需要射箭
    rowTarget[0]--;
    colTarget[0]--;
    // 执行 DFS 搜索路径
    if (dfs(0, 0)) {
        // 输出路径
        for (size_t k = 0; k < path.size(); ++k) {
            cout << path[k];
            if (k < path.size() - 1) cout << " ";
        }
        cout << endl;
    } else {
        cout << "No path found." << endl;
    }
    return 0;
}

代码说明：我们使用了 rowTarget[i] 和 colTarget[j] 两个数组来记录每行每列剩余的箭数要求，初始值为输入的箭靶数字。vis[][] 是访问矩阵，用于防止走回头路。path 动态记录当前走过的路径（格子编号序列）。DFS 从起点 (0,0) 开始。特别地，起点也算作“经过”的格子，因此我们先将起点标记访问，并将其所在行和列的箭数各减一。接下来进入递归搜索。

在 dfs(x, y) 函数中，如果到达终点，则检查所有行和列的箭数是否恰好用完（都为0）；若是，则找到了解；否则即便到了终点也不是合法路径。否则，尝试从当前格子向四个方向走一步 (nx, ny)。每尝试一个新格子，先检查边界和是否未访问，然后做如下操作：

• 将新格子所在的行 nx 和列 ny 的剩余箭数各减 1（表示走进该格子射出了箭）。
• 将格子标记为已访问，并将其编号加入路径序列。编号计算方式为 id = nx * n + ny。
• 剪枝判断：如果减1后发现 rowTarget[nx] 或 colTarget[ny] 出现负值，说明在这个时间点这行或这列已经走的次数超过了给定箭数，不可能是正确路径，立即回溯撤销操作。
• 如果约束未违背，则递归调用 dfs(nx, ny) 继续向深处搜索。如果递归返回 true，表示已经找到正确路径，则当前也直接返回 true（将结果向上传递）。
• 若递归未找到解，则回溯：弹出路径中的最后一个格子，恢复访问标记，并把刚才扣减的箭数加回来，继续尝试下一个方向。

由于题目保证解的唯一性，我们在找到解后可以直接返回并输出路径。算法在最坏情况下需要遍历所有可能路径，但棋盘最大 20×20 且有严格的箭数约束，大幅剪去了不符合条件的分支。因此 DFS 能够高效地找到唯一解路径。

DFS 策略要点：

• 状态设计：本题通过 rowTarget 和 colTarget 动态维护约束条件（行、列还需经过的步数）。这些约束会随着路径延伸不断减少，DFS 参数中不显式传递它们，但因使用全局数组保存，在递归调用前后通过修改和回溯恢复，等价于维护了状态。
• 路径记录：用 path 保存当前走过的路径，当到达终点且满足约束时，path 即为所求解。注意在进入递归和退出递归时对 path 进行修改（append 和 pop），使得不同分支递归各自维护正确的路径前缀。
• 回溯恢复：典型的 DFS 回溯过程在本题中非常重要。每次尝试一个方向后，无论成功与否，都要将 vis 状态和 rowTarget/colTarget计数复原，以不影响后续其他分支的搜索。
• 剪枝优化：在搜索过程中及时进行剪枝可以极大减少搜索空间。除了基本的越界和访问重复剪枝，我们增加了箭数约束的剪枝——一旦某行或某列的所需箭数被超额消耗（出现负值），立即停止深入。这保证了算法不会徒劳地探索不满足条件的路径。

通过以上分析与代码实现，我们成功利用 DFS 找到了“路径之谜”问题中骑士行走的唯一路线。

四、蓝桥杯真题分析：《飞机降落》 (DFS 搜索+剪枝)

题目链接：蓝桥杯练习系统 Problem 3511 - 飞机降落。题目背景较长，简而言之：有 n 架飞机准备降落，每架飞机有三个参数：最早降落开始时间 $T_i$，还能保持飞行的时间 $D_i$（即从最早降落时刻起还能在空中等待的最长时间），以及降落所需时间 $L_i$。跑道同一时刻只能容纳一架飞机降落，并且必须一架飞机完全降落结束后才能开始让下一架降落。问是否存在一种调度顺序，使得所有飞机都能在各自条件限制下顺利降落？如果存在输出 “YES”，否则输出 “NO”。

解题思路：直观分析，只有上一架飞机降落完毕后，下一架才能开始降落。这实际上是在求一种合理的飞机降落顺序。由于飞机数量 n 的规模很小（题目暗示 n ≈ 10），可以通过DFS尝试所有降落顺序（即对 n 架飞机的全排列进行检查）。然而，直接暴力尝试 $n!$ 种顺序效率不高，我们需要在 DFS 中利用剪枝策略避免不必要的完整排列枚举。主要的剪枝依据是每架飞机的时间条件：

• 飞机 i 最晚必须在 $T_i + D_i$ 时刻开始降落，否则就会因为燃油耗尽等原因无法安全降落。因此当我们决定下一架降落的飞机时，如果当前时间已经大于某架未降落飞机的 $T_i + D_i$，那这架飞机已经没机会了，可直接跳过。
• 我们始终让下一架飞机尽早开始降落：如果当前时间早于该机的最早时间 $T_i$，就等待到 $T_i$ 再降落；如果当前时间已经晚于 $T_i$，则立即在当前时间开始降落。这样可以保证不浪费时间空档，有助于满足所有飞机的时间约束。

基于上述思路，我们设计 DFS 函数参数为 (count, time)：已降落飞机数和当前时间。使用一个布尔数组 landed[] 标记哪些飞机已降落。当 count == n 时表示所有飞机都成功安排降落，返回 true；否则尝试选择尚未降落的飞机降落下一架，每选择一架都检查它是否还能撑到当前时刻。具体实现如下：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
int n;
int T_[MAXN], D[MAXN], L[MAXN];  // 飞机的参数
bool landed[MAXN];               // 标记飞机是否已降落

bool dfs(int count, int currentTime) {
    if (count == n) {
        return true;  // 所有飞机都成功降落
    }
    for (int i = 0; i < n; ++i) {
        if (!landed[i]) {
            // 剪枝：如果飞机 i 等不到 currentTime 就会耗尽，则无法安排它现在降落
            if (T_[i] + D[i] < currentTime) {
                continue;
            }
            // 尝试让飞机 i 当前降落
            landed[i] = true;
            // 起飞时间不能早于 T_[i]，且不能早于 currentTime（上一架结束时间）
            int startTime = max(currentTime, T_[i]);
            int finishTime = startTime + L[i];
            // 递归调度下一架飞机，如果成功则直接返回 true
            if (dfs(count + 1, finishTime)) {
                return true;
            }
            // 回溯：撤销选择飞机 i
            landed[i] = false;
        }
    }
    return false;  // 尝试所有未降落飞机均无法全部安排降落
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    if (!(cin >> t)) {
        return 0;
    }
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> T_[i] >> D[i] >> L[i];
        }
        memset(landed, 0, sizeof(landed));
        if (dfs(0, 0)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

代码说明：我们定义了递归函数 dfs(count, currentTime) 来尝试为第 count+1 架降落的飞机选择哪一架。在每一步中，遍历所有尚未降落的飞机 i，如果它还能坚持到当前时间（即 T_[i] + D[i] >= currentTime），则考虑让它作为下一架降落。将其状态标记为已降落，然后计算它的实际开始降落时间：startTime = max(currentTime, T_[i])。因为可能当前跑道空闲时刻 currentTime 早于飞机的可降落时间，需等到 $T_i$；如果当前时间已经晚于 $T_i$，则飞机一到可以立即降落。计算其降落完成时间 finishTime = startTime + L[i]。接着递归调用 dfs(count+1, finishTime) 安排剩余飞机。如果递归返回 true，表示从该选择开始能成功调度完所有飞机，我们也就返回 true 并终止搜索。若选择飞机 i 无法导出可行方案，则回溯，将其标记还原为未降落状态，继续尝试下一架飞机。

剪枝策略：在选择下一架降落飞机时，我们应用了关键的时间剪枝条件——T_[i] + D[i] >= currentTime。这保证了只有当飞机 i 尚未错过最后降落时机时才考虑调度它。如果当前时间已经超过飞机 i 能等待的极限，那么无论后续怎样安排都不可能让它及时降落，直接跳过以减少不必要的搜索分支。此外，我们采取“尽早降落”的策略（开始时间取 max(currentTime, T_i)），使得调度更紧凑，不会浪费时间片段。这实际上是一个贪心思想的剪枝：在不影响最终可行性的前提下，总是尽快地安排飞机降落，以腾出跑道给后面的飞机。这种策略没有反例，可以认为是安全的局部最优选择。

任务调度逻辑：由于每架飞机降落过程不间断且串行进行，我们相当于在时间轴上为 n 架飞机找到一个无重叠的区间排列。DFS 穷举了不同的排列顺序，而时间计算逻辑确保了：前一架的结束时间就是下一架的开始时间（或稍等至其最早可降落时刻）。这样，通过 DFS + 剪枝，我们在可控的计算量内判断出了是否存在一种降落顺序使所有飞机都及时降落。

算法的最坏时间复杂度近似为 $O(n!)$（当没有任何剪枝时需要检查所有排列），但在实际测试中，由于剪枝条件苛刻，大量排列在前缀阶段就被剪掉，因此效率远优于穷举。n=10 时的全排列为 3,628,800 种，但有效搜索分支要少得多。综上，本题采用 DFS 深度优先搜索所有可能的降落顺序，并结合合理的剪枝策略成功解决了飞机降落调度问题。最终，如果 dfs(0,0) 返回 true，我们输出 “YES”，否则输出 “NO”。