Алгоритм для быстрого получения частичного упорядочивания по нескольким связанным спискам
У меня такая ситуация:
- У меня есть n двусвязных списков
- Каждый список имеет начало и конец контрольного сигнала
- Все списки имеют одинаковые начальный и конечный узел (не требуется, но для простоты)
- Списки однородны и могут содержать общие элементы
Я бы хотел найти частичное упорядочение всех узлов во всех n списки, начиная с начального узла и заканчивая, ну, конечным узлом, так что любой узел, который появляется в списках nx , где x
Использование массивов для предоставления примерного набора списков:
first = [a, b, d, f, h, i];
second = [a, b, c, f, g, i];
third = [a, e, f, g, h, i];
Очевидно, один из возможных ответов был бы [a, b, c, d, e, f, g, h, i], но другой допустимый порядок будет [a, b, d, e, c, f, g, h, i].
Я знаю, что там есть a быстрый алгоритм для этого, кто-нибудь помнит, как это происходит или как это называется? У меня уже есть несколько медленных версий, но я уверен, что где-то в Кнута есть гораздо более быстрая.
(И, прежде чем вы спросите, это не для домашнего задания или проекта Эйлера, и я больше не могу это сделать проблема.)
Изменить: я относительно уверен, что частичное упорядочение определяется только до тех пор, пока конечные точки находятся во всех списках и в одинаковых позициях (начало и конец ). Я не был бы против поиска в линейном времени для поиска этих конечных точек, и если они не могут быть найдены, то там может возникнуть ошибка.