‌深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法，其核心特点是“尽可能深”地探索分支，直到无法继续为止，再回溯到上一个节点继续探索。‌ 它的关键亮点包括‌递归或栈的实现方式‌、‌空间复杂度较低‌（通常为O(h)，h为树高）以及‌适用于路径查找、拓扑排序等问题‌。

1. ‌基本思想与流程‌
   DFS从起始节点出发，沿着一条路径不断向下访问未探索的节点，直到遇到叶子节点或无法继续的节点。此时，算法回溯到最近的分叉点，选择另一条未探索的路径重复上述过程。

2. ‌实现方式‌

   • ‌递归实现‌：通过函数调用栈隐式管理回溯逻辑，代码简洁但可能受限于递归深度。
   • ‌栈实现‌：显式用栈存储待访问节点，适合避免递归栈溢出的场景。

3. ‌应用场景‌

   • ‌路径问题‌：如迷宫求解、图中两节点间路径检测。
   • ‌拓扑排序‌：对有向无环图（DAG）进行线性排序。
   • ‌连通性分析‌：判断图的连通分量或强连通分量。

4. ‌优缺点分析‌

   • ‌优点‌：空间效率高（无需存储所有节点），适合深层或目标明确的搜索。
   • ‌缺点‌：可能陷入无限分支（如图中存在环且未标记已访问节点），且不保证找到最短路径。

DFS通过系统化的回溯机制高效探索复杂结构，是解决许多图论问题的基石。使用时需注意‌环的处理（如标记已访问节点）‌和‌目标问题的适配性‌。