复制图形节点以创建节点网络的全新复制

一个函数，它接受一个节点并复制该节点和所有相邻节点以创建一个与此节点完全相似的新结构。复制图形节点以创建节点网络的全新复制

甲
/\
乙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

复制图形节点以创建节点网络的全新复制

回答

相关问题