Java рекурсивно упражняется

Question

Мне нужны некоторые рекомендации по следующему упражнению. У меня есть собственный список, в котором он имеет города, каждый город знает, в какой город он соединяется, это маршрут, маршрут имеет время, которое вам нужно, чтобы добраться между городами. Что им предложено сделать это: учитывая город и когда-X:

public IList citiesWithRange(City c, int timeMinutes);

я должен вернуться ко всем городам я могу достичь в течение этого времени. IList - это список, сделанный мной. Любая помощь будет оценена по достоинству.

Спасибо.

Answer 1

Что вам нужно, это реализация алгоритма, который возвращает пути между узлами в графе.

Посмотрите на алгоритм Дейкстры здесь: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Это может быть полезно также: https://www.ics.uci.edu/~eppstein/161/960208.html

Answer 2

Вы можете попытаться решить эту проблему с несколько более простых шагов в вашей рекурсивной функции

Эта функция должна быть вызвана в стартовом городе и должна быть предоставлена ​​стопка для добавления соответствующих городов также, а также количество времени

1. Выход, если оставшееся время отрицателен
2. Log текущий город в стек
3. Loop через все соединительные города, вызывая рекурсивную функцию на каждом из них с стеком и оставшееся время минус путешествия времени

в конце этого стек будет содержать все действительные города и могут быть дубликатами

Удалить дубликаты и у вас есть все возможные города вы можете путешествовать в