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