Get DFS Path

Posted: 22 Jul, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given an undirected graph G(V, E), where ‘V’ is the number of vertices and ‘E’ is the number of edges present in the graph and two integers ‘v1’ and ‘v2’ denoting vertices of the graph, find and print the path from ‘v1’ to ‘v2’ (if exists) in reverse order. Print an empty list if there is no path between ‘v1’ and ‘v2’.

Find the path using DFS and print the first path that you encountered.

Note:
Vertices are numbered through 0 to V-1.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains two integers ‘V’ and ‘E’ denoting the number of vertices and edges in the graph.

The next ‘E’ lines of the test case contain two space-separated integers ‘a’ and ‘b’ denoting that there exists an edge between ‘a’ and ‘b’.

The last line of the test case contains two space-separated integers ‘v1’ and ‘v2’ denoting the starting vertex and ending vertex.
Output Format :
For each test case, print the path from ‘v1’ to ‘v2’ in reverse order.

Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function and return a list of paths.

If there is no path between the vertices return an empty list.If the path is valid then it will print true else it will print false.
Constraints :
1 <= T <= 10
1 <= V <= 1000
1 <= E <= (V * (V - 1)) / 2
0 <= v1, v2 <= V-1


Time Limit: 1sec
Approach 1

 In this approach, iterate through the whole graph and whenever you encounter a new node, update the parent of the new node by the current node.

The steps are as follows :


 

  1. Initialize a list par with -1 to store the parent of nodes.
  2. In the ‘dfs’ function:
    1. Check if the current node is visited or not.
    2. Now iterate through all the nodes connected to the current node.
    3. If the new node is not visited, update the parent of this node as the current node in par and call dfs for the new node.
    4. If the new node is the final node then return true.
    5. Else return false.


 

  1. In the Main Function:
    1. Create a graph using the given nodes.
    2. Call the dfs function starting from v1.
    3. If the dfs function returns false then return an empty list.
    4. Else if the dfs function returns true, iterate in the par array starting from node v2.
    5. If the parent of the current node is -1 then stop the iteration.
    6. Else push the parent of the current node in a list answer and go to the index of the par to find the parent of parent till we get -1.
    7. Return answer.
Try Problem