题目重点：按单条路径的访问集合回溯，区别全局visited与有环图无限walk。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 只枚举simple path，同路径节点不可重复，有向边，重复邻边去重；无向图需双向建边。
- start==target返回零边路径[start]；节点ID为非None的可哈希值，None作为迭代结束哨兵。
- 原题若允许walk重复节点，有环时可能无限，必须增加长度界等合同，不能宣称已还原该版本。
解题路线
- 当前path与active set仅表示这一条正在探索的路径，新增邻点不在active才入。找到target复制path输出再回退，完成分支退出时从active删点。
- 全局visited会漏答案：start→a→target与start→b→a→target都应输出，第二次访问a来自不同前缀，不该禁用。
- 为什么完整：任意simple path的每步都不在本路径已有节点，搜索会按各邻边枚举它；输出只在target且没有重复节点，因此全部合法。
- 显式迭代器栈实现回溯，避免深链递归；copy输出是必要的，否则未来回退会改变已存path。DAG下可以用memo后缀，但完整路径输出仍可能指数级。
- 评估输出数量和资源：多条路径可能指数增长，真实接口应generator、结果上限或分页；不能写O(V+E)枚举所有答案。
手动走一遍
训练图s→a,b，b→a，a→t，共[s,a,t]与[s,b,a,t]；另加a→s时本合同阻止绕圈，仍输出这两条。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def all_simple_paths(graph,start,target):
"""Directed adjacency map; each vertex at most once per path, edges deduplicated."""
neighbors={v:list(dict.fromkeys(adj)) for v,adj in graph.items()}
output=[]
path=[start]
active={start}
stack=[iter(neighbors.get(start,[]))]
if start==target:return [[start]]
while stack:
nxt=next(stack[-1],None)
if nxt is None:
stack.pop()
active.remove(path.pop())
elif nxt not in active:
path.append(nxt)
active.add(nxt)
if nxt==target:
output.append(path.copy())
active.remove(path.pop())
else:
stack.append(iter(neighbors.get(nxt,[])))
return output
复杂度
记P为输出路径总长度，输出Ω(P)时间/空间。一般回溯还访问未达target的分支，最坏指数；当前path O(V)，示例返回所有结果O(P)，邻接去重O(V+E)。
易错点与追问
容易失分的边界
- global visited漏不同前缀路径。
- 允许重复顶点却忽略无限输出。
- 存path引用而非copy。
- 宣称枚举全路径线性。
继续深挖
- 有最大长度界的walk如何改？
- 只需路径数量时DAG怎样DP？
- 怎样先剪掉根本到不了target的点？
