图 · 单步演示
深度优先搜索（DFS）
从起点出发，沿着一个没访问过的邻居一直往深处走，走到没路了就退回上一个顶点，换下一个邻居继续。递归调用栈记下了回退的路线。
调用栈（底 → 顶）（空）
访问顺序（空）
步 001 / 038从 A 出发做深度优先搜索：一条路走到底，走不动了再退回上一个岔口。邻居按名称顺序处理。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
DFS(u)：标记 u；访问 ufor v in u 的邻居（按名称顺序）if v 未访问：DFS(v)
变量
| u | — |
|---|---|
| 递归深度 | 0 |
| 已访问 | [] |
复杂度
| 最好情况 | O(V + E) |
|---|---|
| 平均情况 | O(V + E) |
| 最坏情况 | O(V + E) |
| 额外空间 | O(V) |
邻接表下每个顶点进入一次、每条边从两端各看一次。递归深度最多 V 层。
要点
- 找连通块、判断有没有环、拓扑排序都建立在 DFS 上。
- 同一张图，DFS 与 BFS 的访问顺序一般不同，把两个演示用同样的输入对照着看。
常见错误
图很大时递归层数可能超过语言的调用栈上限，这时要改用显式的栈来写。