深度复制图结构

Question

我有一个带有Node的图类，其中每个Node可以连接到其他节点：

public class Node {
  List<Node> connections;
}

我想复制整个图。第一次尝试，我尝试制作一个类似以下的复制构造函数：

public Node(Node other) {
  connections = new ArrayList<Node>();
  for (Node n : other.connections) { 
    connections.add(new Node(n));
  }
}

因此，深度复制图形将是：

public Graph deepCopy () {
  Graph g = new Graph();
  g.nodes = new ArrayList<Node>();
  for (Node n : nodes) { 
    g.nodes.add(new Node(n));
  }
}

但这不起作用，因为这破坏了节点之间的连接关系。我想知道是否有人建议以一种简单的方式做到这一点？谢谢。

Answer 1

问题是您需要复制节点的身份，而不仅仅是节点的值。具体来说，当您复制某个节点时，您需要处理其所指节点的身份。这意味着复制构造函数或其他某种纯本地复制机制无法完成此工作，因为它一次只能处理一个节点。我不确定这是否有意义，但是我已经键入了它，而我的退格键不起作用。

无论如何，您可以做的是绕过其他一些对象，该对象可以判断哪个新节点对应于哪个旧节点。如果想花哨（谁不想要），可以将其称为图同构。这可以像地图一样简单。如以下完全未经测试的代码所示：

// in Graph
public Graph deepCopy () {
  Graph g = new Graph();
  g.nodes = new ArrayList<Node>();
  Map<Node, Node> isomorphism = new IdentityHashMap<Node, Node>();
  for (Node n : nodes) { 
    g.nodes.add(n.deepCopy(isomorphism));
  }
  return g;
}

// in Node
public Node deepCopy(Map<Node, Node> isomorphism) {
    Node copy = isomorphism.get(this);
    if (copy == null) {
        copy = new Node();
        isomorphism.put(this, copy);
        for (Node connection: connections) {
            copy.connections.add(connection.deepCopy(isomorphism));
        }
    }
    return copy;
}

Sergii提到使用序列化。遍历对象图时，序列化实际上执行的操作非常相似。