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問題的高效算法是不可能的」，這意味着你的問題不存在有效算法的可能性（儘管它仍有待證明）。