В поисках Эйлера
Я пытаюсь решить проблему с 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]
Тем не менее, при отправке этого, я получаю отклонение от грейдера. Я делаю что-то не так? Я не вижу никаких ошибок.