检测循环依存关系

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

我需要检测循环依赖项(场景1->场景2->场景3->场景1)。

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

List 然后检查 dependsOnScenarios (场景名称数组)。

我应该只是检查一个字符串是否包含在一个字符串列表中,但这个场景从未捕捉到它。

我是否在错误的时间添加/检查列表?

编辑:

allScenarios is:a ConcurrentHashMap<String, Scenario>

依赖场景 是一个 String[] 以及 Scenario

name 是字符串和的属性 脚本

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;
}