Найдите самый длинный путь в графе

Question

Я пытаюсь найти самый длинный путь на графике, но у меня возникают проблемы, когда приходится возвращать самый длинный путь. Я выяснил рекурсию и могу следить за выходами, но не могу получить правильный вывод. В настоящее время программа возвращает несколько путей.

Ожидаемый выход при запуске из Лас-Вегаса: [Лас-Вегас, Солт-Лейк-Сити, Денвер, Хелена, Виннипег, Дулут]

Мой метод поиска в глубину:

public void dfs(City before, ArrayList<String> listOfCities){

    System.out.println(before +"-->"+ before.getAdjCities());

    List<City> neighbours = before.getAdjCities();
    before.setVisited(true);

    for (int i = 0; i < neighbours.size(); i++) {

        City n = neighbours.get(i);
        if(!n.visited){
            listOfCities.add(n.getCityName());
            System.out.println(i+ " Test: " + listOfCities.toString());

            dfs(n, listOfCities);
        }
    }
}

Вот вывод:

Вот график:

Answer 1

Ваш ListOfCities статичен во всех ветвях вашего поиска, поэтому он заканчивается во всех городах. Рекурсивный шаг в каждом городе должен сравнить результат DFS от каждого соседа, чтобы построить результат.