Finding a Eulerian Tour

Posted by user590903 on Stack Overflow See other posts from Stack Overflow or by user590903
Published on 2012-09-16T14:52:10Z Indexed on 2012/09/16 15:38 UTC
Read the original article Hit count: 182

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]
                else:
                    current_vertex = edge[0]
                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.

© Stack Overflow or respective owner

Related posts about python

Related posts about graph