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;`

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.