4

有一个类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;

然后它将在公司层次结构中创建一个循环复杂度无限循环，我们必须在我们的系统中避免这种循环。

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

4

3 回答 3

6

您的任务与圈复杂度无关。您的实体基本上形成了一个图表，您想要检测其中的循环。常见的方法是执行DFS。

您可以在 Internet上找到大量示例。

于 2015-08-10T08:29:58.020 回答
1

我已经以编程方式解决了这个问题，创建了一个本地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 是可索引的：它正确覆盖hashCodeand equals。

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

于 2015-08-10T08:34:42.617 回答
0

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

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>包含循环中的所有公司以供进一步处理（打印出来、删除它们等）。

于 2015-08-10T08:12:18.720 回答