Проблема с проездными билетами

Question

Вам предоставляется пачка проездных билетов на различные перевозки, которые доставят вас из точки А в точку Б через несколько остановок в пути.Все билеты не в порядке, и вы не знаете, где начинается ваше путешествие и где оно заканчивается.Сортируйте билеты в правильном порядке, чтобы завершить путешествие.

tickets = [
  {from: "Barcelona", to: "New York"}
  {from: "Barcelona", to: "Gerona"},
  {from: "Madrid",    to: "Barcelona"},
  {from: "Gerona",    to: "Barcelona"}
]

Полагаю, правильный порядок такой:

tickets = [
  {from: "Madrid",    to: "Barcelona"},
  {from: "Barcelona", to: "Gerona"},
  {from: "Gerona",    to: "Barcelona"},
  {from: "Barcelona", to: "New York"}
]

Поскольку билетов в Мадрид нети никаких билетов из Нью-Йорка.

Какой алгоритм лучше всего подойдет для этой задачи?

Язык - это JavaScript, но не зависящее от языка решение будет достаточно.

Обновление: Я изменил пример данных, чтобы не путать с Проблема полета в один конец .

Answer 1

Если вы можете посетить узел (город) более одного раза, это проблема Эйлера .

Здесь - это два простых алгоритма решенияв зависимости от того, какой тип графика у вас есть.У вас есть рекурсивная реализация на странице 3 здесь .

Answer 2

У вас есть ориентированный граф, и вы хотите найти в нем Эйлерову траекторию . В связанной статье описывается алгоритм его поиска, который в основном:

1. Найти город с меньшим количеством маршрутов, чем вне (если их нет, начать с любого места)
2. Путешествие по билету (ребру), при котором график не будет отключен, если его там нет; если такого билета не существует, в этом случае используйте этот билет.
3. Удалить билет (ребро) и повторить

В конечном итоге вы должны использовать все билеты и в конечном пункте назначения.

Answer 3

1. Создайте ориентированный граф из ваших билетов.
2. Найдите узел, у которого есть степень 0
3. Итерируйте по всем узлам через ребра графа, чтобы создать ваш результат

Обновление: с добавленной информацией в оригинальном сообщении, это решение не решает правильную проблему.Вместо этого посмотрите на ответ IVLad .

Answer 4

Разве это не просто двусвязный список?Добавьте каждый элемент в список, связывая каждый из них по мере необходимости;когда вы закончите, у вас будет две записи с неподключенными ссылками (одна, с ничем не связанная с ее узлом «от», другая без соединения на его узле «к».цепочку, и вы читаете их последовательно, начиная с записи, в которой отсутствует ссылка «от», и переходя по ссылке от одной записи к следующей.

Answer 5

Ниже приведен пример реализации javascript.

var un  =
[
 { from:'c',to:'d'},
 { from:'a',to:'b'},
 { from:'b',to:'c'},
 { from:'z',to:'a'},
 { from:'d',to:'m'},
]

function buildTable( un ){
return un.reduce(function(previousValue, currentValue, currentIndex ){

//build the table.
    previousValue.from[currentValue['from']] = currentValue;
    previousValue.to[currentValue['to']] = currentValue;

//to find start and end.    
    if( !previousValue.from[currentValue['to']] )  previousValue.from[currentValue['to']]= false;
    if(!previousValue.to[currentValue['from']])  previousValue.to[currentValue['from']]= false;

    return previousValue;

},{to:{},from:{}} );


}

function getStart(nodes){
//find start node indx.
    for(var i  in nodes)
    if( !nodes[i] )return i;
}


function print(start,nodes ){


var sorted = [];
//while detecting false from buildTable structure.
    while(start){
        var  node = nodes[start];
        sorted.push(node)
        start = node['to'];
//console.log(start)
    }

return sorted;
}

var sorted = buildTable(un);
console.log(print(getStart(sorted.to),sorted.from));