如何在我的对象层次结构中查找循环？

Question

有一个名为 Company 的类，它具有引用另一个 Company 实例的能力来表示 parent（父组织）。 假设有四个公司 c1，c2，c3和c4，其中c2，c3，c4的上级公司设置为c1。

例如：

public class Company {
  public Company parent;

  public Company() { }
  public Company(Company parent) {
    this.parent = parent;
  }

  public static void main(String[] args) {
    Company c1 = new Company();
    Company c2 = new Company(c1);
    Company c3 = new Company(c1);
    Company c4 = new Company(c1);
}

如果我们将c2设置为c1的母公司：

c1.parent = c2;

那么它将在公司层次结构中创建一个圈复杂度无限循环，我们必须避免在我们的系统中出现这种情况。

我们希望能够在运行时检测到这一点。在上述情况下，检查同一类对象的圈复杂度的最佳算法是什么？

- Mukesh Kumar

Answer 1

你的任务与圈复杂度无关。你的实体基本上形成了一个图形，你想要检测其中的循环。通常的做法是执行 DFS。你可以在 互联网上 找到大量的例子。

- Aivean

Answer 2

我已经通过编程解决了这个问题，创建了一个本地的已处理对象的Set，并让它在每次递归方法调用时作为输入参数传播。

例如：

public void myMethod(Company c)
{
    Set<Company> visitedCompanies=new HashSet<Company>();
    visitedCompanies.add(c);
    myPrivateMethod(c, visitedCompanies);
}

private void myPrivateMethod(Company c, Set<Company> visitedCompanies)
{
    if (visitedCompanies.contains(c))
    {
        // Cylce detected
    }
    else
    {
        //... do some stuff

        // Go upwards in the hierarchy
        if (c.getParent()!=null)
        {
            visitedCompanies.add(c);
            myPrivateMethod(c.getParent(), visitedCompanies);
        }
    }

当然，您首先必须确保您的Company类是可索引的：它正确地重写了hashCode和equals方法。

请注意，即使在Company抽象之外（如此示例），也可以实现此算法，因为它将Company对象作为遍历状态的一部分（与集合一起）在每次调用中传播。这不是强制性的，因为这些方法本身可以是Company抽象的一部分，但是强制要求将集合作为输入参数进行传播。

- Little Santi

Answer 3

您可以将parent设置为private，并使用方法setParent(Company)更改parent的值。然后：

public boolean setParent(Company parent) {
    Company curr = parent;
    while (curr != null) {
        if (curr.equals(this)) {
            return false; // Failed as cycle
        } else {
            curr = curr.getParent();
        }
    }
    this.parent = parent;
    return true;
}

通常情况下，将变量设置为public是不好的实践，因为它会破坏封装性。

如果您无法将字段更改为private，那么：

public List<Company> hasCycle(List<Company> companies) {
    while (companies.size() > 0) {
        List<Company> cycle = new ArrayList<Company>();
        Company curr = companies.get(companies.length() - 1);
        cycle.add(curr);
        while (curr.parent != null) {
            curr = curr.parent;
            if (cycle.contains(curr)) {
                return cycle; // Cycle detected
            }
            cycle.add(curr);
        }
        companies.removeAll(cycle); // Remove all elements we traversed through just now
    }
    return null;
}

编辑：更改hasCycle的返回值，返回一个List<Company>，其中包含循环中的所有公司供进一步处理（打印出来、移除等）。

- M. Shaw

---

这个方法最好重写一下，抛出一个异常。 - Eric