Clone Graph

Problem Statement

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

1
      / \
     /   \
    0 --- 2
         / \
         \_/

Approach

Since we have to clone the given graph, first thing to remember is each node should be cloned/copied. We cannot assign old references. A simple Breadth First traversal can be performed on the graph to create a clone. DFS can also achieve this goal but we have used BFS here.

We will also main a hash table<Label,UndirectedNode> to keep track of the copies of nodes and to take care of the cyclic graphs. The UndirectedNode in the has table is the copy/clone of the node.

A Queue (FIFO) is maintained to process each node and its neighbors sequentially.

• If the node is null, return null else go to step 2
• Do the following :
• Push the first node to the queue
• Create a copy of this node and store in the hash table<label,copy of node>
• Go through every element in the queue until it is empty and check
• If each neighbor of first node is already in the hashTable that means we have already created its copy . All we need to do is to add it as a neighbor to the first node. Also, it will not be added to the queue because it is already been processed.
• If neighbor is not in hash table,
• Add this neighbor to the queue. Since its encountered first time.
• Create a copy and store in hash table
• Add this to the neighbor list of the first node

Run Time Complexity

The Time complexity for cloning the graph is O(V+E) and thats because we shall be traversing each vertex of the graph from the Queue and then visiting each edge E atleast once.

Code

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    
    Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
    Map<Integer,UndirectedGraphNode> map = new HashMap<Integer,UndirectedGraphNode>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node){
        if(node == null){
            return null;
        }
queue.add(node);
        UndirectedGraphNode nodeToReturn = new UndirectedGraphNode(node.label);
        map.put(nodeToReturn.label,nodeToReturn);
        
        while(queue.size() > 0){
            UndirectedGraphNode head = queue.remove();
            for(UndirectedGraphNode neighbor: head.neighbors){
                if(map.containsKey(neighbor.label)){
                    map.get(head.label).neighbors.add(map.get(neighbor.label));
                }else{
                    queue.add(neighbor);
                    UndirectedGraphNode neighborNodeCopy = new UndirectedGraphNode(neighbor.label);
                    map.put(neighbor.label,neighborNodeCopy);
                    map.get(head.label).neighbors.add(neighborNodeCopy);
                    
                }
            }
        }
        return nodeToReturn;
    }
}

If you like it share, you can follow me on Twitter or share it with people you care!

https://twitter.com/deekshasharma25