克隆图的算法

Question

克隆树的算法非常简单,我们可以为此预先遍历遍历.是否有一种有效的算法来克隆图形？

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

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.

另一种方法是在每个节点中添加一个指向副本的附加字段(如果有),否则为null.这只是通过另一种方法实现地图.但它需要在图表上进行两次传递:一次用于复制,另一次用于清除这些地图字段以供将来重复使用.

Answer 2

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

否则，如果您：

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

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

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