{x}
blog image

All Paths From Source to Target

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

Solution Explanation for Finding All Paths From Source to Target

This problem involves finding all possible paths in a directed acyclic graph (DAG) from a source node (0) to a target node (n-1). Two common approaches are Depth-First Search (DFS) and Breadth-First Search (BFS). Both are presented below.

Approach 1: Breadth-First Search (BFS)

BFS explores the graph level by level. We use a queue to store paths. Each element in the queue is a list representing a path from the source to a given node.

  1. Initialization: Start with a queue containing a single path: [0] (the path starting at the source node).
  2. Iteration: While the queue is not empty:
    • Dequeue a path.
    • If the last node in the path is the target node, add the path to the result list.
    • Otherwise, for each neighbor of the last node in the path:
      • Create a new path by extending the current path with the neighbor.
      • Enqueue the new path.
  3. Return: The result list containing all paths from source to target.

Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. In the worst case, we visit every node and edge.

Space Complexity: O(V + E) in the worst case, as the queue and the result list could store all paths, which, in a densely connected graph, would amount to the number of edges and vertices.

Approach 2: Depth-First Search (DFS)

DFS explores the graph by going as deep as possible along each branch before backtracking. It's naturally recursive.

  1. Initialization: Start with a recursive function dfs that takes a path as input. The initial path is [0].
  2. Base Case: If the last node in the path is the target node, add a copy of the path to the result list.
  3. Recursive Step: For each neighbor of the last node in the path:
    • Extend the path with the neighbor.
    • Recursively call dfs with the extended path.
    • Remove the neighbor from the path (backtracking).
  4. Return: The result list containing all paths from source to target.

Time Complexity: O(V + E). Similar to BFS, we visit each node and edge at most once.

Space Complexity: O(V) in the worst case. The space complexity is dominated by the recursion depth, which is at most the length of the longest path in the graph.

Code Examples

The code examples in Python, Java, C++, Go, Rust, JavaScript, and TypeScript demonstrate both BFS and DFS approaches. The BFS solutions are generally considered easier to understand and potentially slightly more efficient for this specific problem due to reduced overhead from recursive function calls. However, DFS solutions using recursion are often more concise. The choice between BFS and DFS depends on personal preference and coding style, both yield the same correct result and have equivalent time complexity.