Problem

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    v2--->3There 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].

Solution - DFS

class Solution {    public List
    
     
      > allPathsSourceTarget(int[][] graph) {        List
      
       
        > res = new ArrayList<>();        List
        
          temp = new ArrayList<>();        int firstNode = 0;        temp.add(firstNode);        dfs(graph, firstNode, temp, res);        return res;    }        private void dfs(int[][] graph, int node, List
         
           temp, List
          
           
            > res) { if (node == graph.length-1) { res.add(new ArrayList<>(temp)); return; } for (int neighbor: graph[node]) { temp.add(neighbor); dfs(graph, neighbor, temp, res); temp.remove(temp.size()-1); } }}
           
          
         
        
       
      
     
    

Solution - BFS

class Solution {    public List
    
     
      > allPathsSourceTarget(int[][] graph) {        int n = graph.length;        List
      
       
        > res = new ArrayList<>();        Deque
        
         
          > queue = new ArrayDeque<>(); queue.offer(Arrays.asList(0)); while (!queue.isEmpty()) { List
          
            cur = queue.poll(); int size = cur.size(); if (cur.get(size-1) == n-1) { res.add(cur); continue; } for (int node: graph[cur.get(size-1)]) { List
           
             next = new ArrayList<>(cur); next.add(node); queue.offer(next); } } return res; }}