Last Updated: 25 Jan, 2022

Find if Path Exists in Graph

Easy

Asked in company

Solve now

Problem statement

You are given an undirected graph consisting of ‘N’ nodes from 0 to ‘N’ - 1. You are given a list ‘EDGES’ of size ‘M’, consisting of all the edges of this undirected graph, and two nodes ‘SOURCE’ and ‘DESTINATION’ of this graph. Determine whether there exists a path from node ‘SOURCE’ to node ‘DESTINATION’. In other words, check whether there exists a path from node ‘SOURCE’ to node ‘DESTINATION’ by moving along the edges of the graph.

Note:

The graph has no self-edges, no parallel edges.
The graph may not be connected.

For Example,

If ‘N’ = 7, ‘M’ = 5, ‘SOURCE’ = 1, ‘DESTINATION’ = 5, EDGES = [ [2, 4], [2, 5],[3, 5],[3, 6],[4, 5] ].

Here, you can see that the graph is not connected and there is no way we can reach node 5 from node 1 as they both are in different connected components. Hence, the output is “No”.

Input Format :

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

The first line of each test case consists of four space-separated integers  ‘N’, ‘M’, ‘SOURCE’, ‘DESTINATION’, described in the problem statement.

Then next ‘M’ lines follow in each test case. The ith line consists of two space-separated integers ‘EDGES[i][0]’ and ‘EDGES[i][1]’ representing that there is a undirected edge between nodes ‘EDGES[i][0]’ and ‘EDGES[i][1]’.

Output Format :

For each test case, print the “Yes” if there exists a path from node ‘SOURCE’ to node ‘DESTINATION’ by moving along the edges of the graph, Otherwise, print “No”.

Print a separate line for each test case.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 500
1 <= M <= (N*(N-1)) / 2
0 <= ‘SOURCE’, ‘DESTINATION’ <= N - 1
Time limit: 1 sec

Solve now

Approaches

01 Approach

Let’s first define a function canReach(node, x, adj, vis) where “node” is the current node we are at, ‘x’ is the destination node which we have to find, “adj” is the adjacency list of all the nodes, adjacency list stores all the nodes which are directly connected to the ith node, “vis” is the vector which keeps track of every node whether it has been traversed or not. If vis[node] = 1, means we have traversed this node, otherwise not.

This function returns “true” if ‘x’ is found otherwise it returns false. So, the idea is to start from the source node and try to find ‘x’ over all possible paths. After reaching a certain node we will check whether this node is equal to the ‘x’ or not, if yes then return “true”, otherwise traverse the adjacency list of the current node and call the “canReach” function for the nodes which are not visited yet.

Here is the algorithm:

canReach function:
- If node is equal to ‘x’
  - Return true.
Vis[node] = 1.
Traverse the adjacency list of the current node “node” (say iterator ‘i’)
- If adj[node][i] is not visited
  - if( canReach( adj [node][i], x, adj, vis) ) , if ‘x’ is found
    - Return True.
Return false.

given function:
- Declare a 2-d vector “adj” for storing the adjacency list of all the nodes.
- Declare a vector “vis” for marking nodes visited.
- Create an adjacency list. This can be done by running a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ push EDGES[i][0] in list ADJ[EDGES[i][1]] and EDGES[i][1] in list ADJ[EDGES[i][0]].
- Return canReach(source, destination, adj, vis)

Solve now

02 Approach

Approach:

The idea of this approach is to traverse the graph in level order starting from the “source” node and explore all the neighboring nodes. Then, we will select the nearest node which has not been visited yet and explore all the unexplored nodes. For the implementation of this approach we will be using a data-structure “queue” as we want level order traversal so if a node ‘x' enters before a node “y” in the queue then “x” will be processed before “y”.

We first push the node “source” in the queue then we will do the above-mentioned process until we find the “destination” node or we have traversed the whole component of the graph connected to the “source” node.

Here is the algorithm:

Declare a 2-d vector “adj” for storing the adjacency list of all the nodes.
Declare a vector “vis” for marking nodes visited.
Create an adjacency list. This can be done by running a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ push EDGES[i][0] in list ADJ[EDGES[i][1]] and EDGES[i][1] in list ADJ[EDGES[i][0]].
Declare a queue and initialize it with the “source” node.
Mark “source” node visited, vis[source] = 1.
while(queue is not empty)
Node = queue.front().
Pop node from queue.
if(node is equal to the destination node)
Return true.
Traverse the adjacency list of the current node “node” (say iterator ‘i’)
If adj[node][i] is not visited
Push adj[node][i] in the queue.
Mark adj[node][i] visited.
Return false.

Solve now