什么将是一个很好的算法，在这种情况下，循环引用检查？ [英] What would be a good algorithm for a circular reference check in this case?

问题描述

鉴于你有下面的类（坏的C＃，但你的漂移）：

Given you have the following class (bad C#, but you get the drift):

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？而且，不，这不是功课。

How would you implement PerformCircularReferenceCheck? And, no, this isn't homework.

天真的实施，国际海事组织，是做对这和所有的孩子，然后调用PerformCircularReferenceCheck对目标，通过这。但我不知道是否有更好的，证明是有效的，方法可以做到这一点，如添加方法崩溃参考文献的全部儿童树这和目标键，然后检查结果（在栈上少pressure？），或者避免检查全部通过使用不同的（可能是自检！）集合以外名单，其中， T>？

The naive implementation, imo, would be to do a reference check on this and all children, then call PerformCircularReferenceCheck on target, passing this. But I'm wondering if there are better, proven effective, ways to do this, such as adding a method to collapse the entire Children tree of references for this and target and then examine the results (less pressure on the stack?), or perhaps avoid the check entirely by using a different (maybe self-checking!) collection other than List<T>?

你会怎么做呢？

编辑：斯特凡指出的那样，以确定这是否是可访问的目标是只需要的

推荐答案

在那里，你永远不会添加自引用（稍后定义）对象的情况下，你的数据结构描述了向无环图（的 http://en.wikipedia.org/wiki/Directed_acyclic_graph ），其中的的IAmCircular类的每个实例描述了一个节点有一组直接后继节点=儿童。

In the case where you never add self-referencing (to be defined later) objects, your data structure describes a directed acyclic graph (http://en.wikipedia.org/wiki/Directed_acyclic_graph), where each instance of the of the IAmCircular class describes a node with a set of direct successor nodes = Children.

假设precondition，截至这一刻，没有创建循环，你想要的功能，PerformCircularReferenceCheck，只需要检查这个距离目标访问。如果是，它应该返回一个例外。

Assuming the precondition that up to this moment, no cycle was created, the function you want, PerformCircularReferenceCheck, needs only to check if "this" is reachable from "target". If it is, it should return an exception.

复杂性理论明智的，这个问题是ST-连接（ http://en.wikipedia.org /维基/ ST-连接），是完整的类NL（ HTTP：/ /en.wikipedia.org/wiki/NL_(complexity）），即使你限制输入到无环图（这是你的情况）。

Complexity theory wise, this problem is ST-connectivity (http://en.wikipedia.org/wiki/St-connectivity) and is complete for the class NL (http://en.wikipedia.org/wiki/NL_(complexity)), even when you restrict the input to acyclic graphs (which is your case).

在特定，Savitch定理（ http://en.wikipedia.org/wiki/Savitch% 27s_theorem ）给出了建设性的方式来创建一个O）的话，其中n为节点的数目（日志^ 2 n）的空间算法（以时间为O（n ^ 2运行）。

In particular, Savitch's theorem (http://en.wikipedia.org/wiki/Savitch%27s_theorem) gives a constructive way to create a O(log^2 n) space algorithm (running in time O(n^2)) for it, where n is the number of nodes.

此外，作为NL-完整，这是不可能的，存在其中运行在空间ö一个算法（log n）的（即使用指针的节点只有一个恒定数），因为这将意味着不可能NL = L编辑：特别是，兔子和乌龟算法中所有人建议小的变化是行不通的（因为他们会用空间太少）

Also, being NL-complete, it is unlikely that there exists an algorithm which runs in space O(log n) (i.e. use only a constant number of pointers to nodes), since that would imply the unlikely NL = L. in particular, small variations of the hare and turtle algo suggested by someone would not work (because they would use too little space).

我会建议实施的琐碎O（n）时间，O（n）的空间算法，该算法生成的目标，它集接班人（递归）和检验，如果这出现在这一套。

I would recommend implementing the trivial O(n) time, O(n) space algorithm, which generates for "target" its set of successors (recursively) and verifying if "this" appears in this set.

要小心，一组明确的建设是非常重要的。否则，如果你只是递归验证，如果这是可达的目标的任何继任者，你就有可能在指数时间运行。

Be careful, the explicit construction of the set is important. Otherwise, if you just recursively verify if "this" is reachable by any successor of "target", you risk to run in exponential time.

我推荐的O（n）时间/ O（n）的空间算法，因为它是渐近最好的，你可以做一次明智的，并且你已经在使用O（N）为您的数据结构的空间。

I recommended the O(n) time/O(n) space algorithm because it is asymptotically the best you can do time-wise, and you are already using O(n) space for your data structure.

这篇关于什么将是一个很好的算法，在这种情况下，循环引用检查？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！