Проблема проездных билетов
Вам дают стопку проездных билетов для различных транспортных средств, которые возьмут Вас от точки для указания на B через несколько остановок на пути. Все билеты не работают, и Вы не знаете, где Ваша поездка запускается, ни где она заканчивается. Отсортируйте билеты в правильном порядке для завершения поездки.
tickets = [ {from: "Barcelona", to: "New York"} {from: "Barcelona", to: "Gerona"}, {from: "Madrid", to: "Barcelona"}, {from: "Gerona", to: "Barcelona"} ]Я предполагаю, правильный порядок то, что один:
tickets = [ {from: "Madrid", to: "Barcelona"}, {from: "Barcelona", to: "Gerona"}, {from: "Gerona", to: "Barcelona"}, {from: "Barcelona", to: "New York"} ]Поскольку нет никакого билета в Мадрид и никакого билета из Нью-Йорка.
Каков был бы лучший алгоритм для той задачи?
Языком является JavaScript, но агностическое языком решение было бы достаточно хорошо.
Обновление: Я изменил демонстрационные данные, которые не будут перепутаны с проблемой прохождения Перелета в одну сторону.
4 ответа
Если вы можете посетить узел (город) более одного раза, это проблема эйлерова пути .
Здесь представлены два простых алгоритма ее решения в зависимости от того, какой у вас тип графа. У вас есть рекурсивная реализация на странице 3 здесь .
У вас есть ориентированный граф, и вы хотите найти в нем Эйлеров путь . В связанной статье описан алгоритм его поиска, который в основном сводится к следующему:
- Найдите город с меньшим количеством маршрутов внутрь, чем выезд (если их нет, начните с любого места)
- Путешествуйте по билету (край), который не уйдет граф отключен, если его нет; если такого билета не существует, в этом случае используйте этот билет.
- Удалите билет (край) и повторите
Вы должны использовать все билеты до конечного пункта назначения.
Разве это не двусвязный список? Добавьте каждый элемент в список, связывая каждый соответствующим образом; когда вы закончите, у вас будет две записи с несвязанными ссылками (одна без подключения к узлу «от», вторая без подключения к узлу «с». Это начальная и конечная точки цепочку, и вы читаете их последовательно, начиная с записи, в которой отсутствует ссылка «от», и переходя по ссылке от одной записи к другой.
- Создайте ориентированный граф из ваших билетов.
- Найдите узел, имеющий степень 0
- Обойдите все узлы по ребрам графа, чтобы получить результат.
Обновление: с добавленной информацией в исходном сообщении, это решение не решает правильную проблему. Вместо этого посмотрите на ответ IVLad .