Реконструировать последовательность из набора частичных порядков
У меня есть набор пар элементов. Каждая из этих пар означает: в окончательной последовательности первые элементы предшествуют второму элементу. Набор пар содержит достаточно пар, чтобы восстановить уникальную последовательность.
например.:
Если мой набор пар {(A, B), (A, C), (C, B)}
= A предшествует B, A предшествует C и C предшествует B.
моя последняя последовательность ACB,
Теперь мне нужен алгоритм для восстановления последовательностей из таких парных наборов. Эффективность имеет решающее значение. Любой умный совет приветствуется!
2 ответа
Решение
Создайте ориентированный граф из этих пар, затем выполните топологическую сортировку.
Это проблема топологической сортировки ориентированного графа. Прочитайте больше