在这种情况下,什么样的算法适合用于循环引用检查?

16

假设你有以下类(C#代码不太好,但你可以理解):

public abstract class AmICircular
{
  // assume Children is never null
  private List<AmICircular> 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?不,这不是作业。
在我看来,天真的实现方式是对this和所有子元素进行引用检查,然后调用PerformCircularReferenceCheck在目标上,传递this。但我想知道是否有更好、经过有效验证的方法来做到这一点,比如添加一个方法来折叠this和目标的整个Children引用树,然后检查结果(减少堆栈压力?),或者通过使用不同的(可能是自检!)集合而完全避免检查List<T>?
你会怎么做?
编辑:正如stefan指出的那样,只需要确定目标是否可以访问此内容。

1
如果这不是作业的话,我会让JSON序列化器为我完成。如果存在循环引用,JsonConvert.SerializeObject(myObject)将抛出一个错误。 - Papa Burgundy
2个回答

14
在你从未添加自引用(稍后定义)对象的情况下,你的数据结构描述了一个有向无环图(http://en.wikipedia.org/wiki/Directed_acyclic_graph),其中IAmCircular类的每个实例都描述了一个具有一组直接后继节点= Children的节点。
假设前提条件是在此之前没有创建循环,您想要的函数PerformCircularReferenceCheck只需要检查是否可以从"target"到达"this"。如果可以,它应该返回异常。
从复杂度理论上讲,这个问题是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。编辑:特别地,某人建议的采用龟兔算法的小变化将不起作用(因为它们使用的空间太少)。
我建议实现简单的O(n)时间、O(n)空间算法,为"target"生成其后继集合(递归)并验证"this"是否出现在该集合中。
要注意,集合的显式构建很重要。否则,如果您只是递归地验证"this"是否可由"target"的任何后继到达,则可能会以指数时间运行。
我推荐O(n)时间/O(n)空间算法,因为从时间上看它是渐进最优的,而且您已经为数据结构使用了O(n)空间。

8
迭代解决方案是定义一组R(可达)和CR(可达的子级)。
您可以从 R = {this} 和 CR = { this.children } 开始。
每个步骤中,您都要检查CR是否包含 this (或 target ,具体取决于您的目标)。如果没有,则将CR添加到R并将CR设置为CR的子项,并从CR中删除R的元素。
如果CR变为空,则R是从 this 可以到达的所有元素的完整集合。

当你说CR时,你是指RC吗? - Petrus Theron
@PetrusTheron:方向相反,但是没错 - 已修复。 - MSalters

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接