Find All Paths From Source to Target - Graph

Problem Statement

Given a directed acyclic graph (DAG), find all paths from the source node (node 0) to the target node (the last node). The graph is represented as an adjacency list where graph[i] is a list of all nodes i can directly reach.

Example

Input:

const graph = [[1, 2], [3], [3], []];

Output:

[
  [0, 1, 3],
  [0, 2, 3]
]

Function Declaration:

function allPathsSourceTarget(graph) {
  // Your implementation goes here
}

---

Short, Easy-to-Remember Solution/Approach

1. Start from the source node (node 0).

2. Use a backtracking function to explore all paths:

   • Add the current node to the current path.

   • If the current node is the target node, add the current path to the list of all paths.

   • Recursively explore all nodes that can be reached from the current node.

   • Backtrack by removing the current node from the path.

Solution in JavaScript with Code Commenting

Here's the complete code with comments explaining each step:

function allPathsSourceTarget(graph) {
  const target = graph.length - 1;
  const allPaths = [];

  function backtrack(currentNode, path) {
    // Add the current node to the path
    path.push(currentNode);

    // If the current node is the target, add the path to all paths
    if (currentNode === target) {
      allPaths.push([...path]);
    } else {
      // Explore all neighbors
      for (const neighbor of graph[currentNode]) {
        backtrack(neighbor, path);
      }
    }

    // Backtrack by removing the current node from the path
    path.pop();
  }

  // Start backtracking from the source node (node 0)
  backtrack(0, []);

  return allPaths;
}

// Example usage:
const graph = [[1, 2], [3], [3], []];
console.log(allPathsSourceTarget(graph)); // Output: [ [0, 1, 3], [0, 2, 3] ]

Explanation of the Solution in Simple Terms

Explanation for a 10-year-old: Imagine you are trying to find all possible ways to go from your house (node 0) to a friend's house (the last node). You have a map that tells you which places you can go to from each place. You start at your house and try all possible paths, writing down each path you take. If you reach your friend's house, you remember that path. If a path doesn't work, you go back and try a different way. In the end, you have all the ways to get from your house to your friend's house.

Code Explanation in Pointers

1. Initialize target: Define the target node as the last node in the graph.

2. Define backtrack function: Create a helper function to explore paths.

   • Add current node: Add the current node to the current path.

   • Check for target: If the current node is the target, add the current path to all paths.

   • Explore neighbors: Recursively explore all nodes reachable from the current node.

   • Backtrack: Remove the current node from the path.

3. Start from source: Call the backtracking function starting from the source node (node 0).

4. Return paths: Return the list of all found paths.

Complexity Analysis

• Time Complexity: O(2^n * n), where n is the number of nodes in the graph. This is because in the worst case, there can be an exponential number of paths in a graph.

• Space Complexity: O(n), due to the recursion stack and path storage.

---