友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
797. 所有可能的路径
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j] 存在一条有向边）。
示例 1：
输入：graph = [[1,2],[3],[3],[]] 输出：[[0,1,3],[0,2,3]] 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]] 输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
提示：
-
n == graph.length -
2 <= n <= 15 -
0 <= graph[i][j] < n -
graph[i][j] != i（即不存在自环） -
graph[i]中的所有元素 互不相同 -
保证输入为 有向无环图（DAG）
思路分析
深度优先搜索，或广度优先搜索。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-06-27 21:54:33
*/
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> result = new ArrayList<>();
Queue<List<Integer>> queue = new LinkedList<>();
for (int i : graph[0]) {
if (i == graph.length - 1) {
result.add(List.of(0, i));
} else {
queue.add(List.of(0, i));
}
}
while (!queue.isEmpty()) {
List<Integer> cur = queue.poll();
int[] ints = graph[cur.getLast()];
if (Objects.isNull(ints)) {
continue;
}
for (int n : ints) {
List<Integer> next = new ArrayList<>(cur);
next.add(n);
if (n == graph.length - 1) {
result.add(next);
} else {
queue.offer(next);
}
}
}
return result;
}