Eine Eulerian Tour finden
Ich versuche, ein Problem mit Udacity zu lösen, das wie folgt beschrieben wird:
# 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]
Ich habe die folgende Lösung gefunden, die zwar nicht so elegant ist wie einige der rekursiven Algorithmen, aber in meinem Testfall zu funktionieren scheint.
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]
Wenn ich dies abschicke, werde ich jedoch vom Grader abgelehnt. Mache ich was falsch Ich kann keine Fehler sehen.