# Clone graph

Problem is given a graph, clone graph as a new graph. New graph should have same vertices and same edges as original one. This problem is very simple when we have access to values of node, we can just read one value, create a a node with corresponding value, scan all neighbors and then add them one by one to neighbor list. Once node is done, take the next node and go to the list corresponding to value and create new node. Scan all neighbors and add it to new node. No difficulties, very simple solution.

Problem arises when value of node is not available and nodes are not store in array of adjacency lists. Every node contains list of pointers of it’s neighbors. Neighbors of neighbor can be accessed using pointers. This is in fact true representation of graph.

Representation of graph node is as follows:

class graphNode{ public: int value; vector<graphNode *>neighbors; graphNode(int val){ this->;value = val; } };

**Clone a graph : Algorithm**

To clone a graph, first we have to traverse the graph. There are two types of traversals on graph, depth first and breadth first traversal. For this particular problem, let’s take BFS. In BFS, node is visited and all the neighbors of it are visited before any of the child of that node is visited. Take a node and create a corresponding node for clone graph. Again scan all the neighbors from list, and create corresponding nodes and add them to neighbor list of new node. Only thing we need to take care of is that we should not allocate a node which is already allocated. For that we will use hash. Whenever, we allocate a new node corresponding to a node in original graph, we will store that mapping in a hash as

hash[old_node] = new_node;

While scanning nodes of original node, before allocating a new node corresponding to it, check the hash, if that node already has a new node, just put the available new node in the neighbor list. Once, we have traversed all the nodes of original graph, our clone graph will be ready. Below example explains the concept. Let’s say graph given is : To clone it, let’s select a node as starting point. We select as 0 as starting point and allocate a new node for clone graph. State of clone graph and the hash is as follow. For simplification, values are shown here in hash, in real implementation, pointers are used. Now, take neighbors of the node (0) which are 1 and 2. So, we go to node (1), check in hash if that node is already allocated, in this case it is not, so allocate a new node and add pointer of newly allocate node (1) in neighbor list of node (0). Take node (2), it will added to list of node (0) is the same fashion. Now let’s take node (1), it has two neighbors 3 and 2. Node (3) is seen first time hence allocated and added to neighbor list of node (1). When 2 is visited, we check hash table and know that corresponding node has been already allocated for 2 in new graph, hence we will use the same node and add it to neighbor list of node 1 too. After 1, we visit 2, which has neighbor 3. we need node allocated a new node for 2, as it has been already allocated, we will use that from hash table. Neighbor 3 is also already allocated, hence, no allocation is done, those node as taken from hash and added to neighbor list of corresponding node in the new graph.

**Clone graph : Implementation**

graphNode * clone(){ queue<graphNode *>q; q.push(this); map<graphNode *, graphNode *>hashMap; graphNode *graphClone = new graphNode(this->value); hashMap[this] = graphClone; while(!q.empty()){ graphNode *node = q.front(); q.pop(); int n = node->neighbors.size(); for (int i = 0; i < n; i++) { graphNode *neighbor = node->neighbors[i]; /* Node is already node allocated. allocate it and set the mapping. */ if (hashMap[neighbor] == NULL) { graphNode *p = new graphNode(neighbor->value); hashMap[node]->neighbors.push_back(p); hashMap[neighbor] = p; q.push(neighbor); } else { /* a copy already exists, then just put that to neighbor list */ hashMap[node]->neighbors.push_back(hashMap[neighbor]); } } } return graphClone; }

Complexity to **clone a graph from original graph** is O(V + E), where we need to visit each node and edge at least once.

Please share if there is something wrong or missing. If you are interested in contributing to website or have an interview experience to share, please contact us.

Pingback: Amazon interview experience 4 | Algorithms and Me()