我正在尝试解决有关Udacity的问题，描述如下：
# Find Eulerian Tour # # Write a function that takes in a graph # represented as a list of tuples # and return a list of nodes that # you would follow on an Eulerian Tour # # For example, if the input graph was # [(1, 2), (2, 3), (3, 1)] # A possible Eulerian tour would be [1, 2, 3, 1]
我提出了以下解决方案，该解决方案虽然不如某些递归算法那么出色，但似乎可以在我的测试用例中使用。
def find_eulerian_tour(graph): tour = [] start_vertex = graph[0][0] tour.append(start_vertex) while len(graph) > 0: current_vertex = tour[len(tour) - 1] for edge in graph: if current_vertex in edge: if edge[0] == current_vertex: current_vertex = edge[1] elif edge[1] == current_vertex: current_vertex = edge[0] else: # Edit to account for case no tour is possible return False graph.remove(edge) tour.append(current_vertex) break return tour graph = [(1, 2), (2, 3), (3, 1)] print find_eulerian_tour(graph) >> [1, 2, 3, 1]
但是，提交此内容时，我被分级机拒绝了。我做错了吗？我看不到任何错误。
这是您的算法失败的有效情况：
graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
利用的力量print来找出graph和会发生什么current_vertex。
print
graph
current_vertex
另一个提示：else向下移动，使其属于和，for并且在for循环不中断时执行。现在，它永远无法执行。 更正之后，算法当然仍然会失败。
else
for
当然，该算法仍然会失败。
请不要发表评论说代码不起作用。没有。即使下面的代码执行了OP的预期，该算法仍然会失败。关键是要表明OP的算法是错误的，而OP无法确定。为此，需要正确执行OP算法（请参见下文）。错误算法的正确实现仍然不是正确的解决方案。
很抱歉，通过写所有这些冗长的解释使这个答案更糟，但是人们仍然抱怨该代码不起作用（当然，这是要表明它是错误的）。他们也否决了这个答案，可能是因为他们希望能够复制代码作为解决方案。但这不是重点，重点是向OP证明他的算法有错误。
以下代码找不到欧拉之旅。 寻找其他地方复制代码以传递您的帮助！
def find_eulerian_tour(graph): tour = [] current_vertex = graph[0][0] tour.append(current_vertex) while len(graph) > 0: print(graph, current_vertex) for edge in graph: if current_vertex in edge: if edge[0] == current_vertex: current_vertex = edge[1] else: current_vertex = edge[0] graph.remove(edge) tour.append(current_vertex) break else: # Edit to account for case no tour is possible return False return tour graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)] print(find_eulerian_tour(graph))
输出：
[(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)] 1 [(2, 3), (3, 1), (3, 4), (4, 3)] 2 [(3, 1), (3, 4), (4, 3)] 3 [(3, 4), (4, 3)] 1 False
