# Graph Cloning

Difficulty Level Medium
Breadth First Search Depth First Search GraphViews 712

## What is Graph Cloning?

Today we have with us a reference to an undirected graph. What do we have to do? Returning a deep copy of the provided graph.

Let us look at the structure:

The Class Node:

It consists of the data value and the neighbors associated with each object of this class. There are a few methods as well to create objects/new nodes accordingly.

```class Node {
public int val;
public List<Node> neighbors;

public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}

public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}

public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
```

The node given to us will always be the root node. Returning a reference/copy to the root will help us return the clone of the graph we have been provided with.

Sample test case:

Input    :  [[1,2],[2,3],[3,4],[4,5],[1,2]]

Output :  [[1,2],[2,3],[3,4],[4,5],[1,2]]

The clone should look something like

i.e consisting of the copy of the nodes which have the same values.

Disclaimer: Do not return the same graph

## Solution

### Using Breadth-First Search and HashMap

We can traverse through using BFS and maintain a HashMap for keeping a mapping of the original and the clone nodes.

#### Pseudocode

• Create a hashmap
• Add the root node and the copy to the hashmap
• Put the root node to the stack
• Traverse through the neighbours and keep repeating the above process
• Add the neighbours for each node
• Keep repeating the above process until the queue gets empty

For more reference lookup BFS: Breadth-First Search (BFS) for a Graph(Opens in a new browser tab)

Here is a simple image to illustrate the above process

Now that we have got a basic idea of how to do stuff let us get into the code

#### Java Program for Graph Cloning

```class Solution
{
public Node cloneGraph(Node node)
{
if(node==null)
return null;
//Creating a Queue for BFS
//Creating a hashmap of nodes and copies
HashMap<Node,Node>hash=new HashMap<Node,Node>();
hash.put(node,new Node(node.val));
//Firing up the BFS!
while(!store.isEmpty())
{
Node cur=store.poll();
for(Node neigh:cur.neighbors)
{
if(!hash.containsKey(neigh))
{
hash.put(neigh,new Node(neigh.val));
}
//Adding the neighbours to the duplicate nodes
}
}
return(hash.get(node));
}
}```

#### C++ Program for Graph Cloning

```class Solution
{
public:
Node* cloneGraph(Node* node)
{
if(!node)
return NULL;
//Creating a Queue for BFS
queue<Node*>store;
store.push(node);
//Creating a hashmap of nodes and copies
map<Node*,Node*>hash;
hash[node]=new Node(node->val,{});
//Firing up the BFS!
while(!store.empty())
{
Node* cur=store.front();
store.pop();
for(Node* neigh:cur->neighbors)
{
if(hash.count(neigh)==0)
{
hash[neigh]=new Node(neigh->val,{});
store.push(neigh);
}
//Adding the neighbours to the duplicate nodes
hash[cur]->neighbors.push_back(hash[neigh]);
}
}
return(hash[node]);
}
};```
```[[1,2],[2,3],[3,4],[4,5],[1,2]]
```
`[[1,2],[2,3],[3,4],[4,5],[1,2]]`

## Complexity Analysis

Time complexity=O(V+E)

Space complexity=O(n)

V=Number of Vertices

E=Number of Edges

How did the time and space complexity end up to this?

• We have in the code a loop emptying the queue that runs over V times. In the loop
• We remove data from the queue=O(1) operation
• Traverse all the neighbour edges to get the clones=O(Adj)