Categories: Graph/DFS

Level: Medium

Introduction: (Basic + Advanced + Interview Edition) 
Learning Algorithms from LeetCode + Interview Success Guide 
(Regular price: 3591 NTD, Discounted price until 2023/06/30 23:59)
https://hiskio.com/bundles/eCP23B397?s=tc

(Regular price: 3990 NTD, Valid for a long term) 
https://bit.ly/lc2022all

Please help me click on the “SHOW EMBED” below and give it 5 likes~ If you like it, you can also give me a round of applause~ 
(Liking doesn’t cost anything, thank you for supporting my writing~)

Question

Given a directed acyclic graph (DAG ) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order .

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Example 1

1
2
3

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2

1
2

Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Constraints

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i (i.e., there will be no self-loops).
• All the elements of graph[i] are unique .
• The input graph is guaranteed to be a ** DAG**.

Analysis/Approach: 
Given a directed acyclic graph (DAG) with n nodes labeled from 0 to n — 1, we need to find all possible paths from node 0 to node n — 1 and return them in any order.

The graph is represented in the following way: graph[i] represents a list of nodes that can be visited from node i. (Directly visiting means there is a directed edge from node i to graph[i][j].)

Let’s talk about graphs in this article. As mentioned in Article 115 , in a graph with directionality (a -> b and b -> a are considered different edges), it is called a directed graph . If a directed graph does not have cycles (a cycle means there is a path starting from a point a and ending at a, forming a loop), it is called a ** directed acyclic graph**, abbreviated as ** DAG**.

Since the problem guarantees that the graph is a DAG, it is impossible to return to the same node from any starting node, and it is also impossible to backtrack, meaning there are no duplicates in the paths.

Let’s try to outline the steps to find the paths:

1. Start from i = 0 and examine the connections in graph[i] . For example, in Example 1, node 0 connects to nodes 1 and 2, so there are two paths: 0->1 and 0->2.
2. For the path 0->1, we need to check the connections from node 1. It is connected only to node 3, which happens to be the last node in this graph. Therefore, we have found one valid path: 0->1->3.
3. Similarly, for the path 0->2, it only has one connection: 0->2->3.

Therefore, for this problem, we can use DFS starting from node 0 and recursively explore the graph. Along the way, we need to keep track of the current path at each step. Whenever we reach the destination node, we add that path to the result list. Finally, we return the entire result.

The steps for solving this problem are as follows:

1. Initialize a list called res to store the resulting paths.
2. Define a function dfs with parameters (i, path), where i is the current node and path is the path taken to reach node i (including i).
3. Inside the function, first check if i is equal to the length of the graph minus 1. If true, it means we have reached node n-1, and this path is one of the answers. Add it to res.
4. If the previous check fails, it means we need to continue exploring. Iterate through the next node nxt in graph[i] and recursively call dfs with nxt and the updated path (path + nxt).
5. Start the recursion by calling dfs with (0, [0]).
6. After Step 5 is completed, return res.

Based on this, the code can be written as follows:

Java

In Java, the res list is obviously two-dimensional, so we can use an ArrayList to store the paths. In the helper (or dfs) function, since we cannot use nested functions like in Python, we need to include graph, i, path, and res as parameters. Since the path is reused in each recursion, we use backtracking to keep track of the path. In each call to the helper function, we add the current node i to the path (path.add(i)), and remember to remove it (path.remove(path.size() — 1)) before exiting.

One important thing to note is that when adding paths to res, ArrayList is a reference-based structure, meaning it doesn’t create a copy of the path. Therefore, when adding to res, we need to use new ArrayList(path) to create a copy. Otherwise, when we backtrack, it will affect the results in res.

Python

In Python, we can use nested functions, so we don’t need to include res and graph as parameters, which makes the code cleaner. When performing dfs, we can directly create a new list using path + [nxt] . This way, we don’t need to deal with backtracking, and we can directly append path to res without making a separate copy. (Since path + [nxt] creates a new list already.)

Potential Interview Questions:
“What are the time and space complexities?” (O(V * 2^V), as each path has a maximum complexity of O(V), and there can be up to O(2^V) paths.)

Similar and Extended Topics:
Special thanks to suggestions/corrections from viewers:
(Welcome to provide feedback to help with corrections~)

Learn Algorithms from LeetCode — See you next time!

Want to see more problems? 
Feel free to check out Article 0 for the topic you want!

Also, follow our Facebook page for notifications on new articles:
Learn with Desolve