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
public class Solution {
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
class Solution:
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