所有可能路径 图解题解
这道题到底在问什么
- 输入
- graph=[[1,2],[3,4],[4],[5],[5],[]]
- 输出
- [[0,1,3,5],[0,1,4,5],[0,2,4,5]]
最优解：一步一步想明白
- 3记住「到终点就存一份、每个邻居 push 进去递归再 pop 出来」,下面逐帧套它。
- 4先看清这张图:节点 0 是起点(紫色)、节点 5 是终点(绿色)。箭头是有向边,例如 0 能到 1 和 2,1 能到 3 和 4。无环,所以一路往下走不会回到走过的点。
- 5把起点 0 放进当前路径,从 0 开始 DFS。当前路径只有 [0]。0 不是终点,接下来逐个试它的邻居 1、2。
- 6从 0 沿边深入到邻居 1:把 1 压进当前路径,现在路径是 0 → 1。继续从 1 往它的邻居走。
- 7从 1 沿边深入到邻居 3:把 3 压进当前路径,现在路径是 0 → 1 → 3。继续从 3 往它的邻居走。
- 8从 3 沿边深入到邻居 5:把 5 压进当前路径,现在路径是 0 → 1 → 3 → 5。它正是终点,下一步就该记一条。
- 9走到了终点 5!当前路径是 0 → 1 → 3 → 5。把它复制一份存进答案(整条路径变绿),这是第 1 条。然后返回,去试别的岔路。
- 10从 5 这条分支回来了,把 5 弹出当前路径,回退到 3,路径缩回 0 → 1 → 3。3 的邻居都试完了,再往上回退。
- 11从 3 这条分支回来了,把 3 弹出当前路径,回退到 1,路径缩回 0 → 1。1 还有没试过的邻居,接着试下一个。
- 12从 1 沿边深入到邻居 4:把 4 压进当前路径,现在路径是 0 → 1 → 4。继续从 4 往它的邻居走。
- 13从 4 沿边深入到邻居 5:把 5 压进当前路径,现在路径是 0 → 1 → 4 → 5。它正是终点,下一步就该记一条。
- 14走到了终点 5!当前路径是 0 → 1 → 4 → 5。把它复制一份存进答案(整条路径变绿),这是第 2 条。然后返回,去试别的岔路。
- 15从 5 这条分支回来了,把 5 弹出当前路径,回退到 4,路径缩回 0 → 1 → 4。4 的邻居都试完了,再往上回退。
- 16从 4 这条分支回来了,把 4 弹出当前路径,回退到 1,路径缩回 0 → 1。1 的邻居都试完了,再往上回退。
- 17从 1 这条分支回来了,把 1 弹出当前路径,回退到 0,路径缩回 0。0 还有没试过的邻居,接着试下一个。
- 18从 0 沿边深入到邻居 2:把 2 压进当前路径,现在路径是 0 → 2。继续从 2 往它的邻居走。
- 19从 2 沿边深入到邻居 4:把 4 压进当前路径,现在路径是 0 → 2 → 4。继续从 4 往它的邻居走。
- 20从 4 沿边深入到邻居 5:把 5 压进当前路径,现在路径是 0 → 2 → 4 → 5。它正是终点,下一步就该记一条。
- 21走到了终点 5!当前路径是 0 → 2 → 4 → 5。把它复制一份存进答案(整条路径变绿),这是第 3 条。然后返回,去试别的岔路。
- 22从 5 这条分支回来了,把 5 弹出当前路径,回退到 4,路径缩回 0 → 2 → 4。4 的邻居都试完了,再往上回退。
- 23从 4 这条分支回来了,把 4 弹出当前路径,回退到 2,路径缩回 0 → 2。2 的邻居都试完了,再往上回退。
- 24从 2 这条分支回来了,把 2 弹出当前路径,回退到 0,路径缩回 0。0 的邻居都试完了,再往上回退。
- 25DFS 全部跑完,回溯到最后路径只剩起点 [0](dfs(0) 结束后不再用它)。一共找到 3 条从 0 到 5 的路径:0→1→3→5、0→1→4→5、0→2→4→5。回头看,我们就是一路深入、到终点存一份、回溯换岔路,把每条路都不重不漏地走了一遍。
⚠️ 容易写错的地方
✗ 错：直接把 path 本身存进答案
✓ 对：存一份副本(path[:] / new ArrayList(path))
path 是同一个会被后续 push/pop 改动的对象,直接存进去,最后答案里全部会变成同一条(空的或最后状态)
✗ 错：递归后忘了 pop(不回溯)
✓ 对：dfs(v) 返回后必须 path.pop()
不弹出 v,path 会越积越长、串进别的分支,枚举出错误路径
✗ 错：画蛇添足加 visited
✓ 对：DAG 无环,不用 visited
题目保证无环,同一路径不会重复经过节点;加 visited 反而会漏掉「不同路径共用某节点」的情况(如本例节点 4 被两条路共用)
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
ans = []
path = [0]
target = len(graph) - 1
def dfs(u: int) -> None:
if u == target:
ans.append(path[:])
return
for v in graph[u]:
path.append(v)
dfs(v)
path.pop()
dfs(0)
return ansC++
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> ans;
vector<int> path{0};
dfs(0, graph, path, ans);
return ans;
}
void dfs(int u, vector<vector<int>>& g, vector<int>& path, vector<vector<int>>& ans) {
if (u == (int)g.size() - 1) { ans.push_back(path); return; }
for (int v : g[u]) {
path.push_back(v);
dfs(v, g, path, ans);
path.pop_back();
}
}
};Java
import java.util.*;
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> ans = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>();
path.add(0);
dfs(0, graph, path, ans);
return ans;
}
private void dfs(int u, int[][] graph, ArrayList<Integer> path, List<List<Integer>> ans) {
if (u == graph.length - 1) { ans.add(new ArrayList<>(path)); return; }
for (int v : graph[u]) {
path.add(v);
dfs(v, graph, path, ans);
path.remove(path.size() - 1);
}
}
}复杂度
时间
O(2^n · n)
最坏情况(每个点都能到后面所有点)路径条数可达 2^(n−1) 量级,每条路径长 O(n)、复制也要 O(n);所以由输出规模主导
空间
O(n)
不算答案本身,递归栈深度和 path 长度都是 O(n);DAG 无环,不需要 visited 数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 所有可能路径 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题能用 BFS 吗?+
能。BFS 队列里存的不是单个节点,而是「到目前为止的整条路径」;每次取出一条以 u 结尾的路径,对 u 的每个邻居 v 复制出一条新路径接上 v 再入队,路径以终点结尾就收进答案。逻辑等价,只是用队列层层扩展、空间通常比 DFS 大,因为要同时存很多条半成品路径。
为什么时间复杂度看起来很大却没法更优?+
因为答案本身可能就有指数级条数(例如每个点都连向后面所有点时,路径数是 2 的幂级),光是把它们全部输出就需要这么多时间。这类「枚举所有方案」的题,复杂度被输出规模卡死,没法低于输出量。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 所有可能路径 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。