一起动脑筋 · 先看一个小故事
机器人探索树屋，先沿一个分支走到没有新路，再退回来试别的分支。
把过程摊开来看
- 起点 A先选 B
- 从 B继续到 D
- D 无新路退回 B
- 再探索尚未访问的分支
深度优先搜索先深入一个分支，再回退探索其他分支。
用栈或递归可记住回来的位置。图中有环时，还需要管理已访问状态。
01什么是 DFS？
DFS（Depth-First Search，深度优先搜索）的直觉是：
先沿一条路尽量走深，走不下去再回来换路
02在一棵树上怎样走？
A
BC
DEF
从 A 出发，可以先进入 B，再继续深入 B 的子节点，完成后再回到 A 去处理 C。
03递归 DFS 怎样写？
void dfs(int u) {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v);
}
}
}每次进入一个节点，就继续递归访问一个尚未访问的邻居。
04DFS 一定要用递归吗？
不一定。也可以显式使用栈：
std::stack<int> st;
st.push(start);递归 DFS 使用的是函数调用栈；迭代 DFS 则自己维护一个栈结构。
05为什么图里通常要 visited？
因为图可能有环。如果 A-B-C-A 构成环，不记录访问状态就可能不停绕圈。
06DFS 能做什么？
- 遍历图或树
- 判断可达性
- 寻找连通分量
- 回溯搜索
- 拓扑、桥、割点等更高级图算法的基础
你已经知道了什么
- DFS 会沿一条路径尽量深入。
- 走不下去后再退回上一层。
- DFS 可以递归实现，也可以用栈实现。
- 图中常需要 visited 防止重复访问。
- DFS 是很多图和回溯算法的基础。
下一篇：DFS 和递归有什么关系？
轮到你来试一试
在一条路尽头没找到目标，应该马上说不存在吗？
想好了吗？点开看解释
不能，应回退到还有未探索分支的位置继续搜索。