java - 深度复制图结构

Question

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

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

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

无论如何，你能做的就是传递一些其他对象，它可以告诉哪个新节点对应于哪个旧节点。如果您想变得更花哨(谁不想呢？)，您可以将其称为 graph isomorphism 。这可以是像 map 一样简单的东西。正如这段完全未经测试的代码:

// 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 提到使用序列化；序列化在遍历对象图时实际上会做一些非常相似的事情。