Clone a Graph

Clone a graph. Input is a Node pointer. Return the Node pointer of the cloned graph.

Assume that a graph is represented as,

Java语言: GraphNode

1 public class GraphNode {
2     int value;
3     ArrayList<GraphNode> neighbors;
4     public GraphNode(int value)
5     {
6         this.value=value;
7         neighbors=new ArrayList<GraphNode>();
8     }
9 }

This question can be done by both BFS and DFS. Let's look at BFS first. Remember to use a hash table to record the nodes you have already copied.

Java语言: CloneAGraph

01 public GraphNode cloneBFS(GraphNode g)
02 {
03     //This hash table maps an original node to its copy in the new graph
04     Hashtable<GraphNode,GraphNode> copy_table=new Hashtable<GraphNode,GraphNode>();
05     //Queue of BFS
06     LinkedList<GraphNode> queue=new LinkedList<GraphNode>();
07     //copy the very first node
08     GraphNode g_copy=new GraphNode(g.value);
09     //put already copied node to the hash table
10     copy_table.put(g, g_copy);  
11     //start BFS traversal
12     queue.add(g);
13     while(queue.size()!=0)
14     {
15         GraphNode curr_node=queue.remove();          
16         for(GraphNode neighbor:curr_node.neighbors)
17         {  
18             //neighbor node not copied before, can be seen as a child node
19             if(!copy_table.containsKey(neighbor))
20             {  
21                 //clone this neighbor
22                 GraphNode child_copy=new GraphNode(neighbor.value);
23               
24                 //get the copy of the current node
25                 //assign the child node copy to the
26                 //current node copy's adjacent list
27                 GraphNode curr_node_copy=copy_table.get(curr_node);
28                 curr_node_copy.neighbors.add(child_copy);
29               
30                 //update the copy table by inserting
31                 //the new original and copy pairs
32                 copy_table.put(neighbor, child_copy);
33                 queue.add(neighbor);
34             }
35             else //met a parent node
36             {  
37                 //get the copy of the parent node
38                 GraphNode parent_copy=copy_table.get(neighbor);
39                 //get the copy of the current node itself
40                 GraphNode curr_node_copy=copy_table.get(curr_node);
41                 //add the parent node copy to the
42                 //current node copy's adjacent list
43                 curr_node_copy.neighbors.add(parent_copy);
44             }
45         }
46     }
47     return g_copy;
48 }