Python或C：将对的列表变成连接列表

Question

什么是C或python中的有效算法，给定表示两个数字之间关系的无序对的列表，将这些对组合起来，使它们形成一个连续的名单。

例如，给出如下：

(0, 1) 
(1, 2) 
(3, 2) 
(4, 3) 

产生如下：[0, 1, 2, 3, 4]

显然，这是行不通的，那里有在对空白或回路，例如，(0, 1) (3, 4)，在这些病例，抛出错误信息或类似的东西。

Answer 1

可以将数字建模为图中的顶点。然后列表中的每个元素将代表节点之间的边界。

你在找什么就是这张图的'欧拉路径'。这有多种算法。看看众所周知的算法：http://en.wikipedia.org/wiki/Eulerian_path

Answer 2

你试图做的不是欧拉路径（访问每个边缘一次），而是一个Hamiltonian path（访问每个顶点一次），因为你不想在你的循环中通过定义循环的路径意味着你不想访问任何顶点两次。

这个问题被称为NP-complete，这意味着没有已知的高效算法（如果您在polynomial time中指的是“高效”）。

如果你可以找到一个有效的算法解决这个问题，你也可以通过显示P和NP是相等的来解决P vs NP problem。大多数计算机科学家认为，P vs NP问题的答案是“不，NP问题的高效算法是不可能的”，这意味着你的问题不存在有效算法的可能性（尽管它仍有待证明）。