[leetcode] Clone Graph | 克隆无向图

Posted by: lexigrey on: October 8, 2013

• In: leetcode
• Leave a Comment

倒是20分钟写出来了bugfree，比较喜欢这种利用data structure的题，感觉试一试总能想出来。

这个题就是基本BFS，要点是生成新节点的同时，怎么把新节点和其他新节点连起来呢？这就需要一个新旧节点对应map，每次生成新节点A’，要把dequeue的这个parent B对应的新节点B’和当前作为child的新节点A’连起来。注意单向连就行了(B’->A)’，因为下次把A当作root的时候，还会经历B作为child，这时再A’->B’。

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
  if (node == null)
    return null;
  Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>(); 
  Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
  enqueueAndClone(q, node, map);
  while (!q.isEmpty()) {
    UndirectedGraphNode parent = q.poll();
    for (UndirectedGraphNode child : parent.neighbors) {
      if (!map.containsKey(child))
        enqueueAndClone(q, child, map);
      map.get(parent).neighbors.add(map.get(child));//不管是否visit过，都要单向连接 
    }
  }
  return map.get(node);
}
private void enqueueAndClone(Queue<UndirectedGraphNode> q, UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
  q.add(node);
  UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
  map.put(node, newNode);
}

Tags: bfs, easy, graph, stack/queue