P105 图的深拷贝

描述#

这个题目说的是，给你一个无向图，你要返回这个图的深拷贝。

比如说，给你的图是：
1 --- 2

/ \   /
/   \ /
4 --- 8
你要返回这个图的一份深拷贝，为了和原图区分，我们记为：
1’--- 2’

/ \   /
/   \ /
4’--- 8’
每个图节点可以表示成它的节点值以及它相邻的节点。比如这个图，可以表示成：
1: 2, 4, 8
2: 1, 8
4: 1, 8
8: 1, 2, 4
拷贝图本质上就是把这组结构再复制一遍即可。

代码#

public class AlgoCasts {

  public class UndirectedGraphNode {
    int val;
    List<UndirectedGraphNode> neighbors;
    UndirectedGraphNode(int x) {
      val = x;
      neighbors = new ArrayList<UndirectedGraphNode>();
    }
  }

  private Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();

  // Time: O(E), Space: O(n)
  public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return null;
    UndirectedGraphNode copy = new UndirectedGraphNode(node.val);
    map.put(node, copy);
    for (UndirectedGraphNode n: node.neighbors) {
      if (map.containsKey(n)) copy.neighbors.add(map.get(n));
      else copy.neighbors.add(cloneGraph(n));
    }
    return copy;
  }

}