This is the 25th day of my participation in the August Challenge

Leetcode -797- All possible paths

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

Given a directed acyclic graph (DAG) with n nodes, find all the paths from node 0 to node n-1 and print them (no specific order required).

The i-th element of a two-dimensional array represents the next nodes that node I can reach in the directed graph, empty means there is no next node.

A directed graph is a directed graph, meaning that a→ B you cannot go from B to A.

Example 1:

Input: graph = [[1, 2], [3], [3], []] output: [,1,3 [0], [0, 2, 3]] : there are two paths 0 - > 1 - > 3 and 0 - > 2 - > 3Copy the code

Example 2:

Input: graph = [,3,1 [4], [3, 4-trichlorobenzene], [3], [4], []] output: [[0, 4], [0, 3], [0,1,3,4], [0,1,2,3,4], [0,1,4]]Copy the code

Example 3:

Graph = [[1],[]] output: [0,1]]Copy the code

Example 4:

Input: graph = [[1, 2, 3], [2], [3], []] output: [,1,2,3 [0], [0, 2, 3], [0, 3]]Copy the code

Example 5:

Input: graph = [[1, 3], [2], [3], []] output: [,1,2,3 [0], [0, 3]]Copy the code

Tip:

  • n == graph.length
  • 2 <= n <= 15
  • 0 <= graph[i][j] < n
  • graph[i][j] ! = I (i.e., there is no self-loop)
  • All elements in graph[I] are different
  • Ensure the input is directed acyclic graph (DAG)

Related Topics

  • Depth-first search
  • Breadth-first search
  • figure
  • back
  • 👍 👎 0 154

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: DFS+ violence

  • There are no special restrictions on this question overall or very good to do DFS search, right
  • DFS traversal
List<List<Integer>> res = new ArrayList<>();
int[][] g;
int n;
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    g = graph;
    n = graph.length;
    List<Integer> list = new ArrayList<>();
    dfs(list, 0);
    return res;
}
public void dfs(List<Integer> list, int num) {
    list.add(num);
    if (num == n - 1) {
        res.add(list);
        return;
    }
    for (int temp: g[num]
         ) {
        List<Integer> tempList = newArrayList<>(list); dfs(tempList,temp); }}Copy the code
  • Time complexity
    O ( n ∗ 2 n ) O(n*2^{n})
  • Spatial complexity
    O ( n ∗ 2 n ) O(n*2^{n})

Idea 2: BFS

  • No doubt you can also traverse with a BFS search
  • You need to define a temporary path record of the previously traversed state to get the full path
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    int n = graph.length;
    Queue<List<Integer>> q = new LinkedList<>();
    q.add(new ArrayList<Integer>() {{
        add(0);
    }});
    List<List<Integer>> res = new ArrayList<>();
    while(! q.isEmpty()) { List<Integer> poll = q.poll();int temp = poll.get(poll.size() - 1);
        if (temp == n - 1) {
            res.add(poll);
        } else {
            for (int val: graph[temp]
                 ) {
                List<Integer> newList = newArrayList<>(poll); newList.add(val); q.add(newList); }}}return res;
}
Copy the code
  • Time complexity
    O ( n ∗ 2 n ) O(n*2^{n})
  • Spatial complexity
    O ( n ∗ 2 n ) O(n*2^{n})

Idea 3: DFS + memory search

  • In fact, this problem memorized search code complexity is disgusting
  • It feels like it can or can’t be used
  • Define a map to record all states of each node
  • Returns the map node for the final N-1 record
  • Insert the head node by **list.add(index,num)**
  • The state of aftereffect is recorded
  • That is, the last node is searched first, and then the first node is inserted layer by layer
  • Finally return res
int[][] g;
int n;
Map<Integer,List<List<Integer>>> cache = new HashMap<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    g = graph;
    n = graph.length;
    List<Integer> list = new ArrayList<>();
    return dfs(0);
}
public List<List<Integer>> dfs( int num) {
    if (cache.containsKey(num)){
        return cache.get(num);
    }
    List<List<Integer>> res = new ArrayList<>();
    if (num == n-1){
        List<Integer> cur = newArrayList<Integer>(){{add(num); }}; res.add(cur); }else{
        for (int temp: g[num]
        ) {
            for (List<Integer> next: dfs(temp)
                 ) {
                List<Integer> cur = new ArrayList<>(next);
                cur.add(0,num);
                res.add(cur);
            }
        }
    }
    cache.put(num,res);
    return res;
}
Copy the code
  • Time complexity
    O ( n ∗ 2 n ) O(n*2^{n})
  • Spatial complexity
    O ( n ∗ 2 n ) O(n*2^{n})