0

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

A
/ \
B CE
\ /
D

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

一个 Node 对象定义为

节点{

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

}

这段代码会起作用吗？

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

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

4

1 回答 1

1

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

问题 ：

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

解决方案：

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

其他潜在问题：

  • 递归函数是公开的。如果我们不需要提供预填充的哈希表，则不应公开
  • 在非多线程上下文中使用哈希表而不是哈希图
  • 如果 A 为空，则无错误管理
于 2012-07-14T09:46:01.410 回答