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:
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:
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.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i (i.e., there will be no self-loops).graph[i] are unique.The Depth First Search (DFS) approach uses a recursive function to explore all paths from the source node to the target node by traversing each possible node in a depth-first manner. This involves exploring as far as possible along each branch before backing up.
This C solution implements a depth-first search (DFS) recursively. The function "dfs" is called with each node and adds the node to the current path. If the current node is the target node, the path is added to the result. Otherwise, the function is called recursively for each of the node's children. Memory is dynamically allocated for the paths and adjusted for recursion depth.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^n) - since every node could lead to every other node, creating exponential paths.
Space Complexity: O(n) - the maximum depth of the recursion, and path storage could be O(n) as well.
The Breadth First Search (BFS) approach uses a queue to explore nodes level by level, tracking each path as it progresses. This is an iterative process that can make finding all possible paths easier to visualize compared to recursive methods like DFS.
This C solution implements Breadth First Search (BFS) using a queue to iteratively explore the graph level by level. Paths are stored in the queue and processed in FIFO order. New paths are generated for each child node, leading to either an extension to the path or storing the path if it reaches the target node.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^n) - Because each node may lead to different paths creating an exponential number of routes.
Space Complexity: O(2^n) - Required for holding all potential paths in the queue.
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) Approach | Time Complexity: O(2^n) - since every node could lead to every other node, creating exponential paths. |
| Breadth First Search (BFS) Approach | Time Complexity: O(2^n) - Because each node may lead to different paths creating an exponential number of routes. |
Graph Coding Question - All Paths From Source To Target (LeetCode) • AlgosWithMichael • 41,042 views views
Watch 9 more video solutions →Practice All Paths From Source to Target with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor