133. Clone Graph Leetcode Java

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
         / \
         \_/

Solution:

/**

 * Definition for undirected graph.

 * class UndirectedGraphNode {

 *     int label;

 *     List<UndirectedGraphNode> neighbors;

 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

 * };

 */

Because nodes are label uniquely, we can build a hashmap to mapping the labels with the created nodes. BFS the original graph, if the label of visited node has been created, connect it with its neighbor. Otherwise create a new one with the label, connect it with its neighbor and put it into the map.

 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {  
     if(node==null) return node;  
     HashMap<Integer, UndirectedGraphNode> map=new HashMap<Integer, UndirectedGraphNode>();  
     LinkedList<UndirectedGraphNode> q=new LinkedList<UndirectedGraphNode>();  
     q.offer(node);  
     map.put(node.label, new UndirectedGraphNode(node.label));  
     while(!q.isEmpty()){  
       UndirectedGraphNode un=q.poll();  
       for(UndirectedGraphNode temp : un.neighbors){  
         if(map.containsKey(temp.label)) map.get(un.label).neighbors.add(map.get(temp.label));  
         else{  
           UndirectedGraphNode newNode=new UndirectedGraphNode(temp.label);  
           map.put(temp.label, newNode);  
           map.get(un.label).neighbors.add(newNode);  
           q.offer(temp);  
         }  
       }  
     }  
     return map.get(node.label);  
   }