檢測循環引用

Question

所以在一次採訪中，我被問到了一個簡單的問題，就是說我有一個嵌套的JSON響應[a，b，c，d [a，[b，[d，e ]，g]，h]。有人問我實現一個類，基本上可以處理存儲這些數據，並打印方法，這樣做的，所以這是我有：

public class JSONode 
{ 
    private String str; 
    private JSONode nodes; 

    public JSONode (String a, ArrayList<String> n) 
    { 
     str = a; 
     nodes = n; 
    } 
} 

public class JSONResp 
{ 
    private ArrayList<JSONode> arr; 

    public JSONResp() 
    { 
    arr = new ArrayList<JSONode>(); 
    } 

    public boolean checkCircular(JSONode temp) 
    { 
    for (int i = 0; i < arr.size(); i++) 
    { 
     if (arr.get(i).nodes == temp) 
      return true; 
    } 
    return false; 
    } 

    public void add (JSONode nd) 
    { 
    if (!checkCircular(nd)) 
    arr.add(nd); 
    } 

    public void recurseJSONode(JSONode) 
    { 
     if (!JSONode.node) 
      System.out.print(JSONode.str); 
     else { 
      System.out.print(JSONode.str); 
      recurseJSONode(JSONode.node); 
     } 
    } 

    public void print() 
    { 
    for (int i = 0; i < arr.size(); i++) 
     recurseJSONode(arr.get(i)); 
    } 

    public static void main (String[] args) { 
     JSONResp x = new JSONResp(); 
     x.add(new JSONode("a", null); 
     x.add(new JSONode("b", null); 
    } 

} 

現在，他說，將有循環引用的問題，當我打印，在換句話說，我有列表A = [a，b，c，D]和D = [q，t，y，A]。所以他說我必須通過使用上面的checkCircular來防止添加D.我做了一個嘗試。也只是一個節點，我知道我的recurseJSONode是不正確的，打印也是這樣，所以尋找一個建議來解決這個問題。我只是好奇這個問題。

Answer 1

首先應該像

public class JSONode 
{ 
    private String str; 
    private ArrayList<JSONode> nodes; 

    public JSONode (String a, ArrayList<JSONode> n) 
    { 
     str = a; 
     nodes = n; 
    } 
} 

你必須recursivly檢查，如果給定的節點是父節點的一部分，父的父等等...

所以更像

public static boolean checkCircular(JSONode temp) 
    { 
    if(temp == null){ 
     return false; 
    } 

    ArrayList<JSONode> pNodes = temp.getChildrens(); 

    for (int i = 0; i < nodes.size(); i++) 
    { 
     if (pNodes.get(i).getString().equals(temp.getString())) 
      return true; 
     if(checkCircular(pNodes.get(i).getNodes(),temp)) 
      return true; 
    } 
    return false; 
    } 

Answer 2

你的循環檢查不正確的原因是你只在你試圖添加它的節點下尋找JSONode的現有副本。但A可能在B下，B在A下，所以每個在其父列表中都是唯一的。

重新：使用用於跟蹤活動的堆疊中一個遞歸函數：

Set<SomeNodeType> stack = new HashSet<SomeNodeType>(); 
someRecursiveThing(rootNode, stack); 

然後內部someRecursiveThing：

void someRecursiveThing(SomeNodeType under, Set<SomeNodeType> stack) { 

    if (!stack.add(under)) { 
     return; 

    // continue happily, e.g. call self with child node, 
    // passing down the stack 

    SomeNodeType child = ... 
    someRecursiveThing(child, stack) 

    // finish by removing 'under' from the stack: 
    stack.remove(under); 
} 

的HashSet的優點是add和remove在恆定的時間通常運行 - 樹的大小是無關緊要的。

對於比較：

馬庫斯Lausberg的回答表明，做一個完整的遞歸搜索整個樹，這將是O（N），其中N是樹中的節點的數量，和你正在做的檢查對於每個節點它最終都是O（N^2）。 10個節點的樹將進行100個節點比較; 1000個節點的樹將進行1000,000個節點比較。

在kan的回答中，檢查包括搜索父鏈，這取決於樹的深度。對於完全不平衡的樹（最壞情況），深度將與節點數相同，再次給出O（N^2）。對於一棵平衡的樹來說，深度將是〜log N，並不是太好（記住，必須爲每個節點完成檢查）。

這些差異的影響取決於用於確定兩個節點是否相同的比較操作。如果它只是一個指針比較（即，你只關心它們是否是同一個對象），並且該樹永遠不會很大，則HashSet的開銷可能會產生負面影響。而如果您需要以更復雜的方式比較兩個節點，那麼每個比較都很昂貴，而且樹很大，那麼HashSet的優化查找將變得有益。