algorithm - 在这种情况下，循环引用检查的好算法是什么？

Question

假设您有以下类(class)(糟糕的 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 和所有子项进行引用检查，然后在 target 上调用 PerformCircularReferenceCheck，传递 this。但我想知道是否有更好的、被证明有效的方法来做到这一点，例如添加一种方法来折叠 this 和 target 的整个子引用树和然后检查结果(堆栈压力更小？)，或者可能通过使用不同于 List 的不同(可能是 self 检查!)集合来完全避免检查？

你会怎么做？

编辑:正如 stefan 指出的，只需要确定目标是否可达

Answer 1

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

假设到目前为止，没有创建任何循环的前提条件，您想要的函数 PerformCircularReferenceCheck 只需要检查“this”是否可以从“target”到达。如果是，它应该返回一个异常。

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

特别是，萨维奇定理 ( http://en.wikipedia.org/wiki/Savitch%27s_theorem ) 给出了一种建设性的方法来为其创建 O(log^2 n) 空间算法(运行时间为 O(n^2))，其中 n 是节点数.

此外，作为 NL-complete，不太可能存在在空间 O(log n) 中运行的算法(即仅使用恒定数量的指向节点的指针)，因为这意味着不太可能的 NL = L。编辑:特别是，某人建议的 hare 和 turtle 算法的小变化是行不通的(因为它们使用的空间太小)。

我会建议实现简单的 O(n) 时间、O(n) 空间算法，该算法为“目标”生成其后继集合(递归)并验证“this”是否出现在该集合中。

请注意，集合的显式构造很重要。否则，如果您只是递归地验证“this”是否可以被“target”的任何后继者访问，您就有可能在指数时间内运行。

我推荐 O(n) 时间/O(n) 空间算法，因为它是您在时间方面可以做到的渐近最佳算法，并且您已经在为您的数据结构使用 O(n) 空间。