Last Updated: 5 Dec, 2020

Check If Path Exists

Easy

Asked in companies

Solve now

Problem statement

You are given a directed and unweighted graph of 'V' vertices and 'E' edges. All edges are given in a 2-dimensional array ‘Edges’ in which ‘Edges[i][0]’ and ‘Edges[i][1]’ contain an edge. Your task is to check if there exists a path from the vertex 'source' to 'destination'.

For Example:

Consider the number of vertices is 4 and number of edges is 3, and the array of edges is:
[ [0, 1]
  [1, 2] 
  [2, 3] ]
there exists one path between 0 and 2, which is 0 -> 1 -> 2. Hence, the answer is 'true'.

Input format :

The first line of input contains an integer ‘T’, the number of test cases.

The first line of each test case contains two space-separated integers, ‘V’, and ‘E’, which denote the number of vertices and edges in the graph.

The next 'E' lines will denote the edges of the graph where every edge is defined by two space-separated integers 'Edges[i][0]’ and 'Edges[i][1]', which signifies an edge from vertex 'Edges[i][0]’ to vertex 'Edges[i][1]’.

The last line of each test case contains two integers, ‘source’ and ‘destination’.

Output Format :

For each test case, print 'true' if there exists a path from vertex 'source' to 'destination'. Otherwise, print 'false'.

Print the output of each test case in 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 <= V, E <= 10 ^ 5
0 <= Edges[i][0], Edges[i][1] < V
0 <= source, destination < V

Time Limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we are going to use DFS(Depth-first search). We have to make a visited array isVisited which checks whether the particular node number is visited or not.

Initialize all entries of the isVisited array with 0. Now we have to use the recursive function here. The first call is made on the node source, and in the recursive function, mark this node as visited and checks whether it is the node destination or not. If yes, we will return true; otherwise, we will make recursive calls on all its adjacent unvisited nodes. If any of the calls return true then return we will return true, else return false.

Algorithm:

Make a recursive function dfs(source, destination, isVisited, adjacencyList) where the source is the source node. The destination is the destination node, isVisited is the array that checks whether that node is visited or not, and adjacencyList is the adjacency list of Edges. This function returns whether there exists a path between source and destination nodes.
The base condition of this function is if the node which is passed as a source node is the destination node, then returns true.
Mark the node that is passed as an argument as visited. So, set isVisited[source] as 1.
Iterate node through adjacencyList[source].
- We will check if isVisited[node] is equal to 1, then move to the next node.
- We will make the recursive call on every unvisited element. If dfs(node, destination, isVisited, adjacencyList) are equal to true, we will return true. It means there is some path from the source to the destination node.
Return false as we cannot reach the destination node.
Create a visited array isVisited initially filled with 0, of size V.
Create a list adjacencyList of size V.
Iterate index from 0 to E - 1,
- Insert Edges[index][1] in adjacencyList[Edges[index][0]].
Set answer as dfs(source,destination,adjacencyList).
Return answer, which tells whether there exists some path from the source node to the destination node.

Solve now

02 Approach

In this approach, we are going to use BFS(Breadth-first search). We will take a queue that stores the integer corresponding to node number and take a visited array that checks whether that particular node is visited or not till now.

Initialize the isVisited array with all entries equal to 0. We will insert the source node number in the queue and mark it visited by making isVisited[source] as 1. We will iterate till the queue is not empty.

We will delete the front node from the queue. We will Insert the directly connected nodes of the front node that are not visited in the queue. We will mark those node visited by setting them as 1 in the array isVisited.
We will do this until the queue becomes empty or we find the destination node.

If we find the destination node, it means there exists some path, so we will return true otherwise, return false.

Algorithm:

Create a list adjacencyList of size V.
Iterate index from 0 to E - 1,
- Insert Edges[index][1] in adjacencyList[Edges[index][0]].
Create a queue, and a visited array isVisited initially filled with 0, of size V where V is the number of vertices.
Insert the node source in the queue and mark its index in the isVisited array as 1.
Run loop until the queue is not empty.
Set front as the front element of the queue and delete the front element from the queue.
If front is equal to the destination then return true.
Iterate node through adjacencyList[front].
- Check if isVisited[node] is 0.
  - Set isVisited[node] as 1. We will insert the node in the queue.
Return false as node destination is not found.

Solve now