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.
1#include <vector>
2
3using namespace std;
4
5void dfs(int node, int n, vector<vector<int>>& graph, vector<int>& path, vector<vector<int>>& results) {
6 path.push_back(node);
7 if (node == n - 1) {
8 results.push_back(path);
9 } else {
10 for (int next : graph[node]) {
11 dfs(next, n, graph, path, results);
12 }
13 }
14 path.pop_back();
15}
16
17vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
18 vector<vector<int>> results;
19 vector<int> path;
20 dfs(0, graph.size(), graph, path, results);
21 return results;
22}The C++ solution uses a helper function 'dfs' along with vectors to perform depth-first search. We start from node 0 and push it onto the current path. If node equals the target, the path is stored as a result. Otherwise, it recursively explores each reachable node from the current node.
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
This C solution implements Breadth First Search (BFS) using a queue to iteratively explore the graph level by level. Paths are stored in the queue and processed in FIFO order. New paths are generated for each child node, leading to either an extension to the path or storing the path if it reaches the target node.