797. All-Paths-From-Source-to-Target

difficulty: Medium

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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.

Constraints:

• 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.

Method One

这个题目的难点其实在于对时间复杂度的分析。 一个切入点是，计算总的可能的路径数量，然后每条路径都是 O(N), 相乘就行。 我们从 两个node开始计算，共有1条。 三个node，有2条。 每增加一个新的node,我们都可以把新的node加入之前的路径构成一组新的路径， 因此会增加一倍的新路径。 所以总共的路径数是 1 + 2 + 4 + ... 2^{n - 1} = 2^{n} - 1 条。 因此时间复杂度是 O(2^N * N);

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        /*
        这个题注意由于我们是要 all possible path, 我们不能 mark vertex
        由于又是 acyclic graph 所以不用担心有环，因此不需要写 marked。
        如果是有环的情况，我们要 Mark edge 的
        */
        LinkedList< List<Integer> > stack = new LinkedList<>();
        List<List<Integer>> ans = new LinkedList<>();
        List<Integer> temp = new ArrayList<>();
        temp.add(0);
        stack.push(temp);
        while(!stack.isEmpty()){
            List<Integer> pathSoFar = stack.pop();
            int cur = pathSoFar.get( pathSoFar.size() - 1);
            if( cur == graph.length - 1){
                ans.add(pathSoFar);
            }
            for(int next : graph[cur] ) {
                List<Integer> nextPath = new ArrayList<Integer>(pathSoFar);
                nextPath.add(next);
                stack.push(nextPath);
            }
        }
        return ans;
    }
}
​