检测循环引用

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

您的循环检查不正确的原因是您只在尝试将其添加到的一个节点下查找 JSONNode 的现有副本。但 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 通常运行在恒定时间内 - 树的大小无关紧要。

为了比较：

Markus Lausberg 的答案建议对整个树进行完整的递归搜索，这将是 O(N)，其中 N 是树中的节点数，当您对每个节点进行检查时，它最终会是 O (N^2)。一棵有 10 个节点的树将进行 100 个节点比较；一棵有 1000 个节点的树将进行 1000,0000 个节点比较。

在 kan 的回答中，检查涉及搜索父链，这取决于树的深度。对于完全不平衡的树（最坏情况），深度将与节点数相同，再次给出 O(N^2)。对于平衡树，深度将为 ~log N，好不了多少（请记住，必须对每个节点进行检查）。

这些差异的影响取决于用于确定两个节点是否相同的比较操作。如果只是指针比较（即您只关心它们是否是同一个对象）并且树从来都不是很大，则 HashSet 的开销可能会产生负面影响。然而，如果您需要以更复杂的方式比较两个节点，因此每次比较都很昂贵，并且树很大，那么 HashSet 的优化查找将变得有益。

Answer 2

首先，它应该像

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

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

你必须递归地检查，如果给定节点是父节点的一部分以及父节点的父节点等等......

所以更像

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(temp))
            return true;
    }
    return false;
  }