Sponsored
Sponsored
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.
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.
1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
5 public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
6 List<List<Integer>> results = new ArrayList<>();
7 List<Integer> path = new ArrayList<>();
8 dfs(0, graph, path, results);
9 return results;
10 }
11
12 private void dfs(int node, int[][] graph, List<Integer> path, List<List<Integer>> results) {
13 path.add(node);
14 if (node == graph.length - 1) {
15 results.add(new ArrayList<>(path));
16 } else {
17 for (int next : graph[node]) {
18 dfs(next, graph, path, results);
19 }
20 }
21 path.remove(path.size() - 1);
22 }
23}This Java solution uses a recursive depth-first search. The dfs method is responsible for adding the current node to the path and traversing each valid node path. If the target node is reached, the path is added to the results.
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.
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.
1
The Java solution utilizes a queue to systematically explore each potential path starting from the source. As paths are dequeued, if their terminal node is the target, they're stored. Otherwise, paths are extended to explore further nodes iteratively.