检测圆属地

Question

给定“场景”的依赖树，我正在计算每个场景分支的“权重”。

我需要检测循环依赖项(scenario1 -> scenario2 -> scenario3 -> scenario1)。

我目前正在进行广度优先搜索，并在递归链中传递一个列表，但是我无法检测到循环依赖项。

每次迭代，我都会将当前场景(字符串)添加到List中，然后检查dependsOnScenarios (一个场景名称数组)。

我应该只是检查字符串是否包含在string列表中，但是这个场景永远不会捕捉到它。

我是不是在错误的时间增加了/核对这个列表？

编辑：

allScenarios is: a ConcurrentHashMap<String, Scenario>

dependsOnScenarios是String[]，是Scenario的一个属性。

name是一个字符串，是Scenario的一个属性

getWeight最初是用空列表调用的：

s.priority = getWeight(s, new ArrayList<String>())+1;

输入：

Scenario g1=new Scenario("Scenario1" , null);
Scenario g2=new Scenario("Scenario2" , new String[]{"Scenario4"});
Scenario g3=new Scenario("Scenario3" , new String[]{"Scenario1","Scenario2"});
Scenario g4=new Scenario("Scenario4" , new String[]{"Scenario3"});

代码：

private static int getWeight(Scenario scenario, List<String> visited) throws Exception{
  int numDep = 0;         
  visited.add(scenario.name);  
  if(scenario.dependsOnScenarios != null){          
      for(String dependency:scenario.dependsOnScenarios) {
           if(visited.contains(dependency)){
                 throw new Exception("Circular Reference: "+dependency+" has already occured");
           }
           return scenario.dependsOnScenarios.length + getWeight(allScenarios.get(dependency),visited);
      }
  }
  return numDep;
}

Answer 1

我的问题是，在评估和检查整个列表之前，我正在从循环中返回。我需要使用一个额外的循环来检查所有的内容。

private static int getWeight(Scenario scenario, List<String> visited) throws Exception{
  int numDep = 0;
  visited.add(scenario.name);
  if(scenario.dependsOnScenarios != null){
      for(String dependency:scenario.dependsOnScenarios) {
          if(visited.contains(dependency)){
             throw new Exception("Circular Reference: "+String.join("->",visited)+"->"+dependency);
          }
      }
      for(String dependency:scenario.dependsOnScenarios) {              
          return scenario.dependsOnScenarios.length + getWeight(allScenarios.get(dependency),visited);
      }
  }
  return numDep;
}