深度复制图形结构
我有一个带有Node的图表类，其中每个Node都可以连接到其他节点：
public class Node { List connections; } 我想对整个图表进行深度复制。 作为第一次尝试，我尝试制作一个复制构造函数，如：
public Node(Node other) { connections = new ArrayList(); for (Node n : other.connections) { connections.add(new Node(n)); } }
如此深入复制图形只会是：
public Graph deepCopy () { Graph g = new Graph(); g.nodes = new ArrayList(); for (Node n : nodes) { g.nodes.add(new Node(n)); } }
但这不起作用，因为它破坏了节点之间的连接关系。 我想知道是否有人建议以简单的方式做到这一点？ 谢谢。
问题是您需要复制节点的标识，而不仅仅是它们的值。 具体来说，当您复制某个节点时，您需要处理它所引用的节点的标识; 这意味着复制构造函数或其他一些纯粹的本地复制机制无法完成这项工作，因为它一次只处理一个节点。 我不确定这有什么意义，但我输入了它，我的退格键不起作用。
无论如何，你可以做的是传递一些其他对象，它可以告诉哪个新节点对应哪个旧节点。 如果你想要花哨（谁没有？）你可以将其称为图形同构 。 这可以像地图一样简单。 就像在这个完全未经测试的代码中一样：
// in Graph public Graph deepCopy () { Graph g = new Graph(); g.nodes = new ArrayList(); Map isomorphism = new IdentityHashMap(); for (Node n : nodes) { g.nodes.add(n.deepCopy(isomorphism)); } return g; } // in Node public Node deepCopy(Map 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提到使用序列化; 序列化在遍历对象图时实际上做了类似的事情。
是的，java中的深层复制（不仅仅是在java中）可以使用像这样的内存serialization/deserialization
public static Object copy(Object orig) { Object obj = null; try { // Write the object out to a byte array ByteArrayOutputStream bos = new ByteArrayOutputStream(); ObjectOutputStream out = new ObjectOutputStream(bos); out.writeObject(orig); out.flush(); out.close(); // Make an input stream from the byte array and read // a copy of the object back in. ObjectInputStream in = new ObjectInputStream( new ByteArrayInputStream(bos.toByteArray())); obj = in.readObject(); } catch(IOException e) { e.printStackTrace(); } catch(ClassNotFoundException cnfe) { cnfe.printStackTrace(); } return obj; }