java - 复制图形节点以制作节点网络的全新复制

Question

一个函数，它获取一个节点并复制该节点和所有相邻节点以创建与该节点完全相似的新结构。

一个
/\
B C-E
\/

应该用新节点创建类似的网络

一个Node对象由

定义

节点{

数组列表邻居；//返回数组列表中的所有相邻节点

这段代码能用吗？

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;
 }

请建议我在这里缺少什么？

Answer 1

此代码将以抛出堆栈溢出异常结束。

问题:

• 错误的基本情况:只要你有一个包含至少 2 个节点的图，你就会有一个无限递归，因为你总是会在每种情况下为每个 child 调用递归函数。
• 错误的递归情况:在某些情况下，递归函数在循环中被调用了两次
• 如果图只有一个节点，则错误行为:它不会被复制

解决方案:

• 取消对邻居的测试
• 如果哈希表中有被处理的节点，直接返回重复的节点
• 如果没有，新建一个节点，在表中添加对应关系，不要忘记初始化neighbors变量
• 在循环中，去掉test，始终填充neighbors变量

其他潜在问题:

• 递归函数是公开的。如果我们不需要提供预填充的哈希表，则不应公开
• 在非多线程上下文中使用哈希表而不是 HashMap
• 如果 A 为 null，则不进行错误管理