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

Question

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

A

/\

B C-E

\/

D

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

Node对象由定义

节点{

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

}

这段代码能工作吗？

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 个节点的图，你就会有一个无限递归，因为在每种情况下你总是会为每个孩子调用递归函数。
• 错误的递归情况：在某些情况下，递归函数在循环中被调用了两次
• 图形只有一个节点时的错误行为：它不会被复制

解决方案：

• 删除对邻居的测试
• 如果哈希表中包含处理节点，则直接返回重复节点
• 如果没有，新建一个节点，在表中添加对应关系，别忘了初始化neighbors变量
• 在循环中，删除测试并始终填充邻居变量

其他潜在问题：

• 递归函数是公共的。如果我们不需要在非多线程上下文中提供哈希表的预填充hashtable
• Usage而不是哈希图，则不应该是公共的
• 如果A为空则无错误管理