旅行门票问题

Question

您将获得一系列各种交通工具的旅行机票,这些机票将通过途中的几个站点将您从A点带到B点.所有的门票都没有故障,你不知道你的旅程从哪里开始,也不知道它的结束地点.按正确的顺序对门票进行排序以完成您的旅程.

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页的递归实现.