从源点到目标的所有路径：编码题

It looks like only the source link was provided. Could you please share the text you’d like translated to Simplified Chinese? Once I have the content, I’ll translate it while preserving the original formatting, markdown, and code blocks.

问题概述

“从源点到目标的所有路径”问题要求你找出 每一条 从起始节点到目标节点的可能路径，图是有向的。
图通常以邻接表的形式提供，每个节点指向它可以直接到达的邻居列表。你的任务是返回所有以源点开始、以目标结束的有效路径，每条路径按访问顺序列出节点序列。

该问题并不是寻找最短路径或仅仅判断可达性；它明确要求枚举所有路径。你必须生成每一条有效路线，这使得解法的性质完全不同。与优化距离不同，这里是在探索可能性的搜索空间。

Why Not BFS

• 广度优先搜索 (BFS) 在需要在无权图中找到最短路径时表现出色，因为它按距离层次进行探索。
• 在这里，距离并不是目标，逐层探索也没有任何实际优势。
• BFS 往往需要一次性存储大量的部分路径，显著增加内存使用。由于路径枚举本身已经会产生大量候选项，通常你会希望采用一种能够控制内存消耗的方法。

DFS 与回溯

深度优先搜索（DFS）非常适合这个问题，因为它会在转向下一条路径之前，先把一条路径探索到底。

1. 从起点开始。
2. 选择一个邻居，向前继续前进，直到到达目标或没有可走的步伐为止。
3. 当到达目标时，将当前路径记录为一个有效答案。
4. 当遇到死路时，回溯并尝试其他邻居。

回溯机制

• 在图中前进时，维护一个当前路径列表。
• 当选择一个邻居时，将其加入路径。
• 当从该选择的探索返回时，将其移除。

这样可以确保路径列表始终准确地表示当前正在探索的路线，避免在每一步都创建单独的副本，使算法更简洁、更高效。它还保证了系统化的生成过程，不会出现来自先前探索的意外残留。

处理循环

在一般的有向图中，如果允许重复访问节点，循环会导致路径数量无限。许多该问题的变体隐式地使用 有向无环图 (DAG)，从而消除循环风险并保证路径集合是有限的。

如果可能出现循环：

• 在当前递归栈内使用 已访问约束，以防止在同一路径探索中重复访问节点。
• 不要 使用全局已访问集合，因为这会错误地排除在不同路径中重新访问同一节点的有效路径。

复杂度分析

• 时间复杂度 主要取决于路径的数量及其长度，因为必须实际输出所有路径。在稠密的无环图中，路径数量可能呈指数增长，当输出本身是指数级时，没有算法能够避免这一成本。
• 空间复杂度 受递归深度和当前构建的路径影响， 与最长路径的长度成正比。还需要额外的空间来存储输出的路径，这是不可避免的。

为什么这个问题有用

• 它测试候选人是否理解寻找单一解与枚举所有解之间的区别。
• 它检查回溯的基础知识，例如安全地维护可变状态以及正确地撤销更改。
• 认识到输出规模决定运行时间展示了算法成熟度。
• “带回溯的深度优先搜索”模式不仅适用于图遍历，还可用于组合学、约束满足问题以及其他递归枚举任务。

能够清晰解释为何首选 DFS、回溯如何维护当前路径以及如何在不丢失有效路径的情况下处理循环，展示了扎实的算法推理能力，使得此问题成为系统枚举和递归搜索的极佳练习。