1. Initialize an empty list `paths` to store all the valid paths found from source to target.

2. Define a recursive Depth-First Search (DFS) function, say `dfs`, that takes the current `node` and the `currentPath` (a list of nodes visited so far to reach the current node) as input.

3. Inside the `dfs` function:

a. Create a new path list by appending the current `node` to the `currentPath`. Let's call this `newPath`.

b. Check if the current `node` is the target node (`n - 1`, where `n` is the total number of nodes).

i. If it is the target node, it means we've found a complete path. Add `newPath` to the main `paths` list and return from this recursive call.

c. If the current `node` is not the target node, iterate through all `neighbor` nodes accessible from the current `node` (i.e., iterate through `graph[node]`).

i. For each `neighbor`, make a recursive call to `dfs` with the `neighbor` as the new current node and `newPath` as the path taken to reach it (`dfs(neighbor, newPath)`).

4. Start the process by calling the `dfs` function with the source node `0` and an empty initial path (`dfs(0, [])`).

5. After the initial `dfs` call completes, return the `paths` list containing all discovered paths.

**Depth-First Search (DFS)** is a classic graph traversal algorithm characterized by its **"go as deep as possible"** approach when exploring branches of a graph. Starting from the initial vertex, DFS follows a single path as far as possible until it reaches a vertex with no unvisited adjacent nodes, then backtracks to the nearest branching point to continue exploration. This process is implemented using **recursion** or an **explicit stack (iterative method)**, resulting in a **Last-In-First-Out (LIFO)** search order. As a result, DFS can quickly reach deep-level nodes far from the starting point in unweighted graphs.

**Comparison with BFS**:

1. **Search Order**: DFS prioritizes depth-wise exploration, while Breadth-First Search (BFS) expands layer by layer, following a **First-In-First-Out (FIFO)** queue structure.

2. **Use Cases**: DFS is better suited for strongly connected components or backtracking problems (e.g., finding all paths in a maze), whereas BFS excels at finding the shortest path (in unweighted graphs) or exploring neighboring nodes (e.g., friend recommendations in social networks).

**Unique Aspects of DFS**:

- **Incompleteness**: If the graph is infinitely deep or contains cycles (without visited markers), DFS may fail to terminate, whereas BFS always finds the shortest path (in unweighted graphs).

- **"One-path deep-dive"** search style makes it more flexible for backtracking, pruning, or path recording, but it may also miss near-optimal solutions.

In summary, DFS reveals the vertical structure of a graph through its depth-first strategy. Its inherent backtracking mechanism, combined with the natural use of a stack, makes it highly effective for path recording and state-space exploration. However, precautions must be taken to handle cycles and the potential absence of optimal solutions.

1. Initialize an empty list `paths` to store all valid paths found from the source to the target.

2. Create a mutable list `path` to track the current path being explored, initially containing only the source node `0`.

3. Implement a recursive DFS function that explores paths using backtracking:

- Base case: If the current node is the target node (`n-1`), make a copy of the current path and add it to the `paths` list.

- Recursive step: For each neighbor of the current node:

- Add the neighbor to the current path.

- Recursively call the DFS function with this neighbor.

- After the recursive call returns, remove the neighbor from the path (backtrack).

4. Start the DFS from the source node `0`.

5. Return the collected `paths` after the DFS completes.

- Time complexity: `Too complex`.

- Space complexity: `Too complex`.

class Solution:

def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:

self.paths = []

self.graph = graph

self.path = [0] # Important

self.dfs(0)

return self.paths

def dfs(self, node):

if node == len(self.graph) - 1:

self.paths.append(self.path.copy()) # Important

return

for neighbor in self.graph[node]:

self.path.append(neighbor) # Important

self.dfs(neighbor)

self.path.pop() # Important

class Solution {

private List<List<Integer>> paths = new ArrayList<>();

private List<Integer> path = new ArrayList<>(List.of(0)); // Important - start with node 0

private int[][] graph;

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {

this.graph = graph;

dfs(0);

return paths;

}

private void dfs(int node) {

if (node == graph.length - 1) { // Base case

paths.add(new ArrayList<>(path)); // Important - make a copy

return;

}

for (int neighbor : graph[node]) { // Recursive step

path.add(neighbor); // Important

dfs(neighbor);

path.remove(path.size() - 1); // Important - backtrack

}

}

}

class Solution {

public:

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {

_graph = graph;

_path = {0}; // Important - start with node 0

dfs(0);

return _paths;

}

vector<vector<int>> _paths;

vector<vector<int>> _graph;

vector<int> _path;

void dfs(int node) {

if (node == _graph.size() - 1) { // Base case

_paths.push_back(_path); // Important - copy is made automatically

return;

}

for (int neighbor : _graph[node]) { // Recursive step

_path.push_back(neighbor); // Important

dfs(neighbor);

_path.pop_back(); // Important - backtrack

}

}

};

public class Solution

{

private IList<IList<int>> paths = new List<IList<int>>();

private List<int> path = new List<int> { 0 }; // Important - start with node 0

private int[][] graph;

public IList<IList<int>> AllPathsSourceTarget(int[][] graph)

{

this.graph = graph;

Dfs(0);

return paths;

}

private void Dfs(int node)

{

if (node == graph.Length - 1)

{ // Base case

paths.Add(new List<int>(path)); // Important - make a copy

return;

}

foreach (int neighbor in graph[node])

{ // Recursive step

path.Add(neighbor); // Important

Dfs(neighbor);

path.RemoveAt(path.Count - 1); // Important - backtrack

}

}

}

func allPathsSourceTarget(graph [][]int) [][]int {

paths := [][]int{}

path := []int{0} // Important - start with node 0

var dfs func(int)

dfs = func(node int) {

if node == len(graph) - 1 { // Base case

// Important - make a deep copy of the path

paths = append(paths, append([]int(nil), path...))

return

}

for _, neighbor := range graph[node] { // Recursive step

path = append(path, neighbor) // Important

dfs(neighbor)

path = path[:len(path) - 1] // Important - backtrack

}

}

dfs(0)

return paths

}

def all_paths_source_target(graph)

@paths = []

@graph = graph

@path = [0] # Important - start with node 0

dfs(0)

@paths

def dfs(node)

if node == @graph.length - 1 # Base case

@paths << @path.clone # Important - make a copy

return

end

@graph[node].each do |neighbor| # Recursive step

@path << neighbor # Important

dfs(neighbor)

@path.pop # Important - backtrack

end