Print All Paths

Moderate
0/80
Average time to solve is 45m
profile
Contributed by
1 upvote
Asked in companies
SalesforceNagarro Software

Problem statement

You are given a graph with ‘N’ nodes and ‘M’ unidirectional edges. Also you are given two integers ‘S’ and ‘D’ denoting the source and destination. Your task is to find all the paths from ‘S’ to ‘D’.

Note: An ordered set of nodes { S, u1, u2...un, D} is a valid path between ‘S’ and ‘D’, if all nodes along the path are unique.

For example:

For given N = 4, M = 4, S = 0 and D =3.

1

In the above example, the path 0 -> 1 - > 3 is a valid path as all nodes along the path are unique and the path 0 -> 1 -> 2 -> 1 -> 3 is not a valid path because node 1 is visited twice.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains one positive integer ‘T’, denoting the number of test cases, then ‘T’ test cases follows.

The first line of each test case contains two integers ‘N’ and  ‘M’, denoting the number of nodes and the number of edges.

The next ‘M’ lines of each test case contains two space-separated integers ’u’ and ‘v’, denoting the edge between ‘u’ and ‘v’.

The last line of each test case contains two integers ‘S’ and ‘D’ denoting the source and destination.
Output Format: 
The first line of each test case contains an integer ‘N’ , denoting the number of valid paths from ‘S’ to ‘D’.

The next ‘N’ line of each test case contains the all nodes from ‘S’ to ‘D’ along the ‘ith’ path where 1 <= i <= N. 

If there are more than one path then the ith path should be lexicographically smaller than (i + 1) path.

Output of each test case will be printed on a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 5
1 <= M <= 10
0 <= u, v , S, D <= N - 1 

Time Limit: 1 sec.
Sample Input 1:
2
4 4
0 1
1 2
1 3
2 3
0 3
5 3
0 1
1 2
3 4
0 3
Sample Output 1:
2
0 1 2 3 
0 1 3 
0
Explanation of Sample Output1:
In the first test case, the graph like this:

1

As we can observe, there are two valid path
P1 : 0  -> 1 ->  2 ->  3 
P2 : 0  -> 1 ->  3 

Note : Path P2: 0 -> 1 -> 3 is lexicographically larger than P1: 0 -> 1 -> 2 -> 3, so path P1 is printed before path P2.

In the second test case, the graph looks like this:

1

As we can observe, there are two disconnected graphs - {0, 1, 2} and {3, 4}. There is no path between 0 and 3.
Sample Input 2:
2
5 4
0 0
0 1
1 3
4 2
3 0
2 2
0 0
1 1
0 0
Sample Output 2:
1
3 1 0 
1
0
Hint

 Can you use backtracking and try out all possible paths?

Approaches (1)
Backtracking

The idea is very simple: we will perform dfs from a given source node and try out all possible paths using the backtracking concept.

 

The steps are as follows:

Let ‘allAllPaths(n, m, edges, src, des)’ be the function that returns a 2D array that contains all the possible paths.

  • Take the following variables: 2D array ‘Graph’, to store graphs and ‘Visited’ array to mark each node whether it is visited or not.
  • Clear graph, initialize the visited array to false.
  • Run a loop from 0 to 'm' :
    • Add the undirected edge between edges[i] [0] and edges[i][1].
  • Take an 2D array 'allPaths' to store the answer.
  • Take an array 'currPath' to store the current path.
  • Push ‘src’ in ‘currPath’ and mark visited[src] equal to true.
  • Make a dfs(n, allPaths, currPath, src, des, graph, visited) and call the dfs function.
  • Return ‘allPaths’.

 

Description of dfs(n, allPaths, currPath, src, des, graph, visited) function

 

  • If ‘src’ is equal to ‘des’
    • Push ‘currPath’ in ‘allPath’ and return.
  • Run a loop from 0 to ‘n’:
    • If graph[src][i] is equal to 1 and visited[i] == 0.
      • Make visited[i] equal to 1.
      • Push ‘i’ in ‘currPath’ i.e currPath.push_back(i).
      • Recursively call dfs on adjacent nodes ‘i’ i.e dfs(n, ‘allPaths’, ‘currPath’, i, des, graph, visited).
      • Remove the ‘i’th node from currPath i.e currPath.pop_back().
      • Make visited[i] equal to 0.
Time Complexity

 O(N ^ N), where ‘N’ is the number of vertices.

 

The time complexity is exponential. From each vertex there are ‘N’ vertices that can be visited from the current vertex.

Space Complexity

 O(N ^ N), where ‘N’ is the number of vertices.

 

To store the paths ( N ^ N) space is needed. Hence the space complexity is O( N ^ N).

Code Solution
(100% EXP penalty)
Print All Paths
Full screen
Console