1 基本概念
深度优先搜索是一类用于遍历和搜索的基础算法，常见于树、图以及各类抽象状态空间。它的核心特点是“先深入、后回退”：从一个起点出发，沿着当前分支不断向下探索，直到无法继续时返回上一步，再转向尚未访问的其他分支。由于这一过程具有明显的层层深入与回溯特征，DFS 常被视为理解递归与栈结构的典型入门算法。
1.1 定义与核心思想
深度优先搜索的基本定义，是在给定起点后，优先访问当前节点所能到达的一个未访问邻接点，并持续重复这一过程，直至当前路径不再存在未访问目标为止。随后算法回到上一个分叉点，继续处理其他未探索分支。
其核心思想并不依赖某种固定的数据结构形态，而是依赖“选择一个方向一直走到底”的策略。正因为如此，DFS 不仅能用于遍历，也能用于查找满足特定约束的解，例如路径、组合、分割方案或满足条件的状态序列。
1.2 与广度优先搜索的区别
深度优先搜索与广度优先搜索都属于图与树的基本遍历方法，但二者的扩展方式不同。BFS 倾向于先访问距离起点较近的节点，按层推进；DFS 则优先沿单一路径尽可能深入，直到无法继续再返回。
从效果上看，BFS 常用于最短路径、分层结构分析等问题，而 DFS 更适合回溯、连通性判断、拓扑关系处理以及需要枚举全部可能性的任务。两者在时间复杂度上通常相近，但在空间占用和搜索顺序上差异明显。
1.3 适用的数据结构
DFS 可以应用于多种对象，只要对象之间存在可导航的“下一步”关系，就可以构建深度优先的搜索过程。
1.3.1 树
在树结构中，DFS 是最自然的遍历方式之一。由于树本身不存在环，访问过程通常更直接，常见形式包括前序、中序和后序遍历。树中的 DFS 适合处理层级关系、子树统计、路径信息传递等任务。
1.3.2 图
在图结构中，DFS 需要额外维护访问状态，以避免在存在环时陷入重复访问。无论是无向图还是有向图，DFS 都能用于遍历连通部分、发现路径、检测环以及构造后续算法所需的顺序信息。
1.3.3 隐式状态空间
除了显式图与树，DFS 还常用于隐式状态空间，例如棋盘局面、字符串变换过程或搜索树。此时节点不一定以明文形式存储，往往由当前状态和可执行操作动态生成。许多经典回溯题都属于这一类。
1.4 访问顺序与回溯机制
DFS 的访问顺序通常受邻接关系的排列影响。对同一数据结构，不同的邻接遍历顺序可能导致不同的访问结果，但不改变“先深后广”的总体特征。
回溯机制是 DFS 的关键部分。搜索进入某一分支后，会在该分支内部尽可能前进；当该方向无法继续或已得到所需结果时，算法会撤销当前选择并返回上层节点，继续尝试其他可能性。正是这种“进入—探索—返回”的循环，使 DFS 成为回溯问题的基础。
2 算法原理
DFS 的实现方式主要有递归与迭代两种。前者直接利用函数调用栈表达深入与返回的过程，后者则显式维护一个栈结构来模拟递归行为。两种实现本质一致，只是表达形式不同。
2.1 递归实现
递归实现是 DFS 最常见的写法。对当前节点进行访问后，依次处理所有未访问的邻接节点，并在每个邻接节点上再次执行同样的过程。
2.1.1 递归调用过程
递归调用可以看作一条“向下展开”的路径。每进入一个新的节点，就会生成一个新的调用层级；当该节点的后续分支处理完毕，控制权自动回到上一层调用，继续完成剩余邻接点的搜索。这个过程与人们在树状问题中逐层深入再返回的直觉高度一致。
2.1.2 终止条件
递归必须设定明确的终止条件。常见终止条件包括：当前节点为空、当前节点已访问、当前状态不再满足约束，或已达到目标状态。在图遍历中，最常见的终止条件是“该节点已被标记访问”，以防止重复搜索。
2.2 迭代实现
迭代实现使用显式栈替代系统调用栈，以手动控制搜索过程。它通常先将起点压栈，然后在循环中不断弹出栈顶元素，访问该节点，并将其未访问邻接点压入栈中。
2.2.1 显式栈的使用
显式栈允许程序员更精细地控制节点入栈顺序，从而影响搜索顺序。为了更接近递归版本的访问结果，通常需要逆序压入邻接点，使得栈顶元素与递归调用的执行顺序尽量一致。
2.2.2 递归与迭代的等价性
从算法本质上看，递归与迭代只是实现层面的不同。递归借助语言运行时自动维护上下文，迭代则由程序显式记录当前状态。只要访问标记、入栈顺序和终止条件设置得当，两者在遍历结果上可以做到等价。
2.3 伪代码表示
DFS(u):
标记 u 已访问
处理 u
for v in u 的所有邻接点:
if v 未访问:
DFS(v)对于迭代形式，可概括为：
将起点入栈
while 栈非空:
取出栈顶节点 u
if u 未访问:
标记 u 已访问
处理 u
将 u 的未访问邻接点按合适顺序入栈3 算法性质
DFS 作为基础遍历算法，具有较清晰的理论性质。其是否能覆盖全部可达节点、是否能正确得到遍历结果，以及复杂度如何，通常取决于图的表示方式和具体实现。
3.1 完整性
在有限图或有限树中，只要起点所在的连通区域可达，并且访问标记处理正确，DFS 能访问所有与起点连通的节点。对于搜索问题而言，只要状态空间有限且转移规则完整，DFS 也能在理论上遍历全部可达状态。
3.2 正确性
DFS 的正确性主要体现在两点：其一，不会遗漏可达节点；其二，不会对已访问节点进行无意义重复展开。前者依赖对所有邻接方向的系统探索，后者依赖访问标记或等价机制。若用于判环、拓扑排序或强连通分量等任务，还需结合专门的辅助规则，才能保证结果符合算法定义。
3.3 时间复杂度
DFS 的时间开销通常与节点数和边数成线性关系，但具体表达会因存储结构不同而变化。
3.3.1 邻接表表示下的复杂度
在邻接表中，每个节点及其边在遍历中通常只会被检查有限次，因此总时间复杂度一般可写为 O(V + E)，其中 V 为顶点数，E 为边数。对于树而言，可简化为 O(N)。
3.3.2 邻接矩阵表示下的复杂度
在邻接矩阵中，查找某个节点的所有邻接点需要扫描整行，因此无论实际边数多少，常见复杂度往往达到 O(V^2)。当图较稀疏时，这种表示方式的效率通常不如邻接表。
3.4 空间复杂度
DFS 的空间消耗主要来自访问标记和栈结构。若算法用于复杂状态搜索，还可能额外使用路径记录、剪枝信息或备忘结构。
3.4.1 递归栈空间
递归版本的空间开销主要来自函数调用栈，最坏情况下深度可达到节点数级别。对于链状结构或极深搜索树，递归栈可能成为限制因素。
3.4.2 显式栈空间
迭代版本使用显式栈保存待处理节点，其最坏空间规模同样可能达到搜索深度的量级。与递归相比，它更便于控制内存使用，也更不容易受到语言默认栈深限制的影响。
4 图与树中的应用
DFS 在树和图中用途广泛，既可以作为独立遍历工具，也常作为更复杂算法的基础步骤。
4.1 树的遍历
树结构中的 DFS 是许多经典遍历方式的统一基础。
4.1.1 前序遍历
前序遍历的顺序通常是“根—左子树—右子树”或更一般地“当前节点—各子节点”。它适合在进入子树前记录节点信息，例如复制结构、序列化或层级编码。
4.1.2 中序遍历
中序遍历常见于二叉树，其顺序为“左子树—根—右子树”。在二叉搜索树中，中序遍历常能得到有序结果，因此具有很强的实用价值。
4.1.3 后序遍历
后序遍历会先处理子节点，再回到父节点，顺序通常为“左子树—右子树—根”。这种方式适合自底向上的计算，例如子树大小、深度、动态规划值或删除节点前的资源回收。
4.2 图的连通性分析
DFS 常被用来判断图的连通结构以及节点之间的可达关系。
4.2.1 无向图连通分量
在无向图中，从任一未访问节点开始执行 DFS，能够得到一个连通分量。重复从新的未访问节点启动 DFS，可依次划分出整个图的所有连通分量。
4.2.2 有向图可达性
在有向图中，DFS 可用于判断从某一源点是否能到达目标点，也可用于枚举从起点出发能够走到的全部节点。由于边存在方向性，可达性结果通常比无向图更具条件性。
4.3 路径与环检测
DFS 不仅能找路，也能辅助识别图中的环结构。
4.3.1 有向图判环
在有向图中，常通过记录节点的访问状态，区分“未访问、正在访问、已完成”三种情况。若在搜索过程中遇到正在访问中的节点，通常表示存在回边，从而说明图中有环。
4.3.2 无向图判环
无向图中判环时，需要注意不要把来自父节点的边误判为环。一般会在 DFS 中记录父节点，并在遇到已访问节点时判断其是否为当前节点的父亲；若不是，则可视为发现了环。
4.4 拓扑排序
拓扑排序常用于有向无环图。DFS 参与拓扑排序时，通常在节点的所有后继节点处理完毕后，再将该节点加入结果序列。最终得到的逆后序序列即为一种合法拓扑序。
4.5 强连通分量
在有向图中，强连通分量指任意两点之间都可互相到达的最大子图。DFS 是求解强连通分量的重要工具，常用于构造节点访问顺序、识别可回到起点的结构，并为后续分组提供基础信息。
5 回溯与搜索问题
DFS 之所以在搜索类题目中地位突出，很大程度上源于它天然适合“尝试—失败—撤销—再尝试”的过程。
5.1 穷举搜索中的应用
在需要枚举所有可能方案的问题中，DFS 可以逐步构建候选解，并在每一步判断当前选择是否继续有效。若当前路线无法产生目标结果，就返回上层并尝试其他分支。这种方式适合规模适中但分支较多的组合型问题。
5.2 迷宫与路径规划
迷宫问题通常可抽象为网格中的可达路径搜索。DFS 可以从起点出发探索上下左右或更多方向，在记录访问状态后寻找终点或全部可行路线。若只需判断“是否存在路径”，DFS 往往足够；若要求最短路径，则通常更适合 BFS。
5.3 组合生成问题
组合生成类问题是 DFS 回溯的典型应用场景，核心在于通过逐层选择构造结果。
5.3.1 子集枚举
子集枚举通常在每个元素上作“选或不选”两种决策，形成二叉式搜索树。DFS 可以系统地遍历所有选择路径，从而列出幂集中的全部子集。
5.3.2 排列枚举
排列问题强调顺序，因此每一步都要在尚未使用的元素中选择一个加入当前序列。DFS 会不断扩展当前排列，并通过回退恢复现场，以便尝试其他元素。
5.3.3 组合枚举
组合枚举关注的是从元素集合中选出若干个，不强调顺序。DFS 常通过控制起始下标避免重复选择，使得每个组合只被生成一次。
5.4 剪枝策略
剪枝是提升 DFS 效率的重要手段，指在搜索过程中提前排除不可能或不值得继续探索的分支。
5.4.1 可行性剪枝
可行性剪枝用于判断当前部分解是否已经违背约束。例如在数独、八皇后或容量限制问题中，一旦局部状态冲突，就无需继续向下搜索。
5.4.2 最优性剪枝
最优性剪枝常用于优化型问题。当当前路径已经不可能优于已知最优解，或者某个估计下界已无法满足目标时，可以直接回退，从而减少无效展开。
6 变体与扩展
围绕标准 DFS，人们发展出了多种变体，以适应深度受限、目标未知或状态空间过大的情形。
6.1 深度限制搜索
深度限制搜索是在 DFS 基础上加入最大深度约束，防止搜索无限深入。它常用于状态空间较大但需要控制展开范围的场景，也可作为其他算法的组成部分。
6.2 迭代加深深度优先搜索
迭代加深深度优先搜索结合了 DFS 的低空间开销和按层逐步扩展的思想。它从较小深度限制开始，反复运行深度限制搜索，每次只增加一层深度上界，从而在某些情况下兼顾空间与完整性。
6.3 双向搜索中的相关思想
双向搜索从起点和终点两端同时展开，试图在中间汇合。虽然其结构不完全等同于标准 DFS，但在某些问题中也会借用深度优先的分支展开思想，以减少搜索空间。
6.4 记忆化搜索
记忆化搜索本质上是在 DFS 基础上加入缓存，用于保存已计算过的子问题结果。这样，当相同状态再次出现时，可直接复用结果而无需重复展开，尤其适用于重叠子问题明显的动态规划场景。
7 实现细节
DFS 的编码看似简单，但在实际应用中，访问标记、顺序控制和栈深管理等细节都会影响最终效果。
7.1 访问标记的维护
访问标记是防止重复搜索的核心机制。对于图遍历，通常在节点首次进入时立即标记；对于某些回溯题，则可能在离开节点时撤销标记，以便让不同路径重新使用该状态。具体做法取决于问题是否允许重复使用节点。
7.2 邻接表遍历顺序
邻接表中的节点顺序会直接影响 DFS 的访问轨迹。在需要稳定输出或特定字典序结果时，常先对邻接点排序，再按预期顺序遍历。若使用显式栈，还需考虑压栈顺序与弹栈顺序之间的对应关系。
7.3 递归深度限制与栈溢出
当搜索深度很大时，递归实现可能超过语言运行时栈限制，从而引发栈溢出。对于链状图、深层树或高分支回溯问题，常改用迭代版本，或通过语言提供的栈配置进行调整。
7.4 多源 DFS 的处理方式
多源 DFS 通常指从多个起点分别或同时开始搜索，用于处理多连通块、多入口传播或多个候选源点的问题。实现时可将所有源点依次加入处理队列式的初始化步骤，然后对每个尚未访问的起点启动一次 DFS。
7.5 常见编码模式
常见的 DFS 编码模式包括：先访问当前节点，再递归邻接点；在回溯题中先做选择、递归、再撤销选择；在树形 DP 中先处理子节点，再合并结果。不同模式服务于不同任务，但都遵循“深入与回退”这一基本框架。
8 典型题型与案例
DFS 在题目设计中覆盖面很广，尤其常出现在树、网格、拓扑关系和约束搜索等类型中。
8.1 树形问题
树形题目常要求统计子树信息、寻找路径、求树高、判断平衡性或完成结构转换。DFS 能以自然的递归形式逐层处理子树，适合大量自底向上或自顶向下的计算。
8.2 网格遍历问题
网格题通常将每个格子视为一个节点，相邻格之间通过上下左右或对角方向连接。DFS 可用于岛屿计数、区域染色、连通块识别以及路径可达性判断。
8.3 拓扑相关问题
涉及依赖关系、先后顺序或任务编排的问题，常可转化为有向图上的 DFS。拓扑排序、环检测以及部分依赖消解类题目，往往都建立在 DFS 访问顺序的基础上。
8.4 约束满足问题
约束满足问题需要在大量候选解中寻找满足条件的方案。DFS 配合剪枝非常适合此类任务，例如数独、八皇后、填表和某些表达式构造问题。通过在每层做合法性判断，可以显著减少搜索量。
8.5 经典竞赛题应用
在编程竞赛中，DFS 经常以“模板题”形式出现，也常作为其他算法的底层工具。许多看似复杂的题目，实际都可拆解为遍历、判环、连通块、回溯枚举或记忆化搜索等 DFS 相关结构。