算法克隆图(Algorithm to clone a graph)

算法克隆一棵树是很容易的，我们可以为做前序遍历。是否有一个有效的算法克隆的图形？

我尝试过类似的方法，并得出结论：我们需要保持在新图中已经添加节点的哈希地图，否则就会出现节点的重复，因为一个节点可以有很多的父母。

Answer 1:

这足以做深度优先搜索，并因为它的访问复制的每个节点。正如你所说，你需要映射节点的一些方法是原图中的相应副本，这样循环和交叉边缘的副本可以被正确连接。

这张地图也足以记得在DFS已经访问过的节点。

所以，在Java中你会碰到这样的：

class Node {

  // Contents of node...
  Data data;

  // ... member declarations like array of adjacent nodes
  final ArrayList<Node> children = new ArrayList<>();

  // Recursive graph walker for copying, not called by others.
  private Node deepCloneImpl(Map<Node, Node> copies) {
    Node copy = copies.get(this);
    if (copy == null) {
      copy = new Node(data);
      // Map the new node _before_ copying children.
      copies.put(this, copy);
      for (Node child : children)
        copy.children.add(child.deepCloneImpl(copies));
    }
    return copy;
  }

  public Node deepClone() {
    return deepCloneImpl(new HashMap<Node, Node>());
  }
}

请注意，你不希望覆盖equals或hashCode的Node 。含有复制地图依赖于参考平等通过定义Object 。

另一种办法是把一个额外的领域中指向副本，如果有一个为空，否则每个节点。这仅仅是实现通过另一种方法的图。但它需要两个越过图：一个使复印件，另一个清除将来再使用这些地图领域。

Answer 2:

如果你有唯一标识每个节点的一些快捷方式你的哈希表的方法似乎是可行的。

否则，你最好关闭，如果你：

使用的数据结构以存储图形，允许你存储“是重复的” 独特标志直接在每一个节点（例如， 0不重复， 1至numberOfNodes为重复的节点），
经过的各个节点（BFS通过，DFS）服用已复制节点的关怀和重建从开始图表中的所有连接 。

无论你的起点图形和整理图形应该有相应的唯一 “被复制”标志中的每个节点，以便您能够重建从正常启动图形连接。当然，你可以使用“被复制”标志和“唯一标识符”作为独立变量。

Answer 3:

当你从源图表复制节点，放置在每一个节点<Node, Integer>地图（因此编号的节点从1至N）。

当你在目标图表粘贴节点，放置在每一个节点<Integer, Node>地图（从1再次编号到N，但在相反的方向，其原因将很快清楚映射）。

当你发现在源图的反向链接，你可以映射backlinked“源复制”节点为整数i使用的第一张地图。接下来，使用第二个地图来查找整i ，找到其需要已经创建了相同的反向链接的“目标副本”节点。

Answer 4:

为了使克隆效率，使用两件事情：

DS 更快的删除和添加在结尾。选择中list ， queue或stack
DS使用快速搜索 。 Map可以快速地搜索，即O(1)摊销。

算法：

                        To be processed <--> Queue
                          / 
Not_Cloned_Yet -> Clone it -> Map
      `~~~~~~~~checks~~~~~~~~~~^


Root is "Not Cloned yet" and needs to be "To be processed" -- (1)
Clone it -> Put in Map & Queue  -- (2)

Continue till "To be processed" is not zero. i.e. Queue is not empty. -- (3)
    Traverse and update the list of neighbours  -- (4)
        Neighbours that are "Not cloned yet" needs "Clone it -> Put in Map & Queue"   --(5)