视频字幕
深度优先搜索，简称DFS，是计算机科学中一种重要的图遍历算法。它的核心思想是从起始节点开始，沿着一个分支尽可能深入地探索，直到无法继续前进时再回溯。这种算法广泛应用于路径查找、连通性检测等问题。
DFS算法的执行步骤非常清晰。首先从起始节点开始，将其标记为已访问。然后选择一个未访问的邻居节点，递归地对该节点执行DFS。如果当前节点没有未访问的邻居，就回溯到上一个节点。这个过程持续进行，直到所有可达的节点都被访问。
DFS有两种主要的实现方式。递归实现利用函数调用栈，代码简洁直观，但在处理深度很大的图时可能导致栈溢出。栈实现使用显式的栈数据结构，可以避免递归深度的限制，更适合处理大规模的图结构。两种方法的时间复杂度都是O(V+E)，其中V是顶点数，E是边数。
DFS算法有着广泛的应用场景。在路径查找中，DFS可以找到从起点到终点的路径。在连通性检测中，可以判断图中两个节点是否连通。DFS还用于拓扑排序、检测图中的环路、以及迷宫求解等问题。在树结构中，DFS是最常用的遍历方式之一。
DFS算法的时间复杂度是O(V+E)，其中V是顶点数，E是边数。这是因为每个顶点和每条边都会被访问一次。空间复杂度是O(V)，主要用于存储访问状态和递归调用栈。与BFS相比，DFS在时间和空间复杂度上是相同的，但在实际应用中各有优势。DFS特别适合处理稀疏图和需要深度优先搜索的问题。