Алгоритм создания связанного списка из набора узлов

Question

Я ищу алгоритм для создания связанного списка из набора узлов.Например, предположим, что узел - это авиабилет от пункта отправления до пункта назначения.(например, Чикаго в Детройт) и есть несколько авиабилетов.Предполагая, что все эти авиабилеты перемешаны, что является лучшим способом определить весь путь путешествия.Если есть 5 авиабилетов, таких как Чикаго-> Детройт, Денвер-> Чикаго, Детройт-> DC, DC-> Нью-Йорк, Сан-Хосе-> Денвер, алгоритм должен быть в состоянии найти правильный путь от начала до конца.

Сан-Хосе -> Денвер -> Чикаго -> Детройт -> DC -> Нью-Йорк

Answer 1

Если вам гарантировано, что узлы образуют один путь (т. Е. Максимальная степень равна 1, максимальная степень равна 1, ровно один узел имеет степень 0, ровно один узел имеет степень 0), тогда вы можете сделать следующее:

• Создайте два хэша: in_cities и out_cities
• Для каждого узла A -> B, добавьте его к in_cities с ключом A и out_cities с ключом B
• Выберите узел произвольно, назовите его S
• У curr есть указатель на S. Пока исходный город curr находится в out_cities, вставьте соответствующий узел в начало пути. Обновите curr, чтобы он указывал на этот узел.
• У curr есть указатель на S. Пока город назначения curr находится в in_cities, добавьте соответствующий узел в конец пути. Обновите curr, чтобы он указывал на этот узел.

Теперь все готово, в линейном времени по отношению к общему количеству городов.

Answer 2

Это не вопрос связанного списка; это теория графов вопрос.

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

A path в графе - это последовательность вершин, в которой есть ребро от каждой вершины до следующей вершины в последовательности.

Отношение смежности обычно представляется одним из двух способов: матрица смежности (простой двумерный массив) или список смежности (который использует связанный список), но проблемы и решения могут быть определены независимо от представления (хотя это влияет на сложность).

Например, задача кратчайшего пути назначает веса ребрам и требует пути между двумя узлами, общий вес которых минимизирован. Классическое решение, которое преподается в курсе информатики, - это алгоритм Дейкстры .

В большинстве хороших книг по алгоритмам есть глава по теории элементарных графов.

---

Сказав все это, есть специальный вид графа, называемый граф путей , который может быть тем, чем является ваш входной граф (это можно подтвердить только после того, как все предположения о проблемах сделал явным). Если ваш входной граф относится к этому простому типу, то существует простое решение вашей проблемы (см. ответ Данбена ).

Я представлю тот же алгоритм в форме псевдокода:

LET pred BE a MAP City=>City // "predecessor"
LET succ BE a MAP City=>City // "successor"

// build pred and succ
FOR EACH Ticket(City A, City B) DO
   pred[B] = A
   succ[A] = B

// find the starting city, i.e. one that doesn't have a pred
LET C BE any City
WHILE pred[C] != NULL
  C = pred[C]

// keep going until you reach the end
WHILE C != NULL
  PRINT C
  C = succ[C]

При хорошей реализации MAP это O(N), где N - количество билетов.