📉 所有可能的路径
📝 题目描述
给你一个有n个节点的有向无环图（DAG），请你找出所有从节点0到节点n-1的路径并输出（不要求按特定顺序）。
graph[i]是一个从节点i可以访问的所有节点的列表（即从节点i到节点graph[i][j]存在一条有向边）。
📋 代码模板
java
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
}
}typescript
function allPathsSourceTarget(graph: number[][]): number[][] {
}💡 提示
（即不存在自环） 中的所有元素互不相同 - 保证输入为有向无环图（DAG）
🚀 示例
🖊️ 题解
DFS
可惜没有如果
java
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> paths = new ArrayList<>();
dfs(graph, paths, new ArrayList<>(), 0);
return paths;
}
private void dfs(int[][] graph, List<List<Integer>> paths, List<Integer> path, int i) {
path.add(i);
if (i == graph.length - 1) {
paths.add(new ArrayList<>(path));
path.remove(path.size() - 1);
return;
}
for (int next : graph[i]) {
dfs(graph, paths, path, next);
}
path.remove(path.size() - 1);
}
}typescript
function allPathsSourceTarget(graph: number[][]): number[][] {
const paths: number[][] = [];
dfs(graph, paths, [], 0);
return paths;
}
function dfs(graph: number[][], paths: number[][], path: number[], i: number): void {
path.push(i);
if (i == graph.length - 1) {
paths.push([...path]);
path.pop();
return;
}
for (const next of graph[i]) {
dfs(graph, paths, path, next);
}
path.pop();
}BFS
如果没有
java
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
int n = graph.length;
Queue<List<Integer>> queue = new LinkedList<>();
List<Integer> startPath = new ArrayList<>();
startPath.add(0);
queue.offer(startPath);
List<List<Integer>> paths = new ArrayList<>();
while (!queue.isEmpty()) {
List<Integer> originalPath = queue.poll();
int i = originalPath.get(originalPath.size() - 1);
if (i == n - 1) {
paths.add(originalPath);
continue;
}
for (int next : graph[i]) {
List<Integer> path = new ArrayList<>(originalPath);
path.add(next);
queue.offer(path);
}
}
return paths;
}
}typescript
function allPathsSourceTarget(graph: number[][]): number[][] {
const n = graph.length;
const queue: number[][] = [];
queue.push([0]);
const paths: number[][] = [];
while (queue.length > 0) {
const originalPath: number[] = queue.shift()!;
const i = originalPath[originalPath.length - 1];
if (i == n - 1) {
paths.push(originalPath);
continue;
}
for (const next of graph[i]) {
const path: number[] = [...originalPath];
path.push(next);
queue.push(path);
}
}
return paths;
}