01先从一个问题出发
检查迷宫里哪些房间能到达。先沿走廊深入，碰到尽头再回到岔路。
一个具体的例子
0 → 1 → 3 到底后回溯，再探索 0 的另一个分支 2。具体顺序取决于邻接顺序。
02最直接的办法，为什么慢？
不记忆访问历史，不断递归探索所有邻居。
暴力 · 有环时可能不终止
一旦遇到环，就会重复走回同一节点，甚至永不终止。
03一步步，推导出优化思路
1
发现可以复用的信息
探索过的节点无需反复展开，用 visited 保存信息。
2
建立可维护的状态
用递归调用栈，或显式后进先出栈，保存待探索节点。
3
消除重复工作
本课用显式栈并在弹出时判重；逆序压邻居使小编号优先访问。
贯穿算法的不变量
只有尚未访问的节点会真正展开邻接表，每个节点至多展开一次。
04让每一步，都看得见
试着先预测下一步，再点击「下一步」验证。变量、动画与代码会同步变化。
Depth-First Search交互演示
STEP 01 / 23无向图 · 源点 0 · 邻居按编号处理
当前处理已处理 / 已确定未处理
01
从节点 0 开始：栈顶在右侧，弹出未访问节点后标记。
dfs.py参考实现 · 当前第 2 行
正在载入代码编辑器…
动画展示参考实现的执行轨迹。切换语言时，当前操作会定位到对应代码行。
05复杂度，来自具体的工作量
时间复杂度
每个节点真正展开一次，所有邻接表总长度 O(E)，重复弹出仍不超过入栈次数。
辅助空间
本课在弹出时判重，同一节点可重复入栈，栈最坏 O(E)，visited 为 O(V)。递归 DFS 或入栈判重的版本可做到辅助空间 O(V)。
06看到什么，应该想到它？
关键词只是线索，继续检查适用条件07这些细节，容易踩坑
01
记得处理环
图的 DFS 需要 visited；树上也要避免沿无向边回到父节点。
02
DFS 不保证最短
首次到达只表示找到一条路，并不保证边数最少。
08把想法带进真实题目
先说出模式和适用条件，再开始写代码。
09不用背模板，回答这几个问题
01显式 DFS 用什么结构？
02DFS 首次找到的路径一定最短吗？
03为什么弹出后还要检查 visited？
你已经走完了这次推导。
能用自己的话解释复杂度和不变量，再标记为掌握。