深度优先搜索(DFS)

定义

深度优先搜索（Depth First Search）是一种遍历或搜索树与图的策略。它从起点出发沿一条路径尽可能深入，走到无路可走时再回溯到上一个分叉点尝试其他分支。

原理

DFS 可以用递归自然实现，也可用显式栈迭代实现，本质都是后进先出地处理待访问节点。遍历过程中需用访问标记数组避免在图中重复访问或陷入环。从某节点出发依次深入其未访问的邻居，全部探索完后回溯。它能系统地枚举所有路径或状态。

复杂度

• 时间复杂度（邻接表）：O(V+E)
• 空间复杂度（递归栈/访问标记）：O(V)

应用场景

• 连通分量与环检测
• 拓扑排序
• 迷宫求解与回溯算法
• 全排列、组合等状态空间搜索