所有可能路径

记住「到终点就存一份、每个邻居 push 进去递归再 pop 出来」,下面逐帧套它。

先看清这张图:节点 0 是起点(紫色)、节点 5 是终点(绿色)。箭头是有向边,例如 0 能到 1 和 2,1 能到 3 和 4。无环,所以一路往下走不会回到走过的点。

把起点 0 放进当前路径,从 0 开始 DFS。当前路径只有 [0]。0 不是终点,接下来逐个试它的邻居 1、2。

从 0 沿边深入到邻居 1:把 1 压进当前路径,现在路径是 0 → 1。继续从 1 往它的邻居走。

从 1 沿边深入到邻居 3:把 3 压进当前路径,现在路径是 0 → 1 → 3。继续从 3 往它的邻居走。

从 3 沿边深入到邻居 5:把 5 压进当前路径,现在路径是 0 → 1 → 3 → 5。它正是终点,下一步就该记一条。

走到了终点 5!当前路径是 0 → 1 → 3 → 5。把它复制一份存进答案(整条路径变绿),这是第 1 条。然后返回,去试别的岔路。

从 5 这条分支回来了,把 5 弹出当前路径,回退到 3,路径缩回 0 → 1 → 3。3 的邻居都试完了,再往上回退。

从 3 这条分支回来了,把 3 弹出当前路径,回退到 1,路径缩回 0 → 1。1 还有没试过的邻居,接着试下一个。

从 1 沿边深入到邻居 4:把 4 压进当前路径,现在路径是 0 → 1 → 4。继续从 4 往它的邻居走。

从 4 沿边深入到邻居 5:把 5 压进当前路径,现在路径是 0 → 1 → 4 → 5。它正是终点,下一步就该记一条。

走到了终点 5!当前路径是 0 → 1 → 4 → 5。把它复制一份存进答案(整条路径变绿),这是第 2 条。然后返回,去试别的岔路。

从 5 这条分支回来了,把 5 弹出当前路径,回退到 4,路径缩回 0 → 1 → 4。4 的邻居都试完了,再往上回退。

从 4 这条分支回来了,把 4 弹出当前路径,回退到 1,路径缩回 0 → 1。1 的邻居都试完了,再往上回退。

从 1 这条分支回来了,把 1 弹出当前路径,回退到 0,路径缩回 0。0 还有没试过的邻居,接着试下一个。

从 0 沿边深入到邻居 2:把 2 压进当前路径,现在路径是 0 → 2。继续从 2 往它的邻居走。

从 2 沿边深入到邻居 4:把 4 压进当前路径,现在路径是 0 → 2 → 4。继续从 4 往它的邻居走。

从 4 沿边深入到邻居 5:把 5 压进当前路径,现在路径是 0 → 2 → 4 → 5。它正是终点,下一步就该记一条。

走到了终点 5!当前路径是 0 → 2 → 4 → 5。把它复制一份存进答案(整条路径变绿),这是第 3 条。然后返回,去试别的岔路。

从 5 这条分支回来了,把 5 弹出当前路径,回退到 4,路径缩回 0 → 2 → 4。4 的邻居都试完了,再往上回退。

从 4 这条分支回来了,把 4 弹出当前路径,回退到 2,路径缩回 0 → 2。2 的邻居都试完了,再往上回退。

从 2 这条分支回来了,把 2 弹出当前路径,回退到 0,路径缩回 0。0 的邻居都试完了,再往上回退。

DFS 全部跑完,回溯到最后路径只剩起点 [0](dfs(0) 结束后不再用它)。一共找到 3 条从 0 到 5 的路径:0→1→3→5、0→1→4→5、0→2→4→5。回头看,我们就是一路深入、到终点存一份、回溯换岔路,把每条路都不重不漏地走了一遍。

边界:两点一条路;0 直达终点立即记;共用节点的多条路都要枚举。

两个追问:可用 BFS 存路径;复杂度被输出量(可能指数级)主导,无法更优。