Формируйте маршрут с конечными точками

Question

Итак, давайте дадим конечные точки (A, B), (B, C), (C, D), тогда мы сможем сформировать маршрут A -> B -> C.

Обратите внимание, что порядок конечных точек задан случайным образом. Таким образом, (A, B), (C, D), (B, C) также дали бы маршрут A -> B -> C.

Но в целом, если нам заданы упорядоченные пары конечных точек, как построить маршрут?

Я не уверен, какая структура данных наиболее полезна здесь. Я думаю хранить каждую координату (x, y) в списке при чтении входных данных.

Так (A, B), (C, D) будет храниться как {A, B, C, D}. Является ли каждый элемент координатами x или y, можно определить по четности его позиции в списке (так что первая запись в списке - x, вторая запись - y, 3rd - x и т. Д.). Затем, когда каждая упорядоченная пара считывается, мы просматриваем список, чтобы увидеть, находится ли в списке либо координата x, либо y. Если это так, мы соединяемся.

Чтобы продемонстрировать, предположим, что мы читаем (A, B), (C, D), (B, C), наш список будет {A, B, C, D} после (C, D) просто читать. Когда считывается (B, C), мы видим, что B уже находится в списке. Итак, мы знаем, что A -> B -> C. Также в списке находится C, и мы имеем A-> B -> C -> D, а затем добавим (B, C) в список, чтобы сформировать {A, B , C, D, B, C}.

Мой трудный: как мы храним A -> B -> C? Какую структуру данных я должен использовать? Как мы отслеживаем частичный маршрут, который мы сформировали, когда мы идем?

Спасибо!

Answer 1

Построить график направленных ребер с adjacency представление списка. Затем используйте DFS в начальной точке до конечной точки и сохраните ранее посещенные узлы в буфере, и как только вы достигнете адресата, значения в буфере являются путем.