Нужен алгоритм для расчета последовательности

Question

Я пытаюсь найти решение проблемы, где у меня есть что-то вроде

1. A> B
2. B> C
3. B> D
4. C> D

И я должен получить ответ как A> B> C> D.

Условия для этой проблемы

1. В выводе будут задействованы все элементы.
2. Проблема не будет иметь никаких поддельных входов. например, (A> B) (C> D) является поддельным входом, поскольку мы не можем определить выход.
3. Входные данные могут быть любого размера, но не поддельными, и всегда найдется решение проблемы.

Мне нужно найти оптимальное решение для этого, используя Java Collections. Любые советы / подсказки приветствуются.

Заранее спасибо!

Answer 1

Это называется топологическая сортировка. http://en.wikipedia.org/wiki/Topological_sorting

Учитывая это, вы сможете выполнить домашнее задание самостоятельно.

Answer 2

Бьюсь об заклад, вы недавно покрыли графики в этом классе ...
Как вы думаете, график может быть применен здесь?
Можете ли вы придумать структуру, которую можно построить на основе проблемных входов (A> B>, A> D, C> A и т. Д.)? Может быть, какой-то ориентированный граф ...

Как только проблема выражена в таком графике, решение будет включать в себя навигацию по этому графику ...

Answer 3

Вы можете сделать это с помощью карты входов и рекурсивного метода, который добавляет свой ответ к возвращенному списку (или просто печатает каждый узел по мере его спуска по дереву.) Если вы возвращаете ответ, тогда pre - добавление к возвращенному списку предотвратит обратный ответ D-> C-> B-> A по завершении (или вы можете просто .reverse () список в конце.) Не забудьте проверить на состояние разрыва при повторении. (подсказка: ключ не найден)

Answer 4

Вы начинаете помещать их в List. Список будет отсортирован, поэтому для n -ой пары (a, b) вы ищите a, используя двоичный поиск. Если он уже существует, пропустите, если нет, вставьте в нужную точку. Начиная с a > b, вы делаете это снова с b в оставшейся части списка. Надеюсь, что это поможет.