Suche eine Eulersche Tour

Ich versuche ein problem zu lösen, auf Udacity wie folgt beschrieben:

# 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]

Kam ich auf die folgende Lösung, die zwar nicht so elegant, wie einige der rekursive algorithmen, scheint zu funktionieren in meinem test-Fall.

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]

Jedoch beim Absenden, bekomme ich auch abgelehnt, durch die Schüler. Mache ich etwas falsch? Ich sehe keinen Fehler.

InformationsquelleAutor james_dean | 2012-09-16
Schreibe einen Kommentar