DFS

定义

DFS（Depth First Search，深度优先搜索）是一种图的遍历算法，沿着树的深度遍历图的结点，尽可能深地搜索图的分支。

算法思想

1. 访问起始顶点 v，标记为已访问
2. 选取 v 的一个未访问邻接顶点 w，递归对 w 进行 DFS
3. 若 v 的所有邻接顶点都已访问，则回溯

实现

通常使用递归或栈实现。

时间复杂度

• 邻接矩阵：$O(V^2)$
• 邻接表：$O(V+E)$

应用

• 拓扑排序
• 连通分量检测
• 迷宫求解
• 回溯算法（全排列、子集等）