问题描述
＃寻找欧莱雅游览
＃
＃编写一个函数，它接收一个图元
＃，表示为一个元组列表
＃，并返回一个节点列表，其中
＃表示您将在Eulerian Tour中遵循
＃
＃例如，如果输入图形是
＃[（1,2），（2,3），（3,1）]
＃可能的欧拉旅游将是[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]
为图中的边：
if current_vertex in edge：
if edge [0] == current_vertex：
current_vertex = edge [1]
elif edge [1] == current_vertex：
current_vertex = edge [0]
其他：
＃可能的
返回False
graph.remove（边缘）
tour.append（current_vertex）
break
返回游览
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 的功能找出发生在图表和 current_vertex 。
另一个提示：将 else 向下移动，使其对属于，并在 for 循环没有被破坏。就像现在一样，它永远不会被执行。当然，修正之后，算法仍然失败。
算法仍然失败。
请不要评论说明代码不起作用。它没有。算法仍然失败，即使下面的代码不符合OP的想法。重点是要证明OP的算法是错误的，OP不能确定。为此，需要正确实施OP的算法（见下文）。正确实现错误的算法仍然不是一个正确的解决方案。
我很抱歉通过编写所有这些冗长的解释来使这个答案变得更糟，但人们继续抱怨代码不起作用（当然，重点是以表明它是错误的）。他们也低估了这个答案，可能是因为他们希望能够将代码复制为解决方案。但这不是重点，关键是要向OP展示他的算法存在错误。
下面的代码没有找到eulerian之旅。
def find_eulerian_tour（graph）：
tour = []
current_vertex = graph [0] [0]
tour.append（current_vertex）
while len（graph）> 0：
print（graph，current_vertex）
用于图中的边：
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
其他：
＃编辑以计算不可能旅行
返回False
返回旅程
图形= [（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
假
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)]
Use the power of print to find out what happens to graph and current_vertex.
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.
The algorithm still fails, of course.
The algorithm still fails, of course.
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.
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.
The code below does not find eulerian tours. Look elsewhere to copy code for passing your assingments!
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))
Output:
[(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
这篇关于寻找欧莱雅之旅的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！