深度複製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中

回答

相關問題