Last Updated: 25 Jan, 2021

Clone Graph

Moderate

Asked in companies

Solve now

Problem statement

You are given a reference/address of a node in a connected undirected graph containing N nodes and M edges. You are supposed to return a clone of the given graph which is nothing but a deep copy. Each node in the graph contains an integer “data” and an array/list of its neighbours.

The structure of the graphNode class is as follows:

class graphNode 
{  
    public:
        int data;
        vector<graphNode*> neighbours;
}

Note :

1. Nodes are numbered from 1 to N.

2. Your solution will run on multiple test cases. If you are using global variables make sure to clear them.

Input Format :

The first line of input contains an integer 'T' representing the number of the test case. Then the test cases are as follows.

The first line of each test case contains a single integer ‘N’ representing the number of nodes in the graph.

The second line of each test case contains a single integer ‘M’ representing the number of edges. 

The next ‘M’ lines in each test case contain two integers ‘U’ and ‘V’ separated by a single space denoting an undirected edge between nodes U and V.

Output Format :

For each test case, print a single line containing "true" if the graph is cloned correctly otherwise it will print "false".

The output of each test case will be printed 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
2 <= N <= 100000
1 <= M <= min(N(N-1)/2,100000)
1 <= E[i][0], E[i][1] <= N

Where  ‘N’ is the number of nodes in the given graph, ‘M’ denotes the number of edges and ‘E’ denotes the edge matrix.

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

To clone a graph, we will need to traverse it. The approach here is to use BFS graph traversal. To clone a graph, you need to have a copy of each node and you need to avoid copying the same node multiple times. So we need a mapping from an original node to its copy.

The steps are as follows :

We need to keep track of the visited/cloned nodes to avoid making multiple copies of the same node. Hence, a HashMap is required in order to maintain all the nodes which have already been created. Where in the HashMap the key stores the address of the original node and the value stores the address of the cloned node.
Now in order to reach each node and its neighbours, we are creating a queue for BFS traversal and a HashMap which keeps a track of all the nodes which are already created.
Create a new node corresponding to the given reference node and insert that node in the HashMap which marks it as visited.
Push the given reference node into a queue and now keep repeating the below steps until the queue isn’t empty.
Get the front node and pop it from the queue and visit all its neighbours, now check if a new cloned node has already been created for each neighbouring node (check it in the HashMap).
If it wasn’t created, then create a new clone node corresponding to the neighbour node and insert it into the HashMap and also push this node into the queue.
Now add the cloned neighbours to “neighbours” list of the cloned node.
Ultimately when the queue is empty, return the source node of the cloned graph.

Solve now

02 Approach

To clone a graph, we will need to traverse it. The approach here is to use DFS graph traversal. To clone a graph, you need to have a copy of each node and you need to avoid copying the same node multiple times. So we need a mapping from an original node to its copy.

Steps are as follows:

The algorithm starts at a given reference node in the given graph and explores as far as possible along each branch of the current node before backtracking.
Now to keep the track of the visited/cloned nodes, a HashMap is required in order to maintain all the nodes which have already been created. Where in the HashMap the key stores the address of the original node and the value stores the address of the cloned node.
The idea is to start from the starting node and mark the node and move to the adjacent unmarked node and continue this recursively until there is no unmarked adjacent node.
Then backtrack and check for other unmarked nodes and traverse them.
Create a recursive function that takes a node and the Hashmap which contains the copies of the nodes as arguments.
Mark the current node as visited and create a new node for the cloned graph and insert the new node into the HashMap.
Traverse all the adjacent nodes of the current node and for all unmarked nodes call the recursive function with the index of adjacent nodes.
After visiting all neighbouring nodes, insert all the cloned neighbouring nodes into the neighbouring array/list of the current node.

Solve now