сортировка списка дорожных развязок

Question

У меня есть объект

class Junction {
   private String name;
   private String previous;
   private String next;
}

Теперь эти соединения имеют следующий формат

Junction[name="T1H", previous="T0F", next="T345"]
Junction[name="K109", previous="TRH", next="JHD"]
Junction[name="LM89", previous="T1H", next="D679"]
Junction[name="TRH", previous="LM89", next="T345"]

Выше было бы упорядочено так:

T1H->LM89->TRH->K109

Ноесли бы у меня был неупорядоченный список, как я мог бы отсортировать это?Какой лучший алгоритм в Java, чтобы сделать это.Быстрая сортировка не сработает, потому что концепция pivot и выше и ниже на самом деле не применяется.Вы не можете работать, если что-то выше, так как все соединения связаны.

Пузырьковая сортировка кажется логичной.

Есть идеи?

Answer 1

Вы можете использовать хеш-карту для хранения преемника для каждого соединения, используя атрибут этих соединений previous. используя None, null или любое другое специальное значение, если «предыдущий» переход отсутствует в списке. Это предполагает, что все соединения являются прямыми наследниками или каким-либо другим соединением, и никакие два соединения не имеют одинакового «предыдущего» соединения. Сложность будет O (n) для n соединений.

from collections import namedtuple
Junction = namedtuple("Junction", "name previous next")
junctions = [
    Junction(name="T1H", previous="T0F", next="T345"),
    Junction(name="K109", previous="TRH", next="JHD"),
    Junction(name="LM89", previous="T1H", next="D679"),
    Junction(name="TRH", previous="LM89", next="T345")
]

d = {j.name: j for j in junctions}  # map names to junctions
succ = {j: None for j in junctions} # map previous to successor
for j in junctions:
    p = d.get(j.previous, None)
    succ[p] = j

Затем, начиная с соединения, являющегося преемником None, повторяем все соединения:

j = succ[None]
while j:
    print(j)
    j = succ[j]

Выход:

Junction(name='T1H', previous='T0F', next='T345')
Junction(name='LM89', previous='T1H', next='D679')
Junction(name='TRH', previous='LM89', next='T345')
Junction(name='K109', previous='TRH', next='JHD')

(здесь используется Python, поскольку вы специально не запрашивали решение для Java, но, конечно, то же самое можно легко сделать в Java.)