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.
1using System.Collections.Generic;
2
3public class Solution {
4 public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
5 var results = new List<IList<int>>();
6 var path = new List<int>();
7 DFS(0, graph, path, results);
8 return results;
9 }
10
11 private void DFS(int node, int[][] graph, List<int> path, List<IList<int>> results) {
12 path.Add(node);
13 if (node == graph.Length - 1) {
14 results.Add(new List<int>(path));
15 } else {
16 foreach (var next in graph[node]) {
17 DFS(next, graph, path, results);
18 }
19 }
20 path.RemoveAt(path.Count - 1);
21 }
22}This C# solution uses a depth-first search to explore all paths. The DFS function recursively visits each node, adding it to the current path, and if the target is reached, appending the path to the results list.
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
public class Solution {
public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
var results = new List<IList<int>>();
var queue = new Queue<List<int>>();
queue.Enqueue(new List<int> {0});
while (queue.Count > 0) {
var path = queue.Dequeue();
int lastNode = path[path.Count - 1];
if (lastNode == graph.Length - 1) {
results.Add(new List<int>(path));
} else {
foreach (var next in graph[lastNode]) {
var newPath = new List<int>(path) {next};
queue.Enqueue(newPath);
}
}
}
return results;
}
}For the C# BFS approach, paths are managed in a queue, processing them level by level. Each path dequeued checks the end node: if it's the target, the path is recorded. Otherwise, it explores connecting nodes to build further paths.