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.
1var allPathsSourceTarget = function(graph) {
2 const result = [];
3 const dfs = (node, path) => {
4 path.push(node);
5 if (node === graph.length - 1) {
6 result.push([...path]);
7 } else {
8 for (const next of graph[node]) {
9 dfs(next, path);
10 }
11 }
12 path.pop();
13 };
14 dfs(0, []);
15 return result;
16};This JavaScript solution uses a recursive function dfs to explore each node path. From the source node, the function attempts to reach the target node, adding each path found to the results and ensuring only valid paths are stored by checking the current node against the target.
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.
#include <queue>
using namespace std;
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> result;
queue<vector<int>> q;
q.push({0});
while (!q.empty()) {
vector<int> path = q.front();
q.pop();
int lastNode = path.back();
if (lastNode == graph.size() - 1) {
result.push_back(path);
} else {
for (int next : graph[lastNode]) {
vector<int> newPath = path;
newPath.push_back(next);
q.push(newPath);
}
}
}
return result;
}In C++, the Breadth First Search (BFS) is accomplished using a queue to manage paths iteratively. For each path dequeued, we check if it reaches the target. If so, it's appended to the results. Otherwise, it generates new paths by expanding with potential next nodes.