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

鉴于你有下面的类（坏的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上target，传递this。但是我想知道是否有更好的，经过验证的有效的方法来执行此操作，例如添加一个方法来折叠整个参考文献的子树this和target，然后检查结果（减少堆栈压力？），或者也许完全避免使用除列表< T>以外的其他（可能是自检！）集合的检查？

你会如何做到这一点？

编辑：作为斯特凡指出的那样，仅仅需要以确定这是否是由所述目标

来源

2009-01-09 Will

如果它不是家庭作业，那么我让JSON序列化程序为我做。如果存在，JsonConvert.SerializeObject（myObject）将抛出循环引用错误。 – 2016-02-25 22:12:52

在你从不添加自参考（将在后面定义）的对象的情况下，数据结构描述了一种向无环图（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-完整的，存在运行在空间O（logn）（即仅使用恒定数量的指向节点的指针）的算法是不太可能的，因为那意味着不太可能的NL = L编辑：特别是，有人建议的兔子和龟算法的小变化不起作用（因为他们会使用太少的空间）。我会建议实施一个微不足道的O（n）时间，O（n）空间算法，它为它的一组继承者（递归地）产生“目标”，并验证这个集合是否出现“this”。

要小心，该组的显式构造很重要。否则，如果您只是递归地验证“this”是否可以被任何“target”的后继者访问，那么您将面临以指数时间运行的风险。

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

来源

2009-01-09 16:32:17 user51568

的迭代解决方案是定义的一组R（可达）和CR（可达的孩子）可达。

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

在每个步骤中，检查CR是否包含this（或target，具体取决于您的确切目标）。如果不是，则将CR添加到R并将CR设置为CR的子项，并从CR中删除R的元素。

如果CR变空，则R是从this可到达的完整元素集。

来源

2009-01-09 16:01:54 MSalters

当你说CR时，你的意思是RC吗？ – 2017-11-10 16:16:04

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

回答

相关问题