DFS
深度优先
图核心时间 O(V+E)空间 O(V)
沿一条路走到底再回溯。适合连通性、拓扑、路径枚举、树形 DP。
动画
深度优先：沿一条路走到底，再回溯。
1 / 13
- 当前
- 默认
讲解
递归结构自然，迷宫、岛屿、排列组合、环检测都靠它。
- 01访问 u 并标记。
- 02对每个未访问邻居递归 DFS。
- 03没有邻居时回溯到上一层。
- 04也可用显式栈模拟递归。
易错点
- 有环必须标记，否则无限递归。
- 递归深度可能爆栈，图很大时用显式栈。
代码
function dfs(g, u, seen = new Set(), order = []) {
seen.add(u); order.push(u);
for (const v of g[u] || []) {
if (!seen.has(v)) dfs(g, v, seen, order);
}
return order;
}