简介
深度优先算法（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
深度优先搜索的基本步骤如下：
创建一个栈S。
将起始节点v标记为已访问，并将其压入栈S。
当栈S非空时，循环执行以下步骤：
从栈S的顶部弹出一个节点，并访问它。
将该节点的所有未访问过的相邻节点标记为已访问，并将它们压入栈S。
当栈S为空时，算法结束。
深度优先搜索通常用于遍历或搜索树或图，特别是在需要找到从源节点到目标节点的路径时。它也可以用于检测图中的环或解决图的连通性问题。
需要注意的是，深度优先搜索是一种递归算法，因为它会不断地深入搜索树的分支，直到达到叶子节点或无法继续深入为止，然后回溯到上一个节点继续搜索。这种递归性质使得深度优先搜索在某些情况下比广度优先搜索更直观和易于实现。
此外，为了避免重复访问节点和形成无限循环，深度优先搜索通常使用一个集合（如哈希集合）来记录已经访问过的节点。在访问一个节点之前，先检查它是否已经被访问过，如果是，则跳过该节点并继续搜索其他节点。