Check If Path Exists
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

Question

Check If Path Exists

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

Accepted Answer

The task is to check if there exists a path from a given source vertex to a destination vertex in a directed and unweighted graph.

Read the number of test cases.
For each test case, read the number of vertices and edges.
Read the edges of the graph.
Read the source and destination vertices.
Implement a graph traversal algorithm (e.g., BFS or DFS) to check if a path exists from the source to the destination.
Print 'true' if a path exists, otherwise print 'false'.

Accepted Answer

Depth First Search

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.

Space Complexity: OtherExplanation:

O(V + E) where V is the number of vertices in the graph and E is the number of edges in the graph.

In the worst case, the space complexity O(V + E) is required by the adjacency list. The O(V) space is used for the visited array and recursion stack in the worst case. So, the overall space complexity is O(V + V + E) = O(V + E).

Time Complexity: OtherExplanation:

O(V + E) where V is the number of vertices in the graph and E is the number of edges in the graph.

We are traversing on each vertex and edge only one time. So, the overall time complexity is O(V + E).

Python (3.5)

"""

    Time Complexity : O(V + E) 

    Space Complexity:O(V^2) 

    

    where V is the number of vertices in the graph and E is the number of edges in the graph.

"""



def dfs(source, destination, isVisited, adjacencyList):



    # Base condition to check if we reached at destination

    if(source == destination):

        return True



    # Mark the source node as visited

    isVisited[source] = 1



    for i in range(0, len(adjacencyList[source])):

        

        if(isVisited[adjacencyList[source][i]] == 0):

            

            result = dfs(adjacencyList[source][i], destination, isVisited, adjacencyList)



            # If we get true from any recursive call then return true

            if(result):

                return True



    # Return false as there is no path between source and destination

    return False





def checkPathExists(v, e, source, destination, edges):



    # Array to check if a particular node is visited or not

    isVisited = []



    for i in range(0, v):

        isVisited.append(0)



    # Adjacency list of edges

    adjacencyList = [[] for i in range(v)]



    for index in range(0, e):

        adjacencyList[edges[index][0]].append(edges[index][1])



    answer = dfs(source, destination, isVisited, adjacencyList)

    

    return answer

Java (SE 1.8)


/*
	Time Complexity : O(V + E) 
	Space Complexity:O(V^2) 
	
	where V is the number of vertices in the graph and E is the number of edges in the graph.
*/
import java.util.ArrayList;

public class Solution {

	public static boolean dfs(int source, int destination, int[] isVisited,

			ArrayList> adjacencyList) {

		// Base condition to check if we reached at destination
		if (source == destination) {
			return true;
		}

		// Mark the source node as visited
		isVisited[source] = 1;

		for (int i = 0; i < adjacencyList.get(source).size(); i++) {
			if (isVisited[adjacencyList.get(source).get(i)] == 0) {
				boolean result = dfs(adjacencyList.get(source).get(i), destination, isVisited, adjacencyList);

				// If we get true from any recursive call then return true
				if (result) {
					return true;
				}
			}
		}

		// Return false as there is no path between source and destination
		return false;
	}

	public static boolean checkPathExists(int v, int e, int source, int destination, int[][] edges) {
		// Array to check if a particular node is visited or not
		int[] isVisited = new int[v];

		// Adjacency list of edges
		ArrayList> adjacencyList = new ArrayList<>(v);

		// Initialization
		for (int i = 0; i < v; i++) {
			adjacencyList.add(new ArrayList<>());
		}
		for (int index = 0; index < e; index++) {
			adjacencyList.get(edges[index][0]).add(edges[index][1]);
		}

		boolean answer = dfs(source, destination, isVisited, adjacencyList);

		return answer;
	}

}

C++ (g++ 5.4)

/*

    Time Complexity : O(V + E) 

    Space Complexity:O(V^2) 

    

    where V is the number of vertices in the graph and E is the number of edges in the graph.

*/



bool dfs(int source, int destination, vector &isVisited, vector> &adjacencyList)

{

    // Base condition to check if we reached at destination

    if(source == destination)

    {

        return true;

    }



    // Mark the source node as visited

    isVisited[source] = 1;



    for(int i = 0; i < adjacencyList[source].size(); i++)

    {   

        if(isVisited[adjacencyList[source][i]] == 0)

        {   

            bool result = dfs(adjacencyList[source][i], destination, isVisited, adjacencyList);



            // If we get true from any recursive call then return true

            if(result)

            {

                return true;

            }

        }       

    }

    

    // Return false as there is no path between source and destination

    return false;

}



bool checkPathExists(int v, int e, int source, int destination, vector> &edges)

