代码与动画 DEPTH-FIRST SEARCH
深度优先遍历.
沿一条分支深入，在访问完邻接节点后回溯。
时间 O(V + E)空间 O(V)递归 · 邻接表
原理与执行逻辑
沿一条尚未访问的分支持续深入，直到没有可扩展邻居，再返回上一层继续其他分支。递归调用栈保存当前探索路径。
执行步骤
- 进入节点时检查访问标记，已访问则返回。
- 标记当前节点并加入访问输出。
- 按邻接顺序递归访问未访问节点。
- 当前节点的邻居全部处理完后返回调用方。
关键理解
递归前标记可阻止环导致无限递归。调用栈体现当前路径，访问输出记录发现顺序；DFS 首次找到的路径不保证最短。
简短示例
A 连接 B、C，B 连接 D，按字母访问时先走 A → B → D，再返回 A 处理 C，输出 A、B、D、C。
代码与执行动画
STEP 0 / 36function dfs(graph, start) { const seen = new Set(), result = []; function visit(node) { if (seen.has(node)) return; seen.add(node); result.push(node); for (const next of graph.get(node)) visit(next); } visit(start); return result;}起点 A已发现 0调用栈: 空
当前数据正在操作已访问 / 命中标记 / 指针
0
准备遍历
从指定起点开始，未连通的节点保持未访问状态。
配置图
修改边列表可添加或删除连接，支持不连通图。
深度优先遍历的操作规则
访问前检查 seen，处理环和重复路径；邻接节点按字母顺序访问，返回访问序列。只遍历起点所在连通分量。
对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
- 对应题目200. 岛屿数量打开题目
通过深度遍历标记连通区域，并统计连通分量。