‌DFS算法（深度优先搜索）是一种用于遍历或搜索树/图结构的经典算法，其核心特点是“一条路走到底”，通过递归或栈实现回溯。关键亮点包括：‌

• ‌纵深探索‌：优先访问深层节点，直到无路可走再回溯；
• ‌空间效率高‌：仅需存储当前路径，空间复杂度为O(h)（h为树高）；
• ‌应用广泛‌：适用于路径查找、拓扑排序、连通性分析等场景。

分点解析

1. ‌算法原理‌
   DFS从起点出发，选择一个相邻未访问的节点深入，重复此过程直至无未访问节点，然后回溯到上一个分叉点继续探索。递归实现简洁，显式栈可避免递归深度限制。

2. ‌核心步骤‌

   • ‌访问节点‌：标记当前节点为已访问；
   • ‌递归邻接点‌：对未访问的邻接点递归调用DFS；
   • ‌回溯‌：返回上一节点继续未完成的搜索。

3. ‌与BFS对比‌
   DFS使用栈（后进先出），适合目标较深的场景；BFS用队列（先进先出），适合最短路径问题。DFS可能陷入无限循环（需记录已访问节点）。

4. ‌典型应用‌

   • ‌迷宫求解‌：标记路径并回溯排除死路；
   • ‌拓扑排序‌：对有向无环图（DAG）进行线性排序；
   • ‌连通分量检测‌：判断图中节点的连通性。

总结

DFS以“深度优先”策略高效探索复杂结构，适合需要全面遍历或路径存在的场景，但需注意处理环路和栈溢出问题。合理选择剪枝策略可进一步提升效率。