{

    // Array to check if a particular node is visited or not

    vector isVisited(v, 0);



    // Adjacency list of edges

    vector> adjacencyList(v);



    for(int index = 0; index < e; index++)

    {

        adjacencyList[edges[index][0]].push_back(edges[index][1]);

    }

        

    bool answer = dfs(source, destination, isVisited, adjacencyList);

    

    return answer;

}

Accepted Answer

Breadth First Search

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.

Space Complexity: OtherExplanation:

O(V + E) where V is the number of vertices in the graph and E is the number of edges in the graph.

In the worst case, the space complexity O(V + E) is required by the adjacency list. At most V elements are present in the queue, also visited array is of size V. So, the overall space complexity is O(V + E + V) = O(V + E).

Time Complexity: OtherExplanation:

O(V + E) where V is the number of vertices in the graph and E is the number of edges in the graph.

We are traversing on each vertex and edge only one time. So, the overall time complexity is O(V + E).

Python (3.5)

"""

    Time Complexity : O(V + E) 

    Space Complexity: O(V^2) 

    

    where V is the number of vertices in the graph and E is the number of edges in the graph.

"""



from queue import Queue



def checkPathExists(v, e, source, destination, edges):



    # Adjacency list of edges

    adjacencyList = [[] for i in range(v)] 



    for i in range(0, e):

        adjacencyList[edges[i][0]].append(edges[i][1])



    # Create a queue for BFS

    q = Queue()



    # Array to check if a particular node is visited or not

    isVisited = []



    for i in range(0, v):

        isVisited.append(0)



    q.put(source)

    isVisited[source] = 1



    while(q.empty() == False):



        front = q.get()



        # If we reach at destination

        if(front == destination):

            return True



        for node in adjacencyList[front]:

            

            if(isVisited[node] == 0):

                isVisited[node] = 1

                q.put(node)



    # Return false because we cannot reach destination

    return False

Java (SE 1.8)


import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

/*
	Time Complexity : O(V + E) 
	Space Complexity: O(V^2) 
	
	where V is the number of vertices in the graph and E is the number of edges in the graph.
*/
public class Solution {

	public static boolean checkPathExists(int v, int e, int source, int destination, int[][] edges) {
		// Adjacency list of edges
	    ArrayList>  adjacencyList =new ArrayList<>(v);
		
	    // Initialization
	    for (int i = 0; i < v; i++) {
			adjacencyList.add(new ArrayList<>());
		 }
	    for(int index = 0; index < e; index++)
	    {
	        adjacencyList.get(edges[index][0]).add(edges[index][1]);
	    }

	    // Create a queue for BFS
	    Queue q= new LinkedList<>();

	    // Array to check if a particular node is visited or not
	    int[] isVisited=new int[v];

	    q.add(source);
	    isVisited[source] = 1;

	    while(q.isEmpty() == false)
	    {
	        int front = q.poll();

	        // If we reach at destination
	        if(front == destination)
	        {
	            return true;   
	        }

	        for(int i =0; i < adjacencyList.get(front).size(); i++) 
	        {   
	            int node = adjacencyList.get(front).get(i);

	            if(isVisited[node] == 0)
	            {
	                isVisited[node] = 1;
	                q.add(node);
	            }  
	        }          
	    }
	    
	    // Return false because we cannot reach destination
	    return false;
	}

}

C++ (g++ 5.4)

/*

    Time Complexity : O(V + E) 

    Space Complexity: O(V^2) 

    

    where V is the number of vertices in the graph and E is the number of edges in the graph.

*/



#include 



bool checkPathExists(int v, int e, int source, int destination, vector> &edges)

{

    // Adjacency list of edges

    vector> adjacencyList(v);



    for(int index = 0; index < e; index++)

    {

        adjacencyList[edges[index][0]].push_back(edges[index][1]);

    }



    // Create a queue for BFS

    queue q;



    // Array to check if a particular node is visited or not

    vector isVisited(v, 0);



    q.push(source);

    isVisited[source] = 1;



    while(q.empty() == false)

    {

        int front = q.front();

        q.pop();



        // Check If front is equal to destination

        if(front == destination)

        {

            return true;   

        }



        for(int i =0; i < adjacencyList[front].size(); i++) 

        {   

            int node = adjacencyList[front][i];



            if(isVisited[node] == 0)

            {

                isVisited[node] = 1;

                q.push(node);

            }  

        }          

    }

    

    // Return false because we cannot reach destination

    return false;

}

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:

Input format :

Output Format :

Note:

Constraints:

Top JUSPAY Front end Developer interview questions & answers

Popular interview questions of Front end Developer