05 August 2008
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.
The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).
Example 1:
Input: graph = [[1,2],[3],[3],[]] Output: [[0,1,3],[0,2,3]] Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3. Example 2:
Input: graph = [[4,3,1],[3,2,4],[3],[4],[]] Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]] Example 3:
Input: graph = [[1],[]] Output: [[0,1]] Example 4:
Input: graph = [[1,2,3],[2],[3],[]] Output: [[0,1,2,3],[0,2,3],[0,3]] Example 5:
Input: graph = [[1,3],[2],[3],[]] Output: [[0,1,2,3],[0,3]]
Constraints:
1
2
3
4
5
6
n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i (i.e., there will be no self-loops).
All the elements of graph[i] are unique.
The input graph is guaranteed to be a DAG.
找路径的题目一般用DFS，BFS存储路径不太方便
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
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> results = new ArrayList<>();
if (graph == null || graph.length == 0 || graph[0].length == 0) {
return results;
}
// 初始值
ArrayList<Integer> oneResult = new ArrayList<>();
oneResult.add(0);
// 用一个index来表示是否到达graph[i][j]
dfs(graph, 0, results, oneResult);
return results;
}
private void dfs(int[][] graph, int index, List<List<Integer>> results, List<Integer> oneResult) {
if (index == graph.length - 1) {
results.add(new ArrayList<>(oneResult));
return;
}
for (int currNode : graph[index]) { // 邻接矩阵中的每一行
oneResult.add(currNode);
dfs(graph, currNode, results, oneResult);
oneResult.remove(oneResult.size() - 1); // 回溯
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
ArrayList<Integer> temp=new ArrayList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
ArrayList<List<Integer>> result=new ArrayList<>();
temp.add(0);
backtracking(0,graph,result);
return result;
}
void backtracking(int current,int graph[][],ArrayList<List<Integer>> res){
if(current==graph.length-1){
res.add((List<Integer>)temp.clone());
return;
}
for(int i:graph[current]){
temp.add(i);
backtracking(i,graph,res);
temp.remove(temp.size()-1);
}
}
}