题目重点：以明确的有向邻接表训练契约写迭代 DFS，解释 visited、当前路径和最短路区别，并与独立 BFS 可达性对照。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版输入有向邻接表与 start/target，返回任意一条简单路径，找不到返回 None；若 start=target 返回单节点路径。
- 邻接列表顺序决定哪一条合法路径先被找到；题目没有字典序或最短要求。
解题路线
- 迭代栈保存 (节点, 邻居迭代器)，另用 path 保存当前栈上的节点；visited 保证环不会使搜索无限循环。
- 进入未访问邻居时将其加入 visited/path/stack，遇 target 复制当前 path 返回；一个节点邻居耗尽时同时弹出栈和 path。
- DFS 的 visited 一旦全局标记，不必在回溯时删除：本题只求任意路径，之后再从其他父节点到达同一节点不会带来新的可达节点。若要求枚举所有简单路径，visited 必须改为当前路径集合。
- 要最短边数必须 BFS；DFS 先遇到的路径长度可能远大于最短。
手动走一遍
A→B、B→A、A→C、C→D：DFS 遇 B→A 会因 visited 跳过，回溯到 A 后走 C→D，返回 A,C,D。若目标不存在，耗尽所有可达节点后返回 None。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def find_path(graph: dict[str, list[str]], start: str, target: str) -> list[str] | None:
"""Training contract: directed adjacency list; return one path, not shortest."""
stack = [(start, iter(graph.get(start, [])))]
path = [start]
visited = {start}
while stack:
node, neighbors = stack[-1]
if node == target:
return path.copy()
neighbor = next(neighbors, None)
if neighbor is None:
stack.pop()
path.pop()
continue
if neighbor in visited:
continue
visited.add(neighbor)
path.append(neighbor)
stack.append((neighbor, iter(graph.get(neighbor, []))))
return None
复杂度
邻接表 V 个节点、E 条边，每点/边至多处理一次，时间 O(V+E)，栈、visited 和路径 O(V)；若输入图不显式包含终点节点，仍可在邻接边中到达它。
易错点与追问
容易失分的边界
- 有环时不标 visited。
- 回溯时忘弹 path，输出含错误分支。
- 只看邻居而漏判 start=target。
- 把 DFS 第一条路径误称最短。
- 在求任意路径时枚举所有简单路径，退化成指数搜索。
继续深挖
- 如果要全部简单路径，visited 策略如何改，复杂度会怎样？
- 如果要最短路径，换 BFS 时如何恢复 parent 链？
- 图太深时递归栈有什么风险？
- 无向图如何避免立即沿父边走回去？
