在这种情况下,循环引用检查的优秀算法是什么？

鉴于你有以下课程(糟糕的C#,但你得到漂移):

public abstract class AmICircular
{
  // assume Children is never null
  private List Children {get;set;}

  // assume target is never null
  public void Add(AmICircular target)
  {
    target.PerformCircularReferenceCheck(this);
    Children.Add(target);
  }

  // throws when a circular reference is detected
  protected abstract void PerformCircularReferenceCheck(AmICircular target);
}

你将如何实现PerformCircularReferenceCheck？而且,不,这不是功课.

天真的实现,imo,将对this所有孩子进行参考检查,然后调用PerformCircularReferenceCheck target,传递this.但是,如果有更好的,证明是有效的,方法可以做到这一点,如添加的方法崩溃的参考文献的全部儿童树我想知道this和target,然后检查结果(压力较小的堆栈？),或者避免完全通过使用List 以外的其他(也许是自我检查!)集合进行检查？

你会怎么做？

编辑:正如stefan指出的那样,只需要确定目标是否可以达到

在您从未添加自引用(稍后定义)对象的情况下,您的数据结构描述了有向无环图(http://en.wikipedia.org/wiki/Directed_acyclic_graph),其中IAmCircular的每个实例class描述具有一组直接后继节点= Children的节点.

假设到目前为止没有创建循环的前提条件,你想要的函数PerformCircularReferenceCheck只需要检查"this"是否可以从"target"到达.如果是,则应返回异常.

复杂性理论明智,这个问题是ST连接(http://en.wikipedia.org/wiki/St-connectivity)并且对于NL类是完整的(http://en.wikipedia.org/wiki/NL_(complexity) )),即使你将输入限制为非循环图(这是你的情况).

特别是,Savitch定理(http://en.wikipedia.org/wiki/Savitch%27s_theorem)提供了一种建设性的方法来创建一个O(log ^ 2 n)空间算法(在时间O(n ^ 2)中运行)它,其中n是节点数.

此外,由于NL-complete,不太可能存在在空间O(log n)中运行的算法(即仅使用指向节点的恒定数量的指针),因为这意味着不可能的NL = L. EDIT:in特别是,有人建议的野兔和海龟算法的小变化是行不通的(因为它们会占用太少的空间).

我建议实现平凡的O(n)时间,O(n)空间算法,该算法为"目标"生成其后继子集(递归)并验证此集合中是否出现"this".

要小心,集合的明确构造很重要.否则,如果您只是递归验证"目标"的任何后继者是否可以访问"此",则可能会以指数时间运行.

我推荐了O(n)时间/ O(n)空间算法,因为它是渐进式的,你可以在时间上做到最好,并且你已经在为数据结构使用O(n)空间了.

迭代解决方案是定义集合R(可达)和CR(可达的子集).

你从R = {this}和开始CR = {this.children}.

在每个步骤中,您检查CR是否包含this(或者target,取决于您的确切目标).如果没有,则将CR添加到R并将CR设置为CR的子项,并从CR中删除R的元素.

如果CR变空,则R是可从中获得的完整元素集this.