深度优先搜索（Depth First Search，简称DFS）是一种图遍历算法，其核心思想是沿着路径深入访问每个节点，直到无法再深入为止。DFS通常用于图和树的遍历，并且在寻找路径、判断连通性以及计算生成树等问题中具有广泛应用。
DFS的基本过程可以概括为：从一个起始节点开始，首先访问该节点并将其标记为已访问，然后检查其未访问的邻接节点。如果存在未访问的邻接节点，则将其设为新的当前节点并重复上述操作；如果没有未访问的邻接节点，则回溯至上一个节点继续探索其他路径，直到所有可能的路径都被遍历完。
DFS可以通过递归或栈的方式实现。递归实现中，每次选择一个未访问的邻接节点作为新的当前节点，递归地进行DFS；非递归实现则使用栈数据结构来模拟递归过程，遵循后进先出（LIFO）原则。
DFS的一个重要特性是每个节点只能被访问一次，这使得它在处理大规模图时能够有效地避免重复计算。此外，DFS的时间复杂度为O(|V|+|E|)，其中|V|是顶点数，|E|是边数。
DFS在实际应用中非常广泛，例如在迷宫求解、拓扑排序、连通性检测等场景中都能发挥重要作用。
声明：文章来源于网络，如有侵权请联系删除！