java - 如何在特殊图中获取从叶子到根的所有路径

Question

我正在尝试以图形形式在特殊数据结构中实现算法。我的目标是获取从叶(目标元素)到根的所有路径。这就是图表的样子，如下图所示。

Answer 1

我们需要记住我们拥有的所有路径，以便在图中以所有不同的方式遍历，因此只有一个状态列表是不够的，我们需要一个路径列表。对于每条路径，如果它有一个父路径，我们会将其加长，如果它有两个或更多路径，我们将复制此列表并将父路径添加到每个路径。

嗯，我不擅长 Java，我无法运行这段代码，所以我不能保证它会运行，但算法没问题。

public static List<ARGState> getAllErrorStatesReversed(ReachedSet reachedSet) {
  ARGState pIsStart =
      AbstractStates.extractStateByType(reachedSet.getFirstState(), ARGState.class);
  ARGState pEnd = targetStates.get(0);

  List<List<ARGState>> results = new ArrayList<>();
  List<List<ARGState>> paths = new ArrayList<>();

  paths.add(new ArrayList<ARGState>(pEnd));

  // This is assuming from each node there is a way to go to the start
  // Go on until all the paths got the the start
  while (!paths.empty()) {
    // Expand the last path on your list
    List<ARGState> curPath = paths.remove(paths.size() - 1);
    // If there is no more to expand - add this path and continue
    if (curPath.get(curPath.size() - 1) == pIsStart) {
      results.append(curPath);
      continue;
    }

    // Expand the path
    Iterator<ARGState> parents = curPath.get(curPath.size() - 1).getParents().iterator();
    // Add all parents
    while (parentElement.hasNext()) {
      ARGState parentElement = parents.next();
      List<ARGState> tmp = new ArrayList<ARGState>(List.copyOf(curPath));
      tmp.add(parentElement);
      paths.add(tmp);
    }
  }
  return results;
}

希望您能理解，欢迎多多提问。
祝你好运