Welcome, guest | Sign In | My Account | Store | Cart

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

Python, 27 lines
 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

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.

1 comment

Karuppasamy 10 years, 4 months ago  # | flag

We can find Complete eulerian path using HIERHOLZERā€™S Algorithm. Complete C code and explanation available in following link. http://iampandiyan.blogspot.in/2013/10/c-program-to-find-euler-path-or-euler.html

Created by Przemek Drochomirecki on Sun, 5 Nov 2006 (PSF)
Python recipes (4591)
Przemek Drochomirecki's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks