（d）深度优先搜索
看清递归调用栈、状态恢复、环检测的全部细节
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
（d）深度优先搜索
看清递归调用栈、状态恢复、环检测的全部细节
算法
上一页我们沿一条路走到底再回头——这就是 DFS。但「走到底再回头」这套动作为什么能被写成程序？它背后藏着所有算法共同的骨架。
菜谱规定步骤顺序与终点，对应有限性；照做必出菜，对应可行性
框架
DFS 的直觉是『一条路走到底、撞墙再换条』。要把它写成可复用的代码，就得先看清所有 DFS 题共用的那个框架。
选岔路=做选择，撞墙回头=撤销选择；标已走的门=三色标记，防止原地打转
细节
框架已经把 DFS 的骨架搭好了，但真正写代码、调错、对比方案时，几个细节没讲透会踩坑——这一页就把这些「里子」拆开。
画到祖先无记录就擦回最近分叉，从旁支继续——一条路走到底
无向图
前面讲 DFS 时，默认图是有方向的——A 能到 B 不代表 B 能到 A。但现实中很多关系是双向的，比如好友、道路连接，这时就要换一种图来建模。
你加我好友我也加你——关系天然对称，没有谁指向谁
有向图
无向图里 A—B 和 B—A 是同一条边，但现实中很多关系是单向的——你关注了某人，他未必关注你。这一页看「有向图」。
路口是顶点，单行道是带箭头的边，车只能按箭头方向开
多可达域
上一页我们把 DFS 的细节抠到了边和点的层面——递归如何推进、visited 何时置位。但有一个隐含前提：图是连通的。一旦图里出现互不相连的部分，这个前提就破了，单次 DFS 只能跑完其中一个区块。
每座岛是一个可达域，从一岛只能走遍该岛；要踏遍群岛必须从每座岛各派一支探险队
嵌套引理
上一页讲了DFS把图切成多个可达域。现在换个维度看'时间'：每个顶点盖两个戳——发现时刻d和结束时刻f。这两数字围出一段区间，而所有区间之间的关系，整齐得令人惊讶。
进入新顶点像打开更小的套娃；返回时合上，区间一一对应
本节要点
- ✓DFS 的主线是深入、回退、再转向
- ✓判重让每次探索至多发生一次
- ✓有向性改变可达语义，不改变遍历骨架
- ✓跨域与嵌套问题都应守住访问不变量
课后思考
先自己思考，再对照参考答案。三问分别对应：直觉回溯、实现细节、边界情况。
参考答案DFS 要求「后进先出」——刚访问的节点要最先展开，所以选栈；队列是「先进先出」，会同时往所有方向铺开，那是 BFS 的行为。
参考答案理论上访问顺序一致，但有两个细节：入栈顺序要倒过来（如先压右孩子再压左孩子），且必须在入栈时就标记 visited，否则会重复入栈打乱顺序。
参考答案走到底再回退时会再次遇到环上节点，导致重复访问甚至死循环。解决方案是维护 visited 集合（或三色标记），访问过的节点直接跳过。