複製圖形節點以創建節點網絡的全新複製

一個函數，它接受一個節點並複製該節點和所有相鄰節點以創建一個與此節點完全相似的新結構。複製圖形節點以創建節點網絡的全新複製

甲
/\
乙CE
\/
d

應該創建新節點

一個節點對象通過

節點{限定的類似網絡

Arraylist neighbors; //返回數組列表中的所有相鄰節點

}

此代碼是否工作？

public Node copyGraph(Node A){ 
    HashTable<Node, Node> hash = new HashTable<Node, Node>(); 

    return copyGraphWithHash(A, hash); 

} 

public Node copyGraphWithHash(Node A, HashTable<Node, Node> hash){ 


    if (A.neighbours.size() == 0) 
    return null; 

    Node newfirst = null; 

    if(!hash.hasKey(A)) 
    newfirst = new Node(); 
    hash.add(A,newfirst); 
    } 


    for (Node n : A.neighbours()){ 

    if (copyGraphWithHash(n, hash)) 
     newfirst.neightbours.add(copyGraphWithHash(n, hash)); 
    } 
    return newfirst; 
}

請建議我在這裏錯過什麼？

來源

2012-07-14 Himani

該代碼將通過拋出堆棧溢出異常結束。

問題：

錯誤的基本情況：只要你有含至少2個節點的圖，你將有一個無限循環，因爲你總是會調用遞歸函數在任何情況下每一個孩子。
錯誤遞歸的情況：遞歸函數調用在循環兩次，在某些情況下
錯誤的行爲，如果有圖有隻有一個節點：它不會被複制

解決方案：

刪除測試
如果哈希表中包含的處理節點，直接返回重複的節點
如果沒有，創建一個NE w ^節點，添加對應關係表中，不要忘了初始化變量
在循環鄰居，取下試，總是充滿變數鄰居

其他潛在的問題：

遞歸函數是公共的。如果我們不需要提供一個哈希表，而不是一個HashMap中的預填充哈希表
使用在非多線程上下文
沒有錯誤的管理，如果A是空不宜公開

來源

2012-07-14 09:46:01 cporte

複製圖形節點以創建節點網絡的全新複製

回答

相關問題