问题描述
我正在尝试解决 Udacity 上的一个问题，如下所述:
I am trying to solve a problem on Udacity described as follows:
# 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]
我想出了以下解决方案，虽然不像某些递归算法那么优雅，但似乎在我的测试用例中有效.
I came up with the following solution, which, while not as elegant as some of the recursive algorithms, does seem to work within my test case.
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]
然而，当我提交这个时，我被评分者拒绝了.我做错了什么?我看不到任何错误.
However, when submitting this, I get rejected by the grader. I am doing something wrong? I can't see any errors.
推荐答案
以下是您的算法失败的有效情况:
Here's a valid case where your algorithm fails:
graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
利用print 的强大功能找出graph 和current_vertex 会发生什么.
Use the power of print to find out what happens to graph and current_vertex.
另一个提示:将else 向下移动，使其属于for 并在for 循环未中断时执行.就像现在一样，它永远无法执行.在修正之后，算法当然还是失败了.
Another hint: Move the else down so that it belongs to the for and is executed when the for loop is not broken. As it is now, it can never be executed. After that correction, the algorithm still fails, of course.
当然，算法仍然失败.
当然，算法仍然失败.
请不要评论说代码不起作用.它没有.该算法仍然失败，即使下面的代码符合 OP 的想法.关键是要表明 OP 的算法是错误的，这是 OP 无法确定的.为此，需要正确实现 OP 的算法(见下文).错误算法的正确实现仍然不是正确的解决方案.
Please, don't comment stating that the code doesn't work. It doesn't. The algorithm still fails, even if the code below does what the OP had in mind. The point was to show that the OP's algorithm is wrong, which the OP couldn't determine. For that, a correct implementation of OP's algorithm is needed (see below). A correct implementation of a wrong algorithm is still not a correct solution.
很抱歉通过编写所有这些冗长的解释使这个答案变得更糟，但是人们继续抱怨代码不起作用(当然，重点是表明它是错误的).他们也反对这个答案，可能是因为他们希望能够复制代码作为解决方案.但这不是重点，重点是向OP表明他的算法存在错误.
I'm sorry to make this answer worse by writing all these lengthy explanations, but people continue to complain that the code doesn't work (of course, the point was to show that it is wrong). They also downvote this answer, probably because they expect to be able to copy the code as a solution. But this is not the point, the point is to show to the OP that there is an error in his algorithm.
下面的代码没有找到欧拉旅行.寻找其他地方复制代码以传递您的评估！
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
这篇关于寻找欧拉之旅的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！