**深度优先搜索（DFS）**是一种用于遍历或搜索树、图等数据结构的算法，核心思想是“一条路走到底”，通过递归或栈实现，优先探索当前路径的最深节点，直到无法继续再回溯。

1. 基本原理

DFS从起点出发，沿着一条分支不断深入，直到到达叶子节点或无法继续的节点，然后回溯到上一个分叉点，选择另一条未探索的路径。这种“纵向优先”的策略适合解决迷宫问题、拓扑排序等场景。

2. 实现方式

• 递归：通过函数调用栈隐式实现回溯，代码简洁但可能受栈深度限制。
• 显式栈：手动维护栈结构，避免递归的潜在溢出问题，适合大规模数据。

3. 应用场景

• 路径查找：如迷宫求解、图中两节点连通性判断。
• 拓扑排序：对有向无环图（DAG）进行线性排序。
• 生成树/图：用于生成图的深度优先生成树或检测环路。

4. 优缺点

• 优点：内存消耗较低（仅存储当前路径）、适合目标明确的深度探索。
• 缺点：可能陷入无限循环（未处理重复访问）、不保证找到最短路径。

总结：DFS是算法中的“探险家”，适合需要彻底探索单一路径的场景，但需注意循环风险和效率权衡。实际应用中，结合剪枝或记忆化技术可优化性能。