一、题目

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。

译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。

点击查看原题
难度级别： 中等

二、思路

1）DFS

由于数据保证是有向无环，那么不用使用visited记录访问过的节点来避免环
直接使用DFS进行遍历，每当能够到达n-1节点就记录下来整条路径即可

三、代码

1）DFS

  1. class Solution {
  2.     List<List<Integer>> ans;
  3.     public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
  4.         Stack<Integer> stack = new Stack();
  5.         ans = new ArrayList();
  6.         stack.push(0);
  7.         dfs(graph, stack, 0);
  8.         return ans;
  9.     }
  10.     public void dfs(int[][] graph, Stack<Integer> stack, int node) {
  11.         if (node == graph.length - 1) {
  12.             List<Integer> temp = new ArrayList(stack);
  13.             ans.add(temp);
  14.             return ;
  15.         }
  16.         for (int i = 0; i < graph[node].length; i++) {
  17.             stack.push(graph[node][i]);
  18.             dfs(graph, stack, graph[node][i]);
  19.             stack.pop();
  20.         }
  21.     }
  22. }

时间复杂度为O(n*2^n)，空间复杂度为O(n)