Graph Cloning

Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg Facebook Google Microsoft Qualcomm Qualtrics Twitter Uber
Breadth First Search Depth First Search GraphViews 1084

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:

A sample graph
A sample graph

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

A deep copy of the graph
A deep copy of the graph

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

Image showing the process for Graph illustrated
Image showing the process for Graph illustrated

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
     Queue<Node>store=new LinkedList<Node>();
     //Adding the root node
     store.add(node);
     //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));
             store.add(neigh);   
             }
             //Adding the neighbours to the duplicate nodes
             hash.get(cur).neighbors.add(hash.get(neigh));
         }
     }
     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;
     //Adding the root node
     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)
    • Add neighbours=O(1) operation
  • Summing up the complexity=V*(O(1)+O(Adj)+O(1))
  • Which boils down to O(V)+O(V*Adj)
  • Making the time complexity=O(V+E)
  • The space complexity is O(n) as all we needed was a queue

References

Translate »