检测循环依赖

Question

给定 "Scenarios" 的依赖关系树，我正在计算每个场景分支的 "weight"。

我需要检测循环依赖（场景 1 -> 场景 2 -> 场景 3 -> 场景 1）。

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

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

我应该只是检查一个字符串是否包含在字符串列表中，但这种情况永远不会捕获它。

我是否在错误的时间添加了 to/checking 列表？

编辑：

allScenarios 是：一个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;
}

检测循环依赖

Detecting Circular Dependencies

java

recursion

breadth-first-search