Поиск в глубину, чтобы найти все пути между узлами

Question

Я пытался решить эту проблему поиска в глубину, но я не могу ее решить. Я хочу напечатать все пути, но каким-то образом он печатает только некоторые пути. Я могу понять ошибку здесь в течение столь длительного времени:

  void printAllPathsUtil(Vertex v, Vertex d, ArrayList<Vertex> path){

        v.state = VISITED;
        path.add(v);

        if (v == d) {
            for (Vertex p : path) {
                System.out.print("Print: " + p.value + " ");
            }
            System.out.println();
        }
        else {
            for (Vertex city : v.outboundCity){

                if (city.state == UNVISITED) {

                    printAllPathsUtil(city, d, path);
                }
            }
        }
        path.remove(v);
        v.state = UNVISITED;
    }


    void printAllPaths(Vertex v, Vertex u){
        clearStates();
        ArrayList<Vertex> path = new ArrayList<>();
        printAllPathsUtil(v, u, path);
    }

Vertex Class выглядит примерно так:

public class Vertex{
String value;

Vertex previous = null;
int minDistance = Integer.MAX_VALUE;

List<Vertex> inboundCity;
List<Vertex> outboundCity;
State state;
}

Answer 1

Я думаю, что вы должны иметь эти две строки внутри loop:

path.remove(v);
v.state = UNVISITED;

Вы должны удалить вершины из пути и "отменить их" сразу после завершения рекурсии, а не после завершения цикла