Depth First Search

深度优先搜索（Depth-First Search, DFS） 是一种用于遍历或搜索树或图的算法。和BFS相反，它从一个起始节点开始，尽可能深入地探索每个分支，直到达到一个没有未访问子节点的节点，然后回溯到上一个节点，继续探索其他分支。DFS 可以使用递归或栈来实现。

DFS 的基本步骤

1. 初始化：选择一个起始节点，并将其标记为已访问。可以使用一个栈或递归来管理待访问的节点。

2. 访问节点：

   • 访问当前节点并处理（例如，打印节点值或检查是否为目标节点）。
   • 遍历当前节点的所有未被访问的相邻节点，依次进行 DFS。

3. 回溯：当所有相邻节点都被访问后，回溯到上一个节点，继续探索其他未访问的分支。

DFS 的特点

• 深度优先：DFS 尽可能深入每个分支，适合用于寻找路径或解决问题的深层结构。
• 使用栈：DFS 可以使用显式的栈来管理待访问的节点，或者使用递归调用栈。
• 时间复杂度：对于图的 DFS，时间复杂度为 $O(V+E)$ ，其中 $V$ 是节点数，$E$ 是边数。
• 空间复杂度：空间复杂度通常为 $O(V)$，用于存储已访问节点和栈。