在這種情況下，循環引用檢查的算法是什麼？

鑑於你有下面的類（壞的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

在這種情況下，循環引用檢查的算法是什麼？

回答

相關問題