题目

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.

  1. Example:
  2. Input: [[1,2], [3], [3], []] 
  3. Output: [[0,1,3],[0,2,3]] 
  4. Explanation: The graph looks like this:
  5. 0--->1
  6. |    |
  7. v    v
  8. 2--->3
  9. 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.

题意

在一个有向无环图中找到所有从结点0到结点n-1的路径。

思路

回溯法。

代码实现

Java

  1. class Solution {
  2.     public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         dfs(graph, 0, graph.length - 1, new ArrayList<>(), ans);
  5.         return ans;
  6.     }
  8.     private void dfs(int[][] graph, int u, int v, List<Integer> tmp, List<List<Integer>> ans) {
  9.         tmp.add(u);
  11.         if (u == v) {
  12.             ans.add(new ArrayList<>(tmp));
  13.         } else {
  14.             for (int i = 0; i < graph[u].length; i++) {
  15.                 dfs(graph, graph[u][i], v, tmp, ans);
  16.             }
  17.         }
  19.         tmp.remove(tmp.size() - 1);
  20.     }
  21. }