ActiveState Code

Recipe 498243: Finding Eulerian path in undirected graph

Takes as input a graph and outputs Eulerian path (if such exists). The worst running time is O(E^2).

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Finding Eulerian path in undirected graph
# Przemek Drochomirecki, Krakow, 5 Nov 2006

def eulerPath(graph):
    # counting the number of vertices with odd degree
    odd = [ x for x in graph.keys() if len(graph[x])&1 ]
    odd.append( graph.keys()[0] )

    if len(odd)>3:
        return None
    
    stack = [ odd[0] ]
    path = []
    
    # main algorithm
    while stack:
        v = stack[-1]
        if graph[v]:
            u = graph[v][0]
            stack.append(u)
            # deleting edge u-v
            del graph[u][ graph[u].index(v) ]
            del graph[v][0]
        else:
            path.append( stack.pop() )
    
    return path

Discussion

Example: (a well-known puzzle - how to draw an envelope without lifting a pen) eulerPath({ 1:[2,3], 2:[1,3,4,5], 3:[1,2,4,5], 4:[2,3,5], 5:[2,3,4] })

The worst time complexity can be easily changed into O(E) category. All you have to do is providing different graph representation which allows you deleting an edge in O(1) time.

Sign in to comment