algorithm - 旅行票问题

Question

You are given a stack of travel tickets for various transportations that will take you from a point A to point B via several stops on the way. All of the tickets are out of order and you don't know where your journey starts, nor where it ends. Sort the tickets in the right order to complete your journey.

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，但与语言无关的解决方案就足够了。

Update: I changed sample data to be not confused with One-way flight trip problem.

Answer 1

如果你可以多次访问一个节点(一个城市)，这就是eulerian path problem .

Here有两种简单的算法来解决它，具体取决于您拥有的图形类型。您在第 3 页上有一个递归实现 here .