### 题目

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, …, graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:

Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.


Note:

• The number of nodes in the graph will be in the range [2, 15].
• You can print different paths in any order, but you should keep the order of nodes inside one path.

### 广度优先（BFS）

        3
/   \
1     2


        3
/   \
1     2
|     |
0     0


#### 代码

class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
int[][] edgesTable = statistic(graph);
while (!bfsQueue.isEmpty()) {
int size = bfsQueue.size();
for (int i = 0; i < size; i++) {
List<Integer> path = bfsQueue.remove(0);
for (int pre : pres) {
if (pre == -1) break;
if (pre == 0) {
} else {
}
}
}
}
return outPut;
}

private int[][] statistic(int[][] graph) {
int[][] edgesTable = new int[graph.length][15];
for (int[] edge : edgesTable) Arrays.fill(edge, -1);
int[] ps = new int[graph.length];
for (int i = 0; i < graph.length; i++) {
int[] arr = graph[i];
for (int j = 0; j < arr.length; j++) {
int to = arr[j];
edgesTable[to][ps[to]++] = i;
}
}
return edgesTable;
}
}


### 深度优先（DFS）

#### 代码

class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
localGraph = graph;
dfs(new LinkedList<Integer>(Arrays.asList(new Integer[]{0})), 0, graph.length - 1);
return res;
}

int[][] localGraph;
List<List<Integer>> res;

private void dfs(List<Integer> path, int node, int target) {
if (node == target) {