8

克隆一棵树的算法非常简单，我们可以为此进行前序遍历。是否有一种有效的算法来克隆图？

我尝试了一种类似的方法，并得出结论，我们需要维护一个已经添加到新图中的节点的哈希映射，否则会出现节点重复，因为一个节点可以有多个父节点。

4

4 回答 4

11

进行深度优先搜索并在访问每个节点时复制它就足够了。正如您所说，您需要某种方式将原始图中的节点映射到相应的副本，以便循环和交叉边的副本可以正确连接。

这个映射也足以记住 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或hashCodefor Node。包含副本的映射依赖于定义的引用相等性Object。

另一种方法是在每个节点中放置一个附加字段，如果有则指向副本，否则为空。这只是通过另一种方法实现地图。但它需要两次遍历图表：一次制作副本，另一次清除这些地图字段以供将来重用。

于 2013-01-26T22:48:33.503 回答
3

如果您有一些唯一标识每个节点的快速方法，您的哈希映射方法似乎是可行的。

否则，您最好：

  1. 使用数据结构存储图形，允许您直接在每个节点中存储“重复”唯一标志（例如，0不重复，1 用于numberOfNodes重复节点），

  2. 遍历节点（通过 BFS、DFS）处理已经复制的节点并从起始图重建所有连接。

您的起始图和结束图都应在每个节点中具有相应的唯一“重复”标志，以便您能够正确地从起始图重建连接。当然，您可以使用“重复”标志和“唯一标识符”作为单独的变量。

于 2013-01-26T12:38:18.547 回答
0

当您从源图中复制节点时，将每个节点放置在<Node, Integer>地图中（从而将节点编号从 1 到 N）。

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

当您在源图中找到反向链接时，您可以i使用第一个映射将该反向链接的“源副本”节点映射到整数。接下来，您使用第二个映射查找整数i并找到需要创建相同反向链接的“目标副本”节点。

于 2013-08-10T00:22:36.830 回答
0

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

  • 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)
  1. 第 2 步和第 5 步基于To be processed --> Queue
  2. 步骤 3 上Queue -> To be processed。
  3. 队列元素是那些已经克隆但未处理（即其邻居列表未更新）的元素。
  4. 邻居可能还没有被克隆。因此，需要签入地图。
于 2017-09-03T07:44:35.207 回答