深度复制Java中

我有一个Java类，节点如下：深度复制Java中

class Node 
{ 
    public ArrayList<Node> nbrs; 
}

每个节点对象包含它的ArrayList中NBRS内的所有邻居的列表，而不是其他。

现在我需要编写一个函数：

public Node copy(Node curr)

该函数应执行在CURR根的整个图形的深层副本，并为CURR返回等效副本。

我试过类节点中实现拷贝构造函数如下：

public Node(Node n) 
{ 
    for(Node curr : n.nbrs) 
     n.nbrs.add(new Node(curr )); 
}

我现在复制节点n，我复印功能中。

但我发现当图形包含循环时，这段代码会无限地运行。

任何帮助我应该如何克服这个问题。

PS：这是面对我的朋友一个面试问题，所以类节点不能包含任何更多的变数

来源

2012-03-26 arya

标准技巧是首先创建所有新节点并将它们存储在映射中（从旧节点到新节点）。然后在所有节点的第二遍中，添加所有边（通过添加到n.nbrs.add）。

来源

2012-03-26 10:20:37

我喜欢你的方法，谢谢！我认为这是最简单的实现方式，因为不需要递归。 – arya 2012-03-26 10:52:26

如果Node类有一个parent你可以检查无限递归的方式。但事实并非如此。所以你需要在克隆操作期间保持一些状态，一个Set包含你正在递归进入的节点。拒绝下降到已经在Set中的节点。

来源

2012-03-26 10:15:52

谢谢，但是我会在集合中存储什么？我正在考虑原始图中的Node对象的哈希值。那会好吗？ – arya 2012-03-26 10:28:31

为什么散列值？对于这里给出的'Node'，散列将与对象标识相关，为什么不清楚并使用'Set '？ – 2012-03-26 10:34:39

是的，你是对的。我可以使用HashSet来达到这个目的。谢谢！ – arya 2012-03-26 10:40:56

考虑使Node对象不可变。在这种情况下使用共享实例不会造成任何伤害。

来源

2012-03-26 10:21:03 3biga

将正在复制的旧节点与新节点之间的映射保存在允许基于标识检索元素的数据结构中（即，如果==运算符返回true，则检索对象）。一个例子是IdentityHashMap。如果您创建一个新节点，然后将其保存到数据结构。

在从先前的ony创建新的Node之前，尝试从数据结构中检索节点。如果您已经有这样的节点，那么将检索到的节点添加到父节点。如果你没有这样的节点，那么继续创建一个（并添加它）。

来源

2012-03-26 10:21:17

如果您可以修改Node类并使其成为Serializable，那么您可以序列化/反序列化对象并获取对象的新图形。

示例代码来说明这一点：

class Node implements Serializable 
{ 
    public List<Node> nbrs = new ArrayList<Node>(); 
} 

Node n1 = new Node(); 
Node n2 = new Node(); 
Node n3 = new Node(); 
n1.nbrs.add(n2); 
n2.nbrs.add(n1); 
n2.nbrs.add(n3); 
n3.nbrs.add(n2); 

ByteArrayOutputStream baos = new ByteArrayOutputStream(); 
ObjectOutputStream dos = new ObjectOutputStream(baos); 
dos.writeObject(n1); 
dos.writeObject(n2); 
dos.writeObject(n3); 

ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray()); 
ObjectInputStream ois = new ObjectInputStream(bais); 

Node n4 = (Node) ois.readObject(); 
Node n5 = (Node) ois.readObject(); 
Node n6 = (Node) ois.readObject();

在这个阶段，你就会有一组新的Node对象，其正确地引用对方。

来源

2012-03-26 10:49:08 beny23

递归中没有基本情况，除了没有邻居的节点。
Daniel Earwicker建议使用Set来确保我们不会添加两次相同的邻居。听起来不错，但是我们如何判断一个节点是否在Set中？ equals的默认实现只是==，所以没有两个节点会被视为相等。 Set包含的方法依赖于equals来确定一个对象是否已经添加到一个集合中。我们冷添加一个id字段到节点，然后通过检查id相等来实现boolean equals(Node other)。这应该使Set解决方案工作。

来源

2012-03-26 11:20:51 Thorn

这个问题排除了添加新字段，但幸运的是这完全没有道理。对于两个节点引用'x'和'y'，如果它们引用同一个节点，'x == y'将是'true'。这正是这里所要求的测试：我们正在检查一个它自己（可能是间接）子节点。 – 2012-03-26 13:44:21

你是否尝试了你的设想，它的工作？由于我们正在复制节点，我不认为x == y是我们想要的等于。 – Thorn 2012-03-26 15:29:10

从问题：“但我发现当图形包含循环时，此代码无限运行。”即该图包含至少一个节点“N”，该节点具有一个子节点列表，其中一个节点具有子节点列表（以此类推......），其中之一是“N”。这就是'N'（同一个对象）在同一棵树中出现两次。这是OP需要解决的问题。另一种考虑它的方法是：在你的建议中，你是否要给每个节点一个唯一的ID？ – 2012-03-27 08:12:20

深度复制Java中

回答

相关问题