Get Path using BFS

Easy
0/40
Average time to solve is 25m
profile
Contributed by
7 upvotes
Asked in companies
PayPalJosh Technology Group

Problem statement

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 BFS and print the first path that you encountered.

Note: 
Vertices are numbered through 0 to V - 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. Then each testcase follow.

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
Sample Input 1 :
2
4 4
0 1
0 3
1 2
2 3
1 3
6 3
5 3
0 1
3 4
0 3
Sample Output 1 :
true
false
Explanation For Sample Output 1 :

In the first test case, there are two paths from 1 to 3. I.e. 1 -> 2 -> 3 or 1 -> 0 -> 3. So you can print any one of them.


In the second test case, there is no path from 0 to 3. Hence return an empty string.
Sample Input 2 :
2
2 1
0 1
1 0
5 4
0 1
1 2
2 3
3 4
0 4
Sample Output 2 :
true 
true
Hint

Iterate through the graph using BFS and store the parents of every node.

Approaches (1)
Breadth-first search

In this approach, iterate through the whole graph using BFS 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. Create a graph using the given nodes and a queue for storing the nodes to iterate through breadth-first search.
  3. Push v1 to the queue and start Breadth-first search till the queue is not empty.
  4. Iterate through all the connected nodes from the current node.
  5. Update the parent of new nodes.
  6. Push the current element in the queue to iterate all the nodes connected to this node.
  7. After the completion of BFS, 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.
  8. If the final node in the answer list is not v1 return an empty list.
  9. Return answer.
Time Complexity

O(V + E). Where V is the number of nodes and E is the number of edges in the graph.

 

Since we are implementing Breadth-first search which is a linear task, Hence the time complexity is O(V + E).

Space Complexity

O(V), Where V is the number of nodes in the graph.


We are using a list par of size V to store the parents of all the nodes, Hence the space complexity is O(V).

Code Solution
(100% EXP penalty)
Get Path using BFS
Full screen
Console