clone graph algorithm - 10 minutes mock interview

clone graph algorithm

Clone a graph, given a class Node and then ask to implement the function cloneGraph. 

Here is the function:
public Node cloneGraph(Node root)
{
}
given class Node, 

class Node{
  Node p1;
  Node p2;
}

please implement the function to clone graph:

Here are the discussion:
The peer asked if the graph Node should include all neighbors. 

class Node {
   public int value;
   List<Node> neighbors;
}   

I gave my advice. It does not have to be like that. Let us work on a simple graph, 
and see how we should clone the graph:

   1
  / \
 2 - 3
 
 Graph with three vertics (1, 2,3) and with fully connected three edges:
 1 -2 ,  2 -3, 3-1
 
 how this graph is represented in the class Node. 
 and then clone 
 
 For example, 
 Node 1 denoted as e1, which contains two neighbors. We argue that it should not include itself.  
 Try to make life simple. 
 
 e1: e2, e3
 e2: e1, e3
 e3: e1, e2
 
 need to clone the graph:
 
 copyE1: copyE2, copyE3
 copyE2: copyE1, copyE3
 copyE3: copyE1, copyE2
 
 - create extra copy,  just look up, do not create one more time