Find All Paths In DAG

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
3 upvotes
Asked in companies
AppleCloudera

Problem statement

Given a connected directed acyclic graph having ‘N’ nodes and ‘M’ edges. A matrix ‘edges’ of size M x 2 is given, which represents the ‘M’ edges such that there is an edge directed from node edges[i][0] to node edges[i][1].

You are supposed to find all possible paths from node 0 to node n - 1.

Note 
Nodes are numbered from 0 to N - 1.

The graph given is connected.

Print the path[][] in sorted order i.e path[i] is an array containing the path from 0 to n-1, and path[i] is lexicographically smaller than path[i + 1] then path[i] should appear before path[i + 1].

Assume we have two solutions
S1: A1 B1 C1 D1  
S2: A2 B2 C2 D2

S1 is lexicographically smaller than S2 iff,
A1 < A2 OR
A1 = A2 AND B1 < B2 OR
A1 = A2 AND B1 = B2 AND C1 < C2 OR 
A1 = A2 AND B1 = B2 AND C1 = C2 AND D1 < D2
For Example : 
The following is an example of DAG i.e a directed graph with no cycles in it.

alt text

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.

The first line of each test case contains two integers separated by a single space,‘N’ and ‘M’, where ‘N’  denotes the number of the vertices and ‘M’ denotes the number of edges in the graph.

The next ‘M’ lines of each test case contain two integers ‘X’ and ‘Y’ separated by a single space, here ‘X’ and ’Y’ are the vertices connected by a directed edge from ‘X’ to ‘Y’.
Output Format : 
For each test case, print all possible paths from node 0 to N - 1 in sorted order.

Print the output of each test case on a new line.
Note : 
You don’t need to print anything; It has already been taken care of.
Constraints : 
1 <= T <= 5
2 <= N <= 16
N-1 <= M <= N*(N - 1)/2
0 <= X,Y <= N - 1

Time Limit: 1 sec
Sample Input 1 :
2
6 5
0 1
0 2
2 5
3 4
4 2
5 6
0 1
2 1
1 4
2 4
0 4
3 1
Sample Output 1 :
0 2 5
0 1 4
0 4
Explanation For Sample Output 1:
For the first test case, 
All possible paths from 0 to 5 are:
0 -> 2 -> 5

For the second test case,
All possible paths from 0 to 5 are:
0 -> 1 -> 4
0 -> 4
As the first path appears before so it is printed first and then the second path.

Sample Input 2:

2
4 4
0 1
0 2
0 3
1 2
2 1
0 1
Sample Output 2:
0 3
0 1
Hint

Can you think of some order which would cover the whole graph?

Approaches (1)
Backtracking, DFS

First of all, we know it is a directed acyclic graph, which means we do NOT need to keep track of previously seen nodes to avoid cycles.

 

We start our DFS from vertex 0, traverse for all adjacent vertices and push the current adjacent vertex to the path. After that, we call our DFS from the current adjacent vertex. After this, we remove the last added vertex from the path array.

 

The algorithm is as follows:

 

  • Declare a 2D array ans to store all the paths array from vertex 0 to vertex N - 1.
  • Declare a 2D array adj[][] which represents the given graph constructed via adjacency list.
  • Traverse all the edges in the graph,
    • Let the current edge be directed from x to y.
    • Append y to adj[x].
  • Sort the adjacency list of each node so that the paths obtained are in lexicographically increasing order.
  • Declare a function dfs with parameters node, path[], adj[][], ans[][]. Where node represents the current vertex in the dfs call, path represents the array to store the path from vertex 0 to N - 1, adj represents the given graph constructed via adjacency list and ans is the 2D array to store all the paths.
    • If node == N - 1,
      • Append path to ans.
      • Return.
    • For every adjacent node neighbour to vertex node,
      • Append neighbour to the path, because the neighbour is on the current path from 0 to N - 1.
      • Call dfs(neighbour, path, adj, ans).
      • Remove the vertex neighbour from the path, since we are trying all possible paths we backtrack at this step.
  • Append vertex 0 to path since vertex 0 should be present for every path from 0 to N - 1.
  • Call dfs(0).
  • Return the ans.
Time Complexity

O(N * (2^N)), where N is the number of vertices in the graph.

 

In the worst case, when the given graph is a complete graph i.e for every 'i' there is an edge to 'j' for all j>i, the total number of paths can be of the order of 2^N, and we are exploring all possible paths and exploring each path will take O(N) time. 

 

So the overall time complexity is O(N * (2^N)).

Space Complexity

O(N + M), where N is the number of vertices and M is the number of edges in the graph.

 

Since we are using an array path[] to store the path from 0 to N-1 and the recursive call stack which can grow up to the order of N. Also we are storing the graph in the form of an adjacency list which will take O(M) space. 

 

So, the overall space complexity is O(N+M).

Code Solution
(100% EXP penalty)
Find All Paths In DAG
Full screen
Console