Last Updated: 7 Dec, 2020

Print All Paths

Moderate

Asked in companies

Solve now

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.

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.

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.

Solve now

Approaches

01 Approach

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.

Solve now