All Paths From Source to Target
Problem Description
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).- All the elements of
graph[i]are unique. - The input graph is guaranteed to be a DAG.
Solve it on LeetCode
Approaches
1. DFS Backtracking
Intuition:
The problem is essentially asking for all paths from node 0 to node n-1 in a Directed Acyclic Graph (DAG). DFS (Depth First Search) is well-suited for exploring all possibilities in the graph. By using a backtracking approach, we can explore each path from the source to the target and backtrack once we reach the end to explore alternative paths.
Steps:
- Start DFS from node
0. Explore each path by recursively visiting each node's neighbors. - Maintain a path list and whenever a node is visited, append it to the path.
- If the current node is the target node
n-1, add a copy of the path to the result list. - Backtrack by removing the node from the path list before exploring other neighbors.
- Return all paths found once DFS exploration is complete.
Code:
- Time Complexity: O(2^n * n), because in the worst case, there can be
2^npaths, and each path can be of lengthn. - Space Complexity: O(n), the space used by the recursion stack.
2. BFS Using a Queue
Intuition:
You can also solve this problem using BFS. The goal of BFS is to explore all neighbors at the present depth before moving on to nodes at the next depth level. By storing paths in the queue, at each step, when you explore a node, you construct and enqueue new paths adding each of the node's neighbors.
Steps:
- Initialize a queue and add the initial path starting from node
0. - While the queue is not empty, pop paths from the queue.
- Extend each path by appending each of the current node's neighbors and enqueue the new path.
- If a path reaches the target node
n-1, add it to the results. - Continue until all paths are explored.
Code:
- Time Complexity: O(2^n * n), similar to DFS, as you are exploring every possible path.
- Space Complexity: O(2^n * n), for storing all paths in the queue.