Clone Graph

Source

Clone an undirected graph. Each node in the graph
contains a label and a list of its neighbors.

How we serialize an undirected graph:

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 #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
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
     / \
     \_/
Example
return a deep copied graph.

Java

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node==null) return null;

        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        UndirectedGraphNode result = new UndirectedGraphNode(node.label);
        map.put(node, result);
        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        queue.add(node);
        while(!queue.isEmpty()){
            UndirectedGraphNode nodeInQueue = queue.poll();

            for(UndirectedGraphNode neighbor: nodeInQueue.neighbors){
                if(map.containsKey(neighbor)){
                    map.get(nodeInQueue).neighbors.add(map.get(neighbor));
                }
                else{
                    UndirectedGraphNode neighborClone = new UndirectedGraphNode(neighbor.label);
                    map.put(neighbor, neighborClone);
                    map.get(nodeInQueue).neighbors.add(neighborClone);
                    queue.add(neighbor);
                }
            }
        }
        return result;
    }
}

Python

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []
class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def __init__(self):
        self.dict = {}

    def cloneGraph(self, node):
        if node is None:
            return None
        hash_map={}
        queue=[]

        clone_node = UndirectedGraphNode(node.label)

        queue.append(node)
        hash_map[node]=clone_node

        while queue:
            node_in_queue = queue.pop()

            for neighbor in node_in_queue.neighbors:
                if neighbor in hash_map:
                    hash_map[node_in_queue].neighbors.append(hash_map[neighbor])
                else:
                    clone_neighbor = UndirectedGraphNode(neighbor.label)
                    hash_map[neighbor] = clone_neighbor
                    hash_map[node_in_queue].neighbors.append(clone_neighbor)
                    queue.append(neighbor)
        return clone_